任意のユニタリ変換を定数深さで近似――指数個の補助量子ビットとファンアウトゲートが前提

n量子ビットの任意のユニタリ変換は、1・2量子ビットゲートを使った深さ2^{O(n)}の回路で実装できることが知られていましたが、指数関数的な深さが本当に必要かは未解決でした。本研究は、2^{O(n)}個の補助量子ビットを使えば、誤差εで深さpoly(n, log 1/ε)の回路に並列化できることを示しました。さらに大きさ2^{O(n)}のファンアウトゲートを許せば、深さを定数にまで減らせます。ゲートの総数は指数個のままで、理論上の結果です。手法は、Aaronson-Kuperbergのユニタリ合成問題を局所復号可能符号・秘密情報検索と結びつけたものです。