Shor のアルゴリズムは一つの目玉だと思うので、ここまで来たということで少し整理しておこう。
動機付け
RSA暗号 - Wikipedia によると
RSA暗号（RSAあんごう）とは、桁数が大きい合成数の素因数分解問題が困難であることを安全性の根拠とした公開鍵暗号の一つである。
ということで、逆に考えると「大きい合成数の素因数分解」を効率良く試みたいという欲求が生まれる。まったく詳しくないが「Miller–Rabin 素数判定法」だとかの確率的アルゴリズムが知られている。似ているような似ていないような気がするが、Shor のアルゴリズムでも確率的な手法を用いることになる。何故「大きい合成数の素因数分解」という概念が出てくるのかはRSA 暗号 - らんだむな記憶で後ほど概観する。
Shor のアルゴリズムの中身をポイントを絞って振り返ってみよう:
位数発見
素因数を見つけたい整数を $N$ とする。Shor のアルゴリズムは何段階かのステップに分かれるが、その中で $x \in \{1, \cdots N-1\}$ に対して $x$ の位数 $r$、すなわち
$$
\begin{align*}
x^r \equiv 1 \mod N
\end{align*}
$$
を満たす $r$ を見つけたいというのがある。これを求めるステップに突入する際の前提条件のもと、一般化された Fermat の小定理（Euler の定理）を用いると、$x$ がある位数を持つことが保証される。具体的にはオイラー関数を $\varphi$ とする時、$r | \varphi(N)$ として求まる。
この位数を求める計算量は古典コンピュータの範囲ではとても大きなものになるが、一方で量子計算を用いると圧倒的に計算量が減るというのが Shor のアルゴリズムの核心部分である。
量子位相推定
$N$ とランダムに選ばれた $x \in \{1, \cdots N-1\}$ から、$\lceil \log_2(N) \rceil$ 個の量子ビットに作用するユニタリゲート $U$ を巧妙に構築する。$U$ は固有ベクトル $\ket{u_j}$ を持ち、その固有値は $e^{2 \pi i \frac{j}{r}}$ となる。よって、適当な $\ket{u_j}$ が用意できると、対応する固有値の位相 $\frac{j}{r}$ を確率的に推定できる。観測値の最頻値から推定した位相を $\hat{\theta}_j$ と置こう。位相は $n$ ビットでエンコードされるものとすると、$n$ を大きくすることで推定値の精度は確率的に向上する。この時、$r \approx \frac{j}{\hat{\theta}_j}$ で近似的に $x$ の位数を求めることができる。
$\hat{\theta}_j$ については、$U$ を制御ユニタリゲート化することで得られる位相キックバックの効果により、量子位相推定の回路の第 1 レジスタに $U_{QFT} | \hat{\theta}_j \rangle$ のようなものが出てくるので、逆量子 Fourier 変換を適用して $\hat{\theta}_j$ を得るのであった。
ところが、$\ket{u_j}$ 自身は $r$ が未知なので用意できない。一方で関係式 $\ket{1} = \frac{1}{\sqrt{r}} \sum_{j=0}^{r-1} \ket{u_j}$ が成立するので、$\ket{u_j}$ を直接用いる代わりにそれらの重ね合わせとして（陽には $r$ を含まない）$\ket{1}$ を用いることができる。
$\ket{1}$ を第 2 レジスタへの入力として量子位相推定を行うと、$\ket{1}$ を構成する固有ベクトルの「固有値の位相の $2^n$ 倍の近似値」が確率的に観測される。
連分数アルゴリズム
観測された $\hat{\theta}_{j_1}, \hat{\theta}_{j_2}, \cdots, \hat{\theta}_{j_M}$ に連分数アルゴリズムを適用すると、対応する $j$ と $r$ を見つけることができる。一度 $r$ が見つかると、1/2 以上の確率で $\gcd(x^{r/2}, N)$ が $N$ の素因数となる。
以上で、Shor のアルゴリズムを振り返ってみた。スッキリしない部分が残っていることは否めないが、量子計算らしい手法でアプローチをしていることだけは確認できたように思う。何度も戻ってくることになると思うので、ここにまとめとして記しておいた。
