技術要約：乗算に基づく改良された厳密および近似量子フーリエ変換

問題提起

量子フーリエ変換（QFT）は、ショアの素因数分解アルゴリズムや量子位相推定などの量子アルゴリズムにおいて、最も重要なサブルーチンである。$F_{2^q}$ 上の標準的な回路実装には $O(q^2)$ のゲートが必要である。Cleve と Watrous (2000) は、整数乗算アルゴリズムを活用することで、厳密な QFT のゲート数を $O(q(\log q)^2 \log \log q)$ に削減したが、Ahokas, Cleve, and Hales (2003) は近似 QFT に対してさらなる最適化を提供した。著者らは、整数乗算の計算量と、その結果得られる QFT 回路の計算量の間にギャップが存在することを指摘している。

具体的には、$n$ ビットの整数の乗算が $M(n) = O(n(\log n)^\alpha)$ 個のゲートで実行できる場合、Cleve-Watrous の構成法は $O(q(\log q)^{\alpha+1})$ 個のゲートを持つ厳密な QFT を提供する。本論文は、このオーバーヘッドを軽減し、整数乗算の計算量により近づけること（すなわち、$O(q(\log q)^\alpha)$ を達成すること）を目的として、厳密および近似の両方の QFT に関する問いに取り組んでいる。

手法

著者らは、QFT 構成のゲート計算量を改善するために、二段構えのアプローチを提案している。

1. 厳密な QFT 構成

著者らは、Mosca と Zalka (2003) の「厳密化（exactification）」手法と、Cleve と Watrous (2000) の乗算ベースの実装を組み合わせている。

• 振幅増幅（Amplitude Amplification）: 近似 QFT 回路（成功確率 $p \geq 3/4$）を厳密なものに変換する手法を利用する。これには以下が含まれる：
  1. フーリエ状態のコピー: Cleve-Watros のコピー回路を用いてフーリエ状態を複製し、元の状態を検証用に保存できるようにする。
  2. 確率の調整: 補助量子ビットを導入し、正しい答えと補助量子ビットの状態の結合成功確率を正確に $1/4$ に調整するための特定の単一量子ビット回転 $B(\theta_q)$ を適用する。
  3. グローバー反復（Grover Iteration）: 成功確率を 1 に高めるために、単一ステップの振幅増幅（グローバー・イテレート）を適用する。
• ゲートセット: 標準的なゲート（アダマール、CNOT、位相ゲート）に加えて、 $q$ に依存する角度を持つ特定の単一量子ビット回転 $B(\theta_q)$ を使用する。この非標準的なゲートは、増幅ステップのための初期振幅を設定するために必要である。

2. 近似 QFT 構成

近似 QFT に対しては、Ahokas, Cleve, and Hales (ACH) の再帰的構成を適応させている。

• 再帰的分割: 入力レジスタを、上部と下部の半分に再帰的に分割する。構成では、上部レジスタに対して再帰的な QFT を適用し、レジスタ間で「積位相（product-phase）」操作を行い、下部レジスタに対して再帰的な QFT を適用した後、レジスタを入れ替える。
• 切り捨て（Truncation）: 積位相操作において、入力の最も重要な $\Theta(\log(q/\varepsilon))$ ビットのみが使用される（ここで $\varepsilon$ は近似誤差である）。
• ベースケース: 再帰は、レジスタサイズが最大 $2k$ になるまで続く。これらのベースケースにおいて、標準的な Cleve-Watrous の厳密 QFT（コスト $O(k(\log k)^{\alpha+1})$）を使用する代わりに、改良された厳密 QFT（コスト $O(k(\log k)^\alpha)$）を代用する。
• 回転の近似: 改良された厳密 QFT は非標準的な回転 $B(\theta_q)$ に依存しているため、著者らは、これらの回転が漸近的なゲート数や補助空間を増やすことなく、標準的な位相ゲート $P(2\pi a/2^d)$ を用いて効率的に近似できることを示している。したがって、$\varepsilon$-近似 QFT のための最終的な構成は、Cleve および Watrous と同じゲートセット（アダマール、制御NOT、および厳密な位相ゲート）を使用する。

主な貢献と結果

1. 改善されたゲート計算量

主要な貢献は、厳密および近似 QFT の両方における漸近的なゲート数の削減であり、これらを整数乗算 $M(n) = O(n(\log n)^\alpha)$ の計算量に直接結びつけている。

• 厳密 QFT (Theorem 1.1): 著者らは、$q$ 量子ビットに対する厳密な QFT を $O(q(\log q)^\alpha)$ 個のゲートを用いて構築する。これは、Cleve と Watrous による従来の最良の境界 $O(q(\log q)^{\alpha+1})$ を改善するものである。
  • 注: この構成には、$q$ に依存する追加の単一量子ビット回転 $B(\theta_q)$ が必要である。
• 近似 QFT (Theorem 1.2): 近似誤差 $\varepsilon$ に対して、著者らは $O(q(\log \log(q/\varepsilon))^\alpha)$ 個のゲートを用いた回路を構築する。これは、Ahokas, Cleve, and Hales による従来の境界 $O(q(\log \log(q/\varepsilon))^{\alpha+1})$ を改善するものである。
  • 注: この構成は、必要な回転を近似することにより、Cleve および Watrous と同じゲートセット（アダマール、制御NOT、および厳密な位相ゲート）を使用する。

2. 最近の乗算に関する主張の影響

本論文は、整数乗算の計算量が $O(n(\log n)^{1-\kappa})$ （ただし定数 $0 < \kappa < 1$）であるという OpenAI の最近の主張の潜在的な影響を強調している。

• もしこの主張がブール回路に対して成立する場合、$\alpha = 1-\kappa$ と設定することで、厳密な QFT は $o(q \log q)$ 個のゲート、近似 QFT は $o(q \log \log q)$ 個のゲートで実現できる。
• これは、このような乗算の進展なしには達成不可能と考えられていた $O(q^2)$ や $O(q \log q)$ よりも大幅に効率的な QFT 回路への道を示唆している。

3. リソース境界

• 補助量子ビット: 厳密な構成は $O(a(q) + M(q))$ 個の補助量子ビットを使用する（ここで $a(q)$ は近似回路の補助量子ビット数である）。近似構成は $O(L(\log L)^\alpha)$ 個の補助量子ビットを使用する。ここで $L = \log(q/\varepsilon)$ である。
• 一様性（Uniformity）: 著者らは、自身の回路ファミリーが 非一様（non-uniform） であることを明示している。これは、回転角 $\theta_q$ が現在の知識では古典的アルゴリズムによって効率的に計算できないためである。彼らは、これらの角度の効率的な生成が自然な未解決問題であることを特定している。

意義と主張

本論文は、整数乗算のコストと量子フーリエ変換のコストとの間の理論的なつながりを強化することを主張している。ゲート計算量における余分な対数因子を取り除くことで、著者らは QFT を基礎となる乗算アルゴリズムと同じくらい効率的にできることを示しており、QFT は基礎となる乗算の計算量にほぼ一致させることができる。

著者らは、回転角への依存性が現在の知識では回路の非一様性を妨げていることを認めつつ、自身の回路の性質について控えめな姿勢をとっている。また、Aaronson (2025) が提起した「$q$ 量子ビットに対する厳密な QFT を $O(q)$ 個のゲートで実装できるか」という未解決問題についても言及し、彼らの結果は指数を改善するものの、まだ線形サイズには達していないことを述べている。

本研究は、新しい実験的実装や、ショアのアルゴリズムや位相推定のような一般的な用途を超えた具体的な応用を提案するものではない。むしろ、量子ゲートのオーバーヘッドを削減するために、最近の古典的な整数乗算の進展を活用した、より洗練された理論的な回路計算量の境界に焦点を当てている。