なんとなくイメージがつかめたのでアウトプットしてみます。
$$
\def\bra#1{\mathinner{\left\langle{#1}\right|}}
\def\ket#1{\mathinner{\left|{#1}\right\rangle}}
\def\braket#1#2{\mathinner{\left\langle{#1}\middle|#2\right\rangle}}
$$
なんのためのアルゴリズム？
素因数分解が多項式オーダーでできるアルゴリズムです。概要
- 素因数分解したい自然数$ N $と、$ N $に互いに素な自然数$ x $を持ってくる。
- $ x^r \equiv 1(modN) $となる最小の$ r $を求める。（位数）
- $ x^r = nN + 1 $なので、 $ (x^{r / 2} + 1)(x^{r / 2} - 1) = nN $となり$ r $が偶数なら左辺のどちらかは$ N $の因数になる
位数を求める
二つのレジスタを使用します。 第一のレジスタは$ t $qubit使用します。ここは、位相推定するときの精度をどうするかで決まっていきます。 第二のレジスタは$ L $qubit使用します。$ L $は$ N $を表すことができるサイズにします。($ L = \lceil log_{2}N \rceil $)初期状態は第一のレジスタは$ \ket{0} $ ,第二のレジスタは$ \ket{1} $にしておきます。
ここで注意したいのは、第二のレジスタの$ \ket{1} $は整数の$ 1 $であるということです。
例えば、$ L = 4 $の場合は$ \ket{1} = \ket{0001} $です。間違いやすいので注意してください。
次に第一のレジスタにのみアダマールゲートを$ t $回作用させます。こうやると、$ \ket{0} $から$ \ket{2^t-1} $まで表すことができます。
状態は$ \frac{1}{\sqrt{2^t}}\sum_{k}\ket{k}\ket{1} $です。
次に$ U\ket{y} = \ket{xy\ mod(N)} $で定義されているユニタリ演算子を使います。
この演算子の固有状態は天下り的ですが$ \ket{u_{s}} = \frac{1}{\sqrt{r}}\sum_{k}exp\frac{-2\pi isk}{r}\ket{x^k\ modN} $となります。
$ U\ket{u_s} = exp(\frac{-2\pi is}{r})\ket{u_s} $です。
また$ \frac{1}{\sqrt{r}}\sum_{s}\ket{u_s}=\ket{1} $なので、$ r $が分からなくても$ \ket{1} $を用意すれば、$ \ket{u_s} $の重ね合わせの状態を得ることができます。
これを第二のレジスタに$ k $回作用させます。
\begin{align}
&\frac{1}{\sqrt{2^t}}\sum_{k=0}^{2^t-1}\ket{k}\ket{1}\\
→ &\frac{1}{\sqrt{2^t}}\sum_{k=0}^{2^t-1}\ket{k}U^{k}\ket{1}\\
= &\frac{1}{\sqrt{2^t}}\sum_{k=0}^{2^t-1}\ket{k}U^{k}\frac{1}{\sqrt{r}}\sum_{s=0}^{r-1}\ket{u_s}\\
= &\frac{1}{\sqrt{r2^t}}\sum_{k=0}^{2^t-1}\sum_{s=0}^{r-1}exp(\frac{-2\pi is}{r})\ket{k}\ket{u_s}\\
= &\frac{1}{\sqrt{r2^t}}\sum_{k=0}^{2^t-1}\sum_{s=0}^{r-1}exp(\frac{-2\pi i\frac{\tilde{s}}{r}}{2^t})\ket{k}\ket{u_s}\\
→ & \frac{1}{\sqrt{r}}\sum_{s=0}^{r-1}\ket{\frac{\tilde{s}}{r}}\ket{u_s}
\
\end{align}
ここで$ \tilde{s}=2^ts $と置きました。最後は、量子フーリエ変換の逆変換をしています。
第一のレジスタを測定すれば$ \frac{\tilde{s}}{r} $を得ることができます。（$ \tilde{s} $の値は確率的に定まる。）あとは連分数展開をして$ r $を求めればおしまいです。
例
$ n=15 $の例でやってみます。 今回$ x=7 $を使います（$ x $は$ N $と互いに素ならどれでも大丈夫です。） 今回は、第一レジスタを11bit、第二レジスタを3bitにします。（第一レジスタは予測できる位相の精度になります。\begin{align}
&\ket{0}\ket{1}\\
→ &\frac{1}{\sqrt{2^t}}\sum_{k=0}^{2^t-1}\ket{k}\ket{1}\\
= &\frac{1}{\sqrt{2^t}}[\ket{0} + \ket{1} + \ket{2} + ‥ + \ket{2^t-1}]\ket{1}\\
→ &\frac{1}{\sqrt{2^t}}\sum_{k=0}^{2^t-1}\ket{k}\ket{7^k\ modN}\\
= &\frac{1}{\sqrt{2^t}}[\ket{0}\ket{1} + \ket{1}\ket{7} + \ket{2}\ket{4}+\ket{3}\ket{13}+\ket{4}\ket{1}+\ket{5}\ket{7}+\ket{6}\ket{4}+・・・]
\end{align}
ここで例えば第二レジスタを測定して$ \ket{4} $が与えられたとします。
すると、状態ベクトルは（確率振幅は省略します。）$ [\ket{2} + \ket{6} + \ket{10} + ・・・] $となります。
この周期の$ 4 $が求めたい位数になっています。
しかし実際問題、この状態ベクトルの重ね合わせは確認できないのでこの手法をとることができません。
そのため、量子フーリエ変換の逆変換を行うことで$ \frac{\tilde{s}}{r} $を求めることができます。（$ \tilde{s}=2^ts $）
グラフを書いてみればわかりますがこの場合は４つパルスがたったグラフになっています。(0, 512, 1024, 1536です。)
512を例にとって考えます。
$ \frac{\tilde{s}}{r} = \frac{2^ts}{r}$なので512を$ 2^t $で割って割ってあげれば$ \frac{s}{r} $を求めることができます。
ここで注意することは$ 0 < r < 15 $なので$ s $は$ 15 $より小さくならないといけません。
そこで、連分数展開をして近似します。
\begin{align}
\frac{1536}{2048}=\frac{1}{1+\frac{1}{3}} = \frac{3}{4}
\end{align}
これ以上展開すると15を超えるので、やる意味がなくなるのでここで止めておきます。
この分母のrが求めたかった位数4になっており偶数なので、素因数を求めることができました。