QFT の回路と数え方

相対エントロピーから情報と物理を組み立てる　第6部 第2章 §6.2.2　★★ Hadamard と制御位相回転 $n(n+1)/2$ 個で QFT が組めること・小さな回転を落とした近似 QFT の誤差

回路

積の形 (6.2.2) を作るには、各量子ビットに $| 0 \rangle +\mathrm{e}^{2\pi\mathrm{i}\,0.j_l\cdots j_n}| 1 \rangle$ の位相を書き込めばよい。使うゲートは Hadamard と、角度 $2\pi/2^k$ の位相回転

$$R_k=\begin{pmatrix}1&0\\0&\mathrm{e}^{2\pi\mathrm{i}/2^k}\end{pmatrix}\tag{6.2.4}$$

を別の量子ビットで制御したもの（制御 $R_k$）である。制御 $R_k$ は $| 11 \rangle$ にだけ位相 $\mathrm{e}^{2\pi\mathrm{i}/2^k}$ を掛ける対角行列なので、制御側と標的側を入れ替えても同じ演算子になる。

1番上の量子ビット $| j_1 \rangle$ に $H$ を当てると $(| 0 \rangle +\mathrm{e}^{2\pi\mathrm{i}\,0.j_1}| 1 \rangle )/\sqrt2$ になる（$(-1)^{j_1}=\mathrm{e}^{2\pi\mathrm{i}\,0.j_1}$）。続けて $j_2$ で制御した $R_2$ を当てると、$j_2=1$ のときだけ $| 1 \rangle$ の成分に $\mathrm{e}^{2\pi\mathrm{i}/4}$ が掛かり、位相は $2\pi\times0.j_1j_2$ になる。同様に $R_3,\dots,R_n$ を $j_3,\dots,j_n$ で制御して当てれば、1番上の量子ビットは $(| 0 \rangle +\mathrm{e}^{2\pi\mathrm{i}\,0.j_1\cdots j_n}| 1 \rangle )/\sqrt2$ になる。2番目の量子ビットには $H$ と制御 $R_2,\dots,R_{n-1}$ を当てて $0.j_2\cdots j_n$ を書き込み、以下同様に進む。この間、まだ処理していない下の量子ビットは制御側にしか使っていないので、$j_l$ の値は書き込みの最中に失われない。最後に、出来上がった並びが式 (6.2.2) と上下逆なので、SWAP ゲートで上下を入れ替える（図 6.2.1）。

図 6.2.1　3量子ビットの QFT の回路（右端の出力は規格化の $1/\sqrt2$ を省いた）。黒丸は制御で、制御 $R_k$ は対角なので制御と標的を区別しなくてよい。右端の SWAP で上下を入れ替えて式 (6.2.2) の並びにする。

$N=2^n$ 次元のベクトルに行列を掛ける古典の計算は、高速 Fourier 変換（FFT）を使っても $\mathcal{O}(N\log N)=\mathcal{O}(n2^n)$ 回の演算が要る。QFT はそれを $\mathcal{O}(n^2)$ 個のゲートで済ませるので指数関数的に速く見えるが、比べ方に注意が要る。FFT は $N$ 個の Fourier 係数をすべて出力するのに対し、QFT の出力は量子状態で、測れば $N$ 個の振幅の2乗に従う乱数が1つ出るだけである。QFT が役に立つのは、出力の分布が少数の値に集中するように入力を用意できる場合、すなわち位相推定と周期発見に限られる。

近似 QFT

$R_k$ の回転角 $2\pi/2^k$ は $k$ とともに指数関数的に小さくなる。$k$ が大きい制御 $R_k$ は恒等演算子にほとんど等しいので、$k>m$ のものを落としてよいと考えられる（Coppersmith の近似 QFT¹1D. Coppersmith (1994), “An approximate Fourier transform useful in quantum factoring,” IBM Research Report RC19642（arXiv:quant-ph/0201067 として再録）。下の脚注へ閉じる）。落とした誤差は次のように押さえられる。

残るゲートの数は約 $nm$ 個で、$m$ は $\log_2(n/\varepsilon )$ 程度でよいので、近似 QFT は $\mathcal{O}(n\log n)$ 個のゲートで済む。実際の量子計算機では、回転角が非常に小さいゲートは雑音より小さくなって意味を失うので、落とす方が正確になることもある。