情報の側から見ると：1回の測定は周期について何 nat 運ぶか

相対エントロピーから情報と物理を組み立てる　第6部 第3章 §6.3.5　★★★ 逆 Fourier 変換の前に測ると $I(S;M)=0$、後に測ると $I(S;M)\approx\ln r$。周期の情報は位相にあり、出力は一様分布から $D$ だけ離れる

隠れた変数 $S$ と測定値の相互情報量

式 (6.3.5) により、$| 1 \rangle$ から始めた回路は「$s$ を一様に選んで $| u_s \rangle$ で位相推定をした」ものと同じ分布を与える。そこで $s$ を確率変数 $S$（$\{0,\dots,r-1\}$ 上の一様分布）とみなし、測定値 $M$ との相互情報量 $I(S;M)=D(p_{SM}\,\|\,p_Sp_M)$（第1部第3章）で、1回の測定が $s/r$ について運ぶ情報を測る。$p(m\,|\,s)$ は式 (6.3.7)、$p(m)$ は式 (6.3.8) である。$I(S;M)=H(M)-H(M\,|\,S)\le H(S)=\ln r$ で、等号は $M$ から $S$ が確定するときに限る。

比べるために、逆 Fourier 変換を当てずに第1のレジスタを計算基底で測る場合を考える。式 (6.3.4) を逆に解いて、制御した掛け算の直後の状態 (6.3.6) を $| u_s \rangle$ で展開すると

$$\frac{1}{2^{t/2}}\sum_{x}| x \rangle | a^x\bmod N \rangle =\frac{1}{\sqrt r}\sum_{s=0}^{r-1}\Bigl(\frac{1}{2^{t/2}}\sum_{x=0}^{2^t-1}\mathrm{e}^{2\pi\mathrm{i} sx/r}| x \rangle \Bigr)| u_s \rangle\tag{6.3.13}$$

となる。$s$ の情報は第1のレジスタの位相 $\mathrm{e}^{2\pi\mathrm{i} sx/r}$ にだけ書かれていて、各 $| x \rangle$ の振幅の大きさは $s$ によらず $2^{-t/2}$ である。したがって計算基底で測った $X$ の分布は $s$ によらず一様で、$I(S;X)=0$ である。同じ状態でも、測る基底を間違えると周期について何も分からない。逆 Fourier 変換は、位相の傾き $s/r$ を振幅の山の位置に移し、その位置を計算基底の測定で読めるようにする基底の変換である。

$r$ が $2^t$ を割り切るときは $p(m\,|\,s)$ が $m=2^ts/r$ に集中するので $H(M\,|\,S)=0$、$I(S;M)=\ln r$ で、1回の測定が $s$ を確定させる。$r$ が $2^t$ を割り切らないときは山にすそがあるので $H(M\,|\,S)>0$ だが、$N=21$、$t=9$ で数えると

$$H(M)=2.613,\quad H(M\,|\,S)=0.828,\quad I(S;M)=1.785\ \text{nat}\quad(\ln6=1.792)\tag{6.3.14}$$

で、$\ln r$ の $99.6\%$ が測定値に移っている。すそは $m$ の値を曖昧にするが、どの山のすそかはほとんど曖昧にしない。

出力は一様分布からどれだけ離れるか

測定値の分布 $P_M$ と、$2^t$ 個の値の一様分布 $u$ との相対エントロピーは

$$D(P_M\,\|\,u)=\sum_mP(m)\ln\frac{P(m)}{2^{-t}}=t\ln2-H(M)\tag{6.3.15}$$

である。$t$ 量子ビットを測って得られる情報量は Holevo 限界（第3部第7章）で $t\ln2$ 以下に抑えられていて、$t\ln2$ のうち $H(M)$ が測定値の乱雑さ、残りの $D(P_M\,\|\,u)$ が「出力が山に集まった分」である。$N=21$、$t=9$ では $t\ln2=6.238$ のうち $D(P_M\,\|\,u)=3.625$ nat である。

$H(M)$ のうち周期について役に立つのは $I(S;M)\approx\ln r$ だけで、$r<N\le2^n$ なので $\ln r\le n\ln2$、つまり第1のレジスタの容量 $t\ln2\approx2n\ln2$ の半分以下である。残りの容量は、山の位置を $1/(2N^2)$ の精度で決め、連分数で分母を一意に読むために使われている（6.3.3 節）。情報量の勘定で言えば、Shor のアルゴリズムは「$\ln r$ nat を、それより2倍ほど大きなレジスタで、ほぼ全部読む」手続きである。

古典の問い合わせとの比べ方

古典の計算で $f(x)=a^x\bmod N$ を問い合わせて周期を求める素朴な方法は、異なる $x$、$x'$ で $f(x)=f(x')$ となる組（衝突）を見つけ、$r$ が $x-x'$ を割り切ることを使うものである。$x$ を無作為に $q$ 個選ぶと、$f$ の値は $r$ 通りの値に一様に散らばるので、衝突の確率は誕生日の問題と同じく $1-\mathrm{e}^{-q^2/(2r)}$ 程度で、衝突を見るには $q\sim\sqrt r$ 回の問い合わせが要る。$r$ が $N$ と同じ桁なら $\sqrt r\sim2^{n/2}$ で、桁数について指数的に増える。1回の問い合わせの答え $f(x)$ そのものは、衝突が起きるまで $r$ について何も教えない。量子の回路は1回の制御した掛け算の重ね合わせ (6.3.6) から $\ln r$ に近い情報を引き出す。この比較は素朴な方法についてのもので、数体ふるい法のように数論の構造を使う古典の方法には当てはまらない。古典の計算量の下界は知られていない。