出典検証済みレベル 3
量子フーリエ変換
量子フーリエ変換（QFT）は離散フーリエ変換の量子アナログで、O(n²)ゲートで計算基底を周波数基底に変換します。
どういう意味か
QFTは計算基底状態を周波数成分を位相エンコードした重ね合わせにマッピングします。古典FFTのO(n·2^n)に対しO(n²)ゲート。ショアのアルゴリズムと量子位相推定の主要サブルーチンです。日常のたとえ
和音を個々の音に変換するようなもの。
白色光を虹に分けるプリズム。
よくある誤解
- QFTの高速化は直接信号処理には使えません。
- QFT回路は古典FFTアルゴリズムとは異なります。
要点
- O(n²)ゲートで変換。
- 古典FFTより指数的に少ないゲート。
- ショアと位相推定の主要サブルーチン。
理解度チェック
n量子ビットのQFTに必要なゲート数は？
- A.O(n)
- B.O(n²)
- C.O(2^n)
- D.O(n·2^n)
答えを見る
答え: B. O(n²)
理由: O(n²)ゲートです。
前提となる概念
一次資料: Shor, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM J. Comput. 26, 1484 (1997), doi:10.1137/S0097539795293172
Circuit form per Coppersmith (1994), arXiv:quant-ph/0201067.