Shorの素因数分解アルゴリズム

いくつか文献を見ましたが、多分初見で一番わかりやすいのはこれです。

流れを説明すると

1. Hadamardゲートでレジスタ１について座標変換し $$ | 0\rangle + | 1\rangle + \cdots + | n - 1\rangle $$ という正規直交基底を作り出します。

2. Unitaryゲートで $$ | 0 \rangle | a^{0} \,\mathrm{mod}\, N \rangle + | 1 \rangle | a^{1} \,\mathrm{mod}\, N \rangle + \cdots + | n - 1 \rangle | a^{n-1} \,\mathrm{mod}\, N \rangle $$ というレジスタ１とレジスタ２の合成状態を作り出します。

3. 2の状態で、レジスタ２の状態はで、これは数通りしかありません。この状態で２を観測することによって状態を固定したとすると、状態１は収縮し、を位数としての形のものの重ね合わせに制約されます。しかし、状態１を観測するのは１回しかできないので、なんとかして１度の観測でを知る必要があります。

4. そこで量子フーリエ逆変換が登場します。これを行うことで、を一発の測定で得ることが可能になります。 量子フーリエ変換後のレジスタの状態は $$\frac{1}{N} \sum_{j = 0}^{n - 1}\sum_{k = 0}^{n - 1} \exp(2\pi ijk/n) | k \rangle | a^j \,\mathrm{mod}\, N\rangle$$ となっています。この状態でレジスタ１を観測するわけですが、本来観測結果は通りあります。しかし、いまが観測されたとして、 その確率を考えてみると、そのときのレジスタ２の値（観測していないが収縮しているはず）をとすると $$\Biggl|\frac{1}{N} \sum_{j: x^j \equiv x^{j_0}} \exp(2\pi ijk_0/n) \Biggr|^2$$ となります。 和の条件を満たすがのようにかけるので、これをもとに式を整理すると（省略しますが、誤差がの積分に帰着します。完璧な導出は元論文にあります）、を満たすとき、この値が大きくなり、観測されやすいことがわかります。 さて、実はこれを満たすは１つに絞られます。具体的な操作としては、この不等式を変形すると整数を用いて $$-\frac{r}{2} \le rk_0 - dN \le \frac{r}{2}$$ つまり $$\Bigl|\frac{k_0}{N} - \frac{d}{r}\Bigr| \le \frac{1}{2N}$$ なので、を連分数分解することによりが求められます。