量子フーリエ変換と位相推定

量子情報入門　第1章 §1.5

この章は本書の山場である。Shorのアルゴリズム(第1.6節)の量子的核心はすべてこの章に置かれており、逆にいえばこの章を理解すれば「量子計算はどこで古典を追い抜くのか」という問いに具体的な形で答えられるようになる。構成は、(i) 古典の離散フーリエ変換の確認、(ii) 量子フーリエ変換(QFT)の定義と基本性質、(iii) 積表示の完全な導出と回路構成、(iv) QFTが周期構造をどう「見る」か、(v) 位相推定アルゴリズムの厳密な解析、の順に一歩ずつ積み上げる。

離散フーリエ変換とは

まず「離散フーリエ変換」がフーリエ変換・フーリエ級数とどう違うかを整理する。

• フーリエ変換(連続・非周期):$\mathbb R$ 上の関数 $f$ に対して $\hat f(k)=\int_{-\infty}^{\infty} f(x)e^{-2\pi ikx}dx$。
• フーリエ級数(連続・周期):周期 $T$ の関数を $c_n = \frac{1}{T}\int_0^T f(x)e^{-2\pi inx/T}dx$ で分解。
• 離散フーリエ変換 (DFT)(離散・有限):$\mathbb Z/N\mathbb Z$ 上の関数、すなわち $N$ 個の値 $f(0),\ldots,f(N-1)$ に対して

$$\tilde f(k) = \frac{1}{\sqrt N}\sum_{j=0}^{N-1} f(j)\, e^{-2\pi i jk/N},\qquad k=0,1,\ldots,N-1.$$

DFTは実質的に「フーリエ級数を有限個のサンプル値で計算するもの」で、有限アーベル群 $\mathbb Z/N\mathbb Z$ 上のフーリエ変換とみなせる。連続の積分の代わりに有限和になっているだけである。

DFTの構造を支えるのは1の原始 $N$ 乗根 $\omega\equiv e^{2\pi i/N}$ である。$\omega^N=1$ であり、複素平面の単位円を $N$ 等分した点 $1,\omega,\omega^2,\ldots,\omega^{N-1}$ が「離散的な回転」の全てを与える。基本となるのは直交関係

$$\frac1N\sum_{j=0}^{N-1}\omega^{j(k-k')} = \delta_{kk'}\pmod N\tag{1.2}$$

である。$k=k'$ なら各項が $1$ で和は $N$。$k\neq k'$ なら公比 $q\equiv\omega^{k-k'}\neq1$ の等比数列の和で、$\sum_j q^j=(q^N-1)/(q-1)=0$($q^N=\omega^{N(k-k')}=1$ による)。「単位円上に等間隔に並んだベクトルを全部足すとゼロ」という幾何学的事実である。この一つの恒等式が、以下のQFTのユニタリ性・周期検出・位相推定の成功確率のすべてを支配する。

素朴に計算すれば $O(N^2)$ だが、古典的な高速フーリエ変換 (FFT) は $O(N\log N)$ でこれを実現する。デジタル信号処理・数値計算・多項式乗算などで極めて広く使われている。

量子フーリエ変換(QFT):定義と基本性質

$N=2^n$ とする。$n$ 量子ビットの状態空間 $\mathbb C^N$ を「$\mathbb Z/N\mathbb Z$ 上の関数の空間」と見なすと、状態 $\ket\psi = \sum_j f(j)\ket j$ の振幅 $f$ に DFT を作用させるユニタリが定義できる。これが量子フーリエ変換(QFT)である:

$$\mathrm{QFT}_N\ket j = \frac{1}{\sqrt N}\sum_{k=0}^{N-1} e^{2\pi i jk/N}\ket k = \frac{1}{\sqrt N}\sum_{k=0}^{N-1}\omega^{jk}\ket k.\tag{1.3}$$

すなわち、計算基底 $\ket j$ を、位相が $j$ に応じて回転する重ね合わせ状態に写す線形写像である。行列成分では $(\mathrm{QFT})_{kj}=\omega^{jk}/\sqrt N$。

ユニタリ性

QFTが本当にユニタリであることは直交関係(1.2)から直ちに従う:

$$(\mathrm{QFT}^\dagger\,\mathrm{QFT})_{jj'} = \frac1N\sum_k \omega^{-kj}\omega^{kj'} = \frac1N\sum_k\omega^{k(j'-j)} = \delta_{jj'}.$$

逆変換は $\omega\to\omega^{-1}$ と置き換えるだけ:$\mathrm{QFT}^\dagger\ket k=\frac1{\sqrt N}\sum_j\omega^{-jk}\ket j$。

最小の例:$n=1$ はHadamardそのもの

$N=2$, $\omega=e^{\pi i}=-1$ を定義に入れると

$$\mathrm{QFT}_2 = \frac{1}{\sqrt2}\begin{pmatrix}1&1\\1&-1\end{pmatrix} = H.$$

Hadamardゲートは1量子ビットのQFTである。第1.6節のDeutsch–Jozsaで全ビットにHadamardをかける操作は、群 $(\mathbb Z/2\mathbb Z)^n$ 上のフーリエ変換とみなせる——QFTの「親戚」が既にあちこちに登場していたのである。

$n=2$ の例

$N=4$, $\omega=i$ で

$$\mathrm{QFT}_4 = \frac12\begin{pmatrix} 1&1&1&1\\ 1&i&-1&-i\\ 1&-1&1&-1\\ 1&-i&-1&i \end{pmatrix}$$

(数値的にユニタリ性を確認済み)。列を眺めると、第 $j$ 列は「角速度 $j$ で単位円を回る点列」であり、$j$ が大きいほど位相が速く回る。QFTとは「位置の基底」から「回転速度の基底」への基底変換である——この見方が次小節以降のすべての直観の源になる。

注意:振幅は直接読めない

QFTは重ね合わせ状態を重ね合わせ状態に写すユニタリであり、振幅そのものを取り出すことはできない(測定すれば1つの $k$ が確率的に得られるだけ)。この意味で、QFTを「古典FFTの高速版」として信号処理に流用することはできない。QFTが強力なのは、出力分布が少数の $k$ に鋭く集中するように仕組まれた問題——周期発見や位相推定のような構造を持った問題——に対してである。本章の残りは、この集中がいつどのように起こるかの解析だと言ってよい。

積表示(テンソル積分解)の完全な導出

QFTの最大の利点は、これが $O(n^2)$ 個のゲートで実装できることである。その鍵が、出力状態がもつれのない積状態に分解できるという事実(積表示)である。ここはShor理解の急所なので、導出を省略せずに実行する。

$j$ の2進表現を $j=j_1j_2\cdots j_n$($j_1$ が最上位ビット)、すなわち $j=\sum_{m=1}^n j_m 2^{n-m}$ とし、2進小数の記法

$$0.j_lj_{l+1}\cdots j_n \equiv \frac{j_l}{2}+\frac{j_{l+1}}{4}+\cdots+\frac{j_n}{2^{n-l+1}}$$

を用いる。

ステップ1:$k$ をビットごとに分解する。出力の和の変数 $k$ も2進展開 $k=\sum_{l=1}^n k_l2^{n-l}$($k_l\in\{0,1\}$)し、(1.3)の指数を書き換える:

$$e^{2\pi ijk/2^n} = \exp\!\Bigl(2\pi ij\sum_{l=1}^nk_l2^{-l}\Bigr) = \prod_{l=1}^n e^{2\pi ijk_l2^{-l}}.$$

和 $\sum_{k=0}^{N-1}$ は $\sum_{k_1}\cdots\sum_{k_n}$ とビットごとの独立な和に分かれるので、

$$\mathrm{QFT}\ket j = \frac{1}{2^{n/2}}\sum_{k_1=0}^{1}\cdots\sum_{k_n=0}^{1}\ \prod_{l=1}^n e^{2\pi ijk_l2^{-l}}\ \ket{k_1\cdots k_n} = \frac{1}{2^{n/2}}\bigotimes_{l=1}^n\Bigl(\ket0 + e^{2\pi ij2^{-l}}\ket1\Bigr).$$

最後の等号では、各ビットの和が独立な2項和なので全体がテンソル積に因子化することを使った。もつれた入力ではないから当然と思うかもしれないが、$\ket j$ は積状態でも、その像が計算基底の一様重ね合わせにビットごとの位相を付けただけの積状態になるのは、指数関数が和を積に変えるという性質の賜物である。

ステップ2:位相を2進小数に読み替える。$j2^{-l} = j_1j_2\cdots j_{n-l}.j_{n-l+1}\cdots j_n$(小数点が $l$ 桁分左に移動)であり、$e^{2\pi i(\text{整数})}=1$ だから整数部分は捨ててよい:

$$e^{2\pi ij2^{-l}} = e^{2\pi i\,0.j_{n-l+1}j_{n-l+2}\cdots j_n}.$$

これを代入して積表示が完成する:

$$\boxed{\ \mathrm{QFT}\ket{j_1\cdots j_n} = \frac{1}{2^{n/2}} \Bigl(\ket0+e^{2\pi i\,0.j_n}\ket1\Bigr)\otimes \Bigl(\ket0+e^{2\pi i\,0.j_{n-1}j_n}\ket1\Bigr)\otimes\cdots\otimes \Bigl(\ket0+e^{2\pi i\,0.j_1j_2\cdots j_n}\ket1\Bigr)\ }\tag{1.4}$$

($n=3$, $j=5$ で右辺と定義(1.3)の直接計算が一致することを数値確認済み)。

各出力ビットの状態 $(\ket0+e^{2\pi i\theta}\ket1)/\sqrt2$ はBloch球の赤道上の点(経度 $2\pi\theta$)である。積表示は「$n$ 桁の2進小数 $0.j_1\cdots j_n$ を、精度の異なる $n$ 本の時計の針(赤道上の量子ビット)に分配して記録した状態」と読める:第1出力ビットの針は $j_n$ しか区別しない粗い針、最終ビットの針は全桁を反映する最も精密な針である。位相推定(第1.5.6節)はこの針たちを逆向きに読む操作にほかならない。

回路の構成

積表示(1.4)を実現する回路を組む。部品はHadamardと制御位相ゲート

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

の2種類だけである($R_1=Z$, $R_2=S$, $R_3=T$ と、第1.1章のゲートが揃って再登場する)。

$n=3$ での逐語的な追跡

入力 $\ket{j_1j_2j_3}$ に対し、次の手順を実行する。

(1) 第1ビットに $H$:

$$\ket{j_1}\to\frac{\ket0+e^{2\pi i\,0.j_1}\ket1}{\sqrt2}$$

($e^{2\pi i\,0.j_1}=(-1)^{j_1}$ だからこれは単なる $H$ の作用の書き換えである)。

(2) 第2ビットを制御に、第1ビットへ制御 $R_2$:$j_2=1$ のときだけ位相 $e^{2\pi i/4}$ が加わり

$$\frac{\ket0+e^{2\pi i\,0.j_1j_2}\ket1}{\sqrt2}.$$

2進小数の第2桁が書き込まれた。

(3) 第3ビットを制御に、第1ビットへ制御 $R_3$:同様に

$$\frac{\ket0+e^{2\pi i\,0.j_1j_2j_3}\ket1}{\sqrt2}.$$

第1ビットの針が最精密の値を指した。

(4)(5) 第2ビットに $H$、制御 $R_2$($j_3$ 制御):$\bigl(\ket0+e^{2\pi i\,0.j_2j_3}\ket1\bigr)/\sqrt2$。

(6) 第3ビットに $H$:$\bigl(\ket0+e^{2\pi i\,0.j_3}\ket1\bigr)/\sqrt2$。

(7) SWAP:第1・第3ビットを交換。これで各ビットの位相が $(0.j_3,\ 0.j_2j_3,\ 0.j_1j_2j_3)$ の順になり、式(1.4)と一致する。

以上を回路図にまとめると次のようになる(時間は左から右へ流れる;$\bullet$ は制御、箱は標的への作用)。

回路のパターンを掴んでほしい:各ビットに「$H$ の後、自分より下位のすべてのビットから制御位相を受け取る」を上から順に繰り返すだけである。下位ビットほど細かい桁($R_k$ の $k$ が大きい=角度が小さい)を担い、SWAPが最後に重みの逆転を直す。一般の $n$ でも構造は同一で、$l$ 番目のビットの処理は「$H$、続いて制御 $R_2,\ldots,R_{n-l+1}$」となる。

ここでも位相キックバック

手順(2)で「制御 $R_2$ が標的である第1ビットの位相を書き換える」と述べたが、$R_k$ は対角行列なので、制御位相ゲートは制御と標的の区別がない対称なゲートである(行列を両方の向きで書いて同一になることを確認できる;第1.5.6節末のkeyboxで論じた「位相の帰属の不定性」の演算版そのものである)。「$j_2$ の値が第1ビットの位相に転写される」という読み方は、まさに位相キックバックであり、QFT回路とはキックバックを $n(n-1)/2$ 回組織的に行って2進小数を組み立てる機械だと総括できる。

ゲート数

第 $l$ ビットには $H$ が1個と制御 $R_k$ が $n-l$ 個かかるので、合計

$$\sum_{l=1}^n\bigl(1+(n-l)\bigr) = \frac{n(n+1)}2 = O(n^2)$$

個、末尾のSWAPが $\lfloor n/2\rfloor$ 個(SWAP 1個はCNOT 3個で組める)。古典FFTの $O(N\log N)=O(2^n\cdot n)$ に対し、QFTは $O(n^2)$——指数的に少ない。ただし前小節の注意のとおり、この差がそのまま計算の高速化になるのは出力を賢く使える問題に限られる。

QFTは何を「見る」のか:周期状態とピーク

Shorへの橋として、周期的な重ね合わせにQFTをかけると何が起こるかを見る。周期 $r$ が $N$ を割り切る簡単な場合($N=rM$)を考え、オフセット $x_0$ から $r$ おきに立った一様重ね合わせ

$$\ket\psi = \frac{1}{\sqrt M}\sum_{m=0}^{M-1}\ket{x_0+mr}$$

にQFTを作用させる:

$$\mathrm{QFT}\ket\psi = \frac{1}{\sqrt{NM}}\sum_{k=0}^{N-1}\ \underbrace{e^{2\pi ix_0k/N}}_{\text{オフセット位相}}\ \underbrace{\sum_{m=0}^{M-1}e^{2\pi imrk/N}}_{\text{干渉因子}}\ \ket k.$$

干渉因子は公比 $e^{2\pi irk/N}$ の等比数列の和で、直交関係(1.2)とまったく同じ機構により

$$\sum_{m=0}^{M-1}e^{2\pi imrk/N} = \begin{cases} M & (rk/N\in\mathbb Z\ \text{すなわち}\ k=0,\tfrac Nr,\tfrac{2N}r,\ldots)\\ 0 & (\text{それ以外})\end{cases}$$

となる。すなわち測定で得られる $k$ は$N/r$ の倍数に限られ、それぞれ等確率 $1/r$ で出る($N=8$, $r=4$ で出力分布が $k=0,2,4,6$ に各 $1/4$ となることを数値確認済み)。オフセット $x_0$ は位相因子にしか現れず、確率分布に影響しない——周期だけが抽出され、位置情報は消える。これは古典フーリエ解析の「シフトは位相にしか効かない」の量子版である。

位相推定アルゴリズム

QFTの最も重要な応用が位相推定(Quantum Phase Estimation, QPE)である。設定は次の通り:

• ユニタリ $U$ の固有ベクトル $\ket u$ が与えられている(用意できる)
• その固有値 $e^{2\pi i\varphi}$ の位相 $\varphi\in[0,1)$ を精度良く求めたい

直観:「時計の針を読む」

固有値 $e^{2\pi i\varphi}$ の位相 $\varphi$ を「時計の針の角度 $/2\pi$」と思うと、位相推定は「未知の時計の針の位置を、多数の観察を組み合わせて2進小数で読み取る」アルゴリズムだと思える。1回だけ $U$ を作用させて針の位置を測ってもノイズだらけの1ビットしか取れないが、$U^2, U^4, U^8, \ldots$ と作用させると針は2倍速・4倍速・8倍速で回転し、それぞれから $\varphi$ の異なるビットが取り出せる。これらを QFT で「ビット列」に整えて読むのが位相推定である。

位相キックバックの直観

制御ユニタリ $\Lambda(U)$ を、制御ビット $\ket 1$ と標的 $\ket u$(固有ベクトル)に作用させると

$$\ket 1\otimes \ket u \to \ket 1\otimes U\ket u = e^{2\pi i\varphi}\,\ket 1\otimes \ket u.$$

位相 $e^{2\pi i\varphi}$ は代数的にはどちらの因子に付いてもよいが、慣習的に制御ビットの $\ket 1$ の係数として現れると見なす。すなわち制御ビットを $(\ket 0+\ket 1)/\sqrt2$ にしておけば

$$\left(\ket 0 + \ket 1\right)\otimes\ket u \to \left(\ket 0 + e^{2\pi i\varphi}\ket 1\right)\otimes\ket u.$$

未知の位相が制御ビットに「転写」される。これが位相キックバックである。$U^{2^k}$ を制御すれば係数は $e^{2\pi i\, 2^k\varphi}$ となり、$\varphi$ の2進展開の第 $k$ ビットに対応する情報が制御ビットに載る。

アルゴリズムの全経過

$t$ 量子ビットの補助レジスタ(精度を決める)と固有ベクトル $\ket u$ を用意する。$M\equiv 2^t$ とおく。

(1) 一様重ね合わせの準備:補助レジスタ $\ket0^{\otimes t}$ に $H^{\otimes t}$ を作用させ

$$\frac{1}{\sqrt M}\sum_{j=0}^{M-1}\ket j\ \otimes\ \ket u.$$

(2) 制御 $U^{2^k}$ の適用:補助の第 $k$ ビット($k=0,\ldots,t-1$、最下位から)を制御として $U^{2^k}$ を作用させる。$\ket j$ の2進展開 $j=\sum_kj_k2^k$ に対し、作用する $U$ の総回数は $\sum_kj_k2^k=j$ 回。キックバックにより

$$\frac{1}{\sqrt M}\sum_{j=0}^{M-1}e^{2\pi ij\varphi}\ket j\ \otimes\ \ket u.\tag{1.5}$$

$\ket u$ は一度も変化していないことに注意——固有ベクトルだから位相しか出さず、その位相はすべて補助レジスタに蓄積された。

(3) 逆QFTと測定:補助レジスタに $\mathrm{QFT}^\dagger$ を作用させ、計算基底で測定する。

全体の回路は次の形になる($t=3$ の場合)。

下段のレジスタ($\ket u$)は最後まで変化せず、情報の流れはすべて「制御 $U^{2^k}$ による位相キックバック $\to$ 補助レジスタ」の向きであることが図から読み取れる。補助レジスタに蓄積した状態(1.5)は、$\varphi$ が $t$ ビットで書けるとき「$\mathrm{QFT}\ket{2^t\varphi}$」の形をしているので、$\mathrm{QFT}^\dagger$ がそれを計算基底へ巻き戻す——QFT回路(前小節)が2進小数を位相に「書き込む」機械なら、QPEはその逆再生で位相から2進小数を「読み出す」機械である。この対称性が見えると、両者は一つのアルゴリズムの表裏であることが分かる。

厳密なケース

$\varphi$ がちょうど $t$ ビットで表せる場合、すなわち $\varphi=a/M$($a\in\{0,\ldots,M-1\}$)なら、式(1.5)の補助レジスタは

$$\frac{1}{\sqrt M}\sum_je^{2\pi ija/M}\ket j = \mathrm{QFT}\ket a$$

そのものである。よって $\mathrm{QFT}^\dagger$ で確定的に $\ket a$ に戻り、測定結果 $a$ から $\varphi=a/M$ が確率1で読み出せる。

例題:$U=T$ ゲートの位相推定

$T=\mathrm{diag}(1,e^{i\pi/4})$ の固有ベクトル $\ket1$ の固有値は $e^{2\pi i\cdot 1/8}$、すなわち $\varphi=1/8=0.001_{(2)}$。$t=3$ ビットの補助レジスタで上のアルゴリズムを走らせると、$\varphi\cdot2^3=1$ が整数なので厳密なケースに該当し、測定結果は確定的に $m=1$ となる(状態ベクトルシミュレーションで $P(m{=}1)=1.000000$ を確認済み)。針の速度が $1,2,4$ 倍と上がるにつれ位相は $\tfrac18,\tfrac14,\tfrac12$ 回転——3本の針がそれぞれ2進小数の1桁ずつを担っているのが直接見える。

位相が正確に表せない場合の解析

一般には $\varphi$ は無理数でもよく、$t$ ビットで表しきれない。このときの成功確率を定量化する。$b$ を $M\varphi$ に最も近い整数とし、ずれを $\delta\equiv\varphi-b/M$($|\delta|\le1/2M$)とおく。逆QFT後に結果 $m$ を得る振幅は

$$c_m = \frac1M\sum_{j=0}^{M-1}e^{2\pi ij(\varphi-m/M)} = \frac1M\cdot\frac{1-e^{2\pi iM\varphi-2\pi im}}{1-e^{2\pi i(\varphi-m/M)}}$$

(等比数列の和;分布のピーク構造は第1.5.5節の干渉因子と同型である)。最良の候補 $m=b$ について、$|1-e^{i\theta}|=2|\sin(\theta/2)|$ と不等式 $\frac{2}{\pi}|x|\le|\sin x|\le|x|$($|x|\le\pi/2$)を使うと

$$|c_b| = \frac1M\,\frac{|\sin(\pi M\delta)|}{|\sin(\pi\delta)|} \ \ge\ \frac1M\cdot\frac{2M|\delta|\cdot 2/\pi\cdot\pi}{2\pi|\delta|\cdot\tfrac12}\cdot\frac12 \quad\Longrightarrow\quad P(m=b)=|c_b|^2\ \ge\ \frac{4}{\pi^2}\approx 0.405.$$

すなわち最良の $t$ ビット近似が常に $40\%$ 以上の確率で得られる(たとえば $\varphi=0.2$, $t=3$ の数値実験では $P(m{=}b)=0.578$、両隣を含めれば $0.837$)。定数確率で成功するなら、数回繰り返して多数決を取れば失敗確率は指数的に落ちる——BQPの定義(第1.7節)で $2/3$ という定数が本質的でなかったのと同じ理屈である。

さらに「小数点以下 $n$ ビットの精度で、失敗確率 $\varepsilon$ 以下」を保証したければ、補助レジスタを

$$t = n + \left\lceil\log_2\Bigl(2+\frac{1}{2\varepsilon}\Bigr)\right\rceil$$

ビットに取ればよいことが、裾の確率 $\sum_{|m-b|>e}|c_m|^2$ を上と同様の等比和評価で押さえることで示せる(N&C, §5.2.1)。目安として数ビット余分に持つだけで裾が急速に潰れる:$\varphi=0.2$ を $n=3$ ビット精度で求める場合、$t=5$($2$ ビット追加)で成功確率は既に $0.957$ に達する(数値確認済み)。精度は $t$ に対して指数的に上がる($2^{-t}$ 刻み)一方、コストは制御 $U^{2^k}$ の回数として線形にしか増えない——この非対称性がQPEの威力である。

制御 $U^{2^k}$ の実装コスト

最後の懸念として、$U^{2^{t-1}}$ は「$U$ を $2^{t-1}$ 回」であり指数回に見える。一般の $U$ ではその通りだが、Shorで使うモジュラー乗算 $U_a$ では $U_a^{2^k}=U_{a^{2^k}\bmod N}$ であり、指数 $a^{2^k}\bmod N$ は反復2乗法で $k$ 回の古典乗算で先に計算できる。すなわち各制御ユニタリは(べき乗済みの $a'$ による)1回のモジュラー乗算回路で済み、全体は多項式規模に収まる。「量子回路の指数を古典前処理に押し付ける」この分業も、Shorの多項式時間性の隠れた立役者である。

この章のまとめと見取り図

• QFTは $\mathbb Z/2^n\mathbb Z$ 上のDFTをユニタリとして実装したもの。すべての性質は1の原始根の直交関係(1.2)に還元される。$\mathrm{QFT}_2=H$ であり、Deutsch–JozsaのHadamard変換は $(\mathbb Z/2\mathbb Z)^n$ 上のQFTである。
• 積表示(1.4)によりQFTは積状態への写像であり、$H$ と制御 $R_k$ で $O(n^2)$ ゲート(近似すれば $O(n\log n)$)で組める。回路の実体は「位相キックバックによる2進小数の組み立て」であり、出力はビット逆順で現れるためSWAPで直す。
• 周期的重ね合わせへのQFTは、等比和の破壊的干渉により出力を $N/r$ の倍数へ集中させる。オフセットは消え、周期だけが残る。
• 位相推定は、制御 $U^{2^k}$ のキックバックで固有位相を補助レジスタに転写し、逆QFTで読む。厳密なら確率1、一般でも最良近似が確率 $\ge4/\pi^2$ で得られ、数ビットの追加で任意の信頼度に増幅できる。
• これらを部品として、次章のShorは「位数発見 $\to$ 位相推定 $\to$ QFT」と組み上がる。より広くは、QFTが効く問題は「隠れた部分群問題」(周期発見・離散対数はその特別な場合)として統一的に理解されており、量子的指数加速のほぼ唯一知られた源泉である。