量子フーリエ変換 — 知識ノート

離散フーリエ変換の量子版。

| j ⟩ ⟼ \frac{1}{\sqrt{N}} \sum_{k = 0}^{N - 1} e^{2 π i j k / N} | k ⟩

速いが、読み出せない#

	古典 FFT	QFT
計算量	$𝒪 (N \log N)$	$𝒪 ({(\log N)}^{2})$
出力	$N$ 個の係数すべて	測定して 1 つのサンプル

指数的に速いが、結果を全部取り出せない。 $N = 2^{n}$ 個の係数が振幅として存在するが、測定で得られるのは 1 つのビット列だけ。

このため QFT 単体では役に立たず、 周期性のような大域的な性質を抽出する用途に限って威力を発揮する。 Shor がその代表例。

「量子フーリエ変換で信号処理が速くなる」は誤解で、入力の準備と出力の読み出しがボトルネックになる。

アダマールと制御位相回転ゲートで構成され、 $𝒪 (n^{2})$ ゲートで実装できる。

小さい位相回転を省く近似 QFT でも実用上十分な精度が得られ、ゲート数を $𝒪 (n \log n)$ に減らせる。ノイズのある実機では、むしろ近似版の方が精度が良いこともある。

Michael A. Nielsen, Isaac L. Chuang. Quantum Computation and Quantum Information, 10th Anniversary Edition. Cambridge University Press, 2010. https://doi.org/10.1017/CBO9780511976667
Ashley Montanaro. Quantum algorithms: an overview. npj Quantum Information 2, 2016. https://doi.org/10.1038/npjqi.2015.23