A log-depth in-place quantum Fourier transform that rarely needs ancillas

技術要約：補助量子ビットをほとんど必要としない、対数深さのインプレース量子フーリエ変換

問題提起
特定のユニタリ演算のための量子回路を設計する際には、リソース制約（深さ、量子ビット数、局所性）と近似誤差の間のバランスを取る必要があります。従来のアプローチでは、あらゆる可能な入力状態に対して低い誤差でユニタリを近似する「最悪ケース」の保証を求めることが一般的です。しかし、この「最悪ケース」の保証を実現しようとすると、大量の補助量子ビット、長距離ゲート、あるいは深い回路といった多大なリソースが必要になります。例えば、従来の対数深さの量子フーリエ変換（QFT）構成では、$O(n)$ 個の補助量子ビット、長距離の結合性、または測定ベースのフィードフォワードが必要でした。著者らは、より大きな量子アルゴリズム内における多くのアプリケーションにおいては、すべての入力に対してではなく、ほとんどの入力に対して良好な近似を実現することが十分であり、「悪い」入力（誤差が大きい入力）は稀であるか、あるいは簡約化によって対処可能であると考えています。

手法
本論文は、「楽観的量子回路（optimistic quantum circuits）」のフレームワークを導入し、それをQFTに適用した後、最悪ケースの入力を処理するための簡約化技術を提示しています。

1. 楽観的量子回路:
   著者らは、ターゲットとなるユニタリ $U$ に対する楽観的量子回路 $C$（ユニタリ $\tilde{U}$ を誘導するもの）を、任意の正規直交基底における平均二乗誤差が $\epsilon$ 未満であるものとして定義します。形式的には、$\frac{1}{\dim \mathcal{H}} \sum_i \|\tilde{U}|\phi_i\rangle - U|\phi_i\rangle\|^2 < \epsilon$ です。この定義は基底に依存せず、誤差演算子のフロベニウスノルムを制限することと同等です。極めて重要な点は、これにより、誤差が $O(1)$ となる「悪い」入力の小部分集合が存在しても、その部分集合がヒルベルト空間のわずか $O(\epsilon)$ の割合しか占めない限り、許容されるということです。

2. 楽観的QFTの構成:
   著者らは、$n$ 量子ビットに対する誤差パラメータ $\epsilon$ の楽観的QFT ($\widetilde{\text{QFT}}$) を構築しています。

• ブロック分割アプローチ: 入力レジスタをサイズ $m = O(\log(n/\epsilon))$ のブロックに分割します。
• 位相推定のトリック: この回路は、ブロックに対して逆QFTを適用することが、隣接するブロックの位相因子の位相推定を近似するという事実を利用しています。ブロックに対して $\text{QFT}^\dagger$ を適用することで、回路は隣接ブロックからの位相寄与を推定します。
• 交換: 構成において、$\text{QFT}^\dagger \text{QFT}$ という形の恒等写像を挿入し、互いに可換なブロックを互いに通過させます。これにより、標準的な近似QFTの線形依存の連鎖を断ち切ります。
• 失敗モード: 位相推定は、入力状態がブロック上で $0$または$2^m$の近くにあるとき（すなわち、長い$0$または$1$の文字列のとき）に、モジュロ$2^m$ での回り込み（wrap around）が発生し、失敗します。これらが「悪い」部分空間を構成します。
• リソース: 得られる回路は、深さ $O(\log(n/\epsilon))$、正確に $n$ 量子ビットを使用（補助量子ビットなし）、1次元量子ビット配置に対して局所的（範囲 $O(\log(n/\epsilon))$）、かつ測定フリーです。

3. 最悪ケースから平均ケースへの簡約化:
   入力が「悪い」部分空間に集中する可能性のあるシナリオに対処するため、著者らは楽観的回路を一般的な近似回路へと変換するための簡約化を提案しています。

• ランダム化された簡約化: 楽観的回路を適用する前に、ユニタリ1-デザインからのランダムなユニタリ $V$ を適用します。その後、$\hat{V}^\dagger = U V^\dagger U^\dagger$ を適用します。これにより入力状態がランダム化され、高誤差部分空間に到達する確率が低くなります。
• 決定論的な簡約化: ランダム化されたプロセスは、$V$ の選択を制御レジスタにエンコードすることで、ユニタリ演算へと純化（purify）できます。
• 特定の1-デザイン: QFTについては、Weyl-Heisenberg群（Pauli的なシフトと位相勾配の一様サンプリング）を1-デザインとして利用します。この選択により、必要なランダム化およびアンランダム化の操作が効率的になることが保証されます。

主な貢献と結果

• 楽観的QFT: 本論文は、以下の特性を同時に達成する最初のQFT構成を提示しています：
  • 深さ: $O(\log(n/\epsilon))$
  • 量子ビット数: $n$ （補助量子ビットなし）
  • 局所性: $O(\log(n/\epsilon))$ の範囲（1次元において局所的）
  • 測定フリー
  • 誤差: ヒルベルト空間の $O(\epsilon)$ の割合を除いたすべての状態に対して $\epsilon$ で抑えられる。
• 楽観的乗算と素因数分解: 著者らは、楽観的QFTをショアのアルゴリズムに直接利用できることを示しています。楽観的QFTを最近のQFTベースの高速算術構成（具体的には楽観的乗算器）に統合することで、合計 $2n + O(n/\log n)$ 個の量子ビットを用いて、素因数分解回路の深さを $O(n^{1+\delta})$ （調整可能な $\delta > 0$）で実現します。これは、$O(n)$ 個の補助量子ビットやより深い回路を必要とした従来の手法と比較して、深さと量子ビット効率の両面で大幅な改善となります。
• 一般的な近似QFT: 簡約化技術を適用することで、任意の入力に対して低誤差で動作する近似QFTを導出しています。
  • ランダム化バージョン: 合計 $n + O(n/\log(n/\epsilon))$ 個の量子ビットを用いて、深さ $O(\log(n/\epsilon))$ を達成。
  • 決定論的（ユニタリ）バージョン: 合計 $3n + O(n/\log(n/\epsilon))$ 個の量子ビットを用いて、深さ $O(\log(n/\epsilon))$ を達成。
    これらは、漸近的に最適な対数深さを、劣線形な補助量子ビット数（ランダム化版）または測定/フィードフォワードなし（決定論版）で達成する最初の構成であると主張されています。

意義
本論文は、「楽観的量子回路」が量子アルゴリズム設計における実用的なパラダイムシフトを提供すると主張しています。典型的なアルゴリズム的文脈（ショアのアルゴリズムなど）において統計的に起こりにくい失敗モードを受け入れることで、リソースのオーバーヘッド（深さと補助量子ビット数）を劇的に削減できます。具体的な楽観的QFTの構成は、素因数分解回路におけるQFTのボトルネックを取り除き、最小限の量子ビットオーバーヘッドで、ほぼ線形深さの素因数分解を可能にします。さらに、提供された簡約化技術は、このような楽観的回路を、必要に応じて堅牢な最悪ケースの保証へと変換するための一般的な手法を提供し、ヒューリスティックな効率性と厳密な正当性の間の溝を埋めるものです。この研究は、量子ハードウェアが成熟するにつれ、時空ボリュームと深さのトレードオフが極めて重要になることを示唆しており、これらの構成はその両方を最適化するための経路を提供しています。