書籍 p.146 の下のほうの記述を検証しておこう:
$$
\begin{align*}
\sqrt{r} \sum_{j = 0}^{r - 1} \ket{u_j} &= \sum_{k = 0}^{r - 1} \sum_{j = 0}^{r - 1} e^{- 2 \pi i \frac{jk}{r}} \ket{x^k \bmod{N}} \\
&= r \ket{1} + \sum_{k = 1}^{r - 1} \frac{1 - e^{- 2 \pi i \frac{kr}{r}}}{1 - e^{- 2 \pi i \frac{k}{r}}} \ket{x^k \bmod{N}} = r \ket{1}
\end{align*}
$$
であるので、両辺を $r$ で割って、$\frac{1}{\sqrt{r}} \sum_{j = 0}^{r - 1} \ket{u_j} = \ket{1}$ を得る。${}_\square$
$U \ket{a} = \ket{xa \bmod{N}}$ に対して $U \ket{u_j} = e^{2 \pi i \frac{j}{r}} \ket{u_j}$ であるので、$\theta = \frac{j}{r}$ と置いて $n$ 量子ビットでの量子位相推定を適用すると、$\theta$ の近似値 $\hat{\theta} = \frac{\hat{x}_1}{2^n} \ (\hat{x}_1 \in \Z)$ が得られるので、$r \approx \frac{j}{\hat{\theta}}$ として $x$ の位数 $r$ を確率的に推定できる。
かくして、量子位相推定で感じる「固有ベクトルが用意されているという都合の良いシチュエーション」でのアルゴリズムのご利益について一定の意味が与えられたように思う。
書籍 p.147 の $x=2$, $N=15$ の時の回路図は以下のようになった:
1 段目で制御ユニタリゲートを適用しつつ、上段の後半で逆量子 Fourier 変換の SWAP 処理が記述されている。4 段目まで逆量子 Fourier 変換が続くが、3 段目の後半で測定が始まるような記述になっている。ベタベタな実装で $U \ket{a} = \ket{2a \bmod{15}}$ なるユニタリゲート $U$ を実装して、量子位相推定の回路を実装しているという内容である。
q_8, q_9, _q_10, q_11 で表される “第 2 レジスタ” は 4 量子ビットからなるが、これは $U$ の作用するベクトルが $15 = 2^4 - 1$ を法とする整数に対応しているからである。
上記の回路では LSB である q_8 に X ゲートを作用させて、第 2 レジスタを $\ket{0001}$ で初期化している。これは冒頭で見たように状態 $\ket{1} = \frac{1}{\sqrt{r}} \sum_{j = 0}^{r - 1} \ket{u_j}$ を使っていることに対応する。
量子位相推定を使うと、固有状態を与えた時に対応する固有値の近似値が高い確率で観測されるのであった。
の場合 4 つも観察されている。これは固有状態 $\ket{u_0}$, $\ket{u_1}$, $\ket{u_2}$, $\ket{u_3}$ の混合状態を与えたためであり、それぞれの固有値の位相の $2^8$ 倍の値が相対的に高い確率で観測されていることになる。よってそれぞれに対する位相は順不同で $0$, $\frac{1}{4}$, $\frac{1}{2}$, $\frac{3}{4}$、従って $\frac{0}{4}$, $\frac{1}{4}$, $\frac{2}{4}$, $\frac{3}{4}$ となる。これが固有値 $e^{2 \pi i \frac{j}{r}},\ j = 0, 1, 2, 3$ の $\frac{j}{r}$ の部分に対応する。照合すると、$r = 4$ ではないだろうか？と推測される。実際、$2^4 = 16 \equiv 1 \mod 15$ である。ここから素因数 3 が計算できる・・・ということである。(ここまでしなくても、$\ket{1} = \frac{1}{\sqrt{r}} \sum_{j = 0}^{r - 1} \ket{u_j}$ に対応する位相は $r$ 個確認されるはずで、実際 4 つ確認されているので、$r = 4$ と考えられそうな気もする・・・)
なお、ここでは数字の関係性から $r = 4$ を割り出したが、実際には、Shor's Algorithm によると 観測された $\hat{\theta}$ に対する「連分数アルゴリズム」というもので求めていくようである。
$r$ は事前には幾らか分からないが、一般化された Fermat の小定理（Euler の定理）を考慮すると、Euler 関数を $\varphi$ とすると、$r \leq \varphi(N)$ と見積もれると思われる。$N$ が素数の時には $\varphi(N) = N - 1$ となるので、$r$ は決して小さくない数になり得るように思われる。この場合、観測される固有値の位相も相当な個数になると思われるので、RSA 暗号を破ろうとして Shor のアルゴリズムを適用しようとした場合、どういった感じになってくるのだろう・・・というのは気になった。
が、ここで今それを気にしても仕方ないような気もするので、一旦納得することにして、p.150 まで完了としたい。
