位数計算
位数とは、互いに素の $x$ と $m$（$x\lt m$）が与えられたとき、$x^r\pmod{m}=1$ を満たす最小の $r$ です。通常のコンピュータでは、位数を求める計算は計算量的に難しい問題とされています。
この位数計算は、量子コンピュータでは、次で定義されるユニタリ演算子と、
$$U\ket{y}\equiv\ket{xy\bmod{m}} -①$$
その固有関数 $\ket{\phi_l}$ と固有値 $e^{2\pi il/r}$ において、
$$U\ket{\phi_l}=e^{2\pi il/r}\ket{\phi_l} -②$$
$$\ket{\phi_l}=\frac{1}{\sqrt{r}}\sum_{j=0}^{r-1}e^{-2\pi ijl/r}\ket{x^j\bmod{m}} -③$$
量子位相推定を解く（②の $l/r$ を求める）問題に置き換えられます。
尚、ユニタリ演算子と固有関数について、以下の関係式が成り立ちます。
$$U\ket{x^j\bmod{m}}=\ket{x^{j+1}\bmod{m}} -④$$$$\frac{1}{\sqrt{r}}\sum_{l=0}^{r-1}\ket{\phi_l}=\ket{1} -⑤$$
②を導く
③にユニタリ演算子を作用させ、④を使うと、
$$U\ket{\phi_l}=\frac{1}{\sqrt{r}}\sum_{j=0}^{r-1}e^{-2\pi ijl/r}U\ket{x^j\bmod{m}}$$$$=\frac{1}{\sqrt{r}}\sum_{j=0}^{r-1}e^{-2\pi ijl/r}\ket{x^{j+1}\bmod{m}}$$
$$=\frac{1}{\sqrt{r}}\Big(e^{-2\pi i\cdot0\cdot l/r}\ket{x^1\bmod{m}}+\cdots$$$$+e^{-2\pi i(r-2)l/r}\ket{x^{r-1}\bmod{m}}+e^{-2\pi i(r-1)l/r}\ket{x^r\bmod{m}}\Big)$$
$$=e^{2\pi il/r}\frac{1}{\sqrt{r}}\Big(e^{-2\pi i\cdot1\cdot l/r}\ket{x^1\bmod{m}}+\cdots$$$$+e^{-2\pi i(r-1)l/r}\ket{x^{r-1}\bmod{m}}+e^{-2\pi irl/r}\ket{x^r\bmod{m}}\Big)$$
最後の項について、$e^{-2\pi il}=1$ であり、$\ket{x^r\bmod{m}}=\ket{1\bmod{m}}$ であるため、以下のように書くことができます。
$$=e^{2\pi il/r}\frac{1}{\sqrt{r}}\Big(e^{-2\pi i\cdot1\cdot l/r}\ket{x^1\bmod{m}}+\cdots$$$$+e^{-2\pi ij(r-1)/r}\ket{x^{r-1}\bmod{m}}+e^{-2\pi i\cdot0\cdot l/r}\ket{x^0\bmod{m}}\Big)$$$$=e^{2\pi il/r}\frac{1}{\sqrt{r}}\sum_{j=0}^{r-1}e^{-2\pi ijl/r}\ket{x^j\bmod{m}}$$$$=e^{2\pi il/r}\ket{\phi_l}$$
④を導く
$p$ と $q$ を自然数として、$x^j=pm+q$ と置くと、④の両辺は、
$$U\ket{x^j\bmod{m}}=U\ket{q}=\ket{xq\bmod{m}}$$$$\ket{x^{j+1}\bmod{m}}=\ket{x(pm+q)\bmod{m}}=\ket{xq\bmod{m}}$$
これより④が成り立つことが分かります。
⑤を導く
⑤の左辺に③を代入すると、
$$\frac{1}{\sqrt{r}}\sum_{l=0}^{r-1}\ket{\phi_l}=\frac{1}{r}\sum_{j=0}^{r-1}\Big(\sum_{l=0}^{r-1}e^{-2\pi ijl/r}\Big)\ket{x^j\bmod{m}}$$
$j\ne0$ の場合、この括弧の中は、$r$ 等分割された単位円上の点の座標を足し合わせる問題となり、常に０となります。$j\ge2$ の場合でも、単位円上の点の数と位置は変わりません。
$$\sum_{l=0}^{r-1}e^{-2\pi ijl/r}=\sum_{l=0}^{r-1}(e^{-2\pi il/r})^j=0$$
$j=0$ の場合、
$$\frac{1}{\sqrt{r}}\sum_{l=0}^{r-1}\ket{\phi_l}=\frac{1}{r}\sum_{l=0}^{r-1}e^{-2\pi i\cdot0\cdot l/r}\ket{x^0\bmod{m}}$$$$=\ket{1}$$
量子回路
量子位相推定では、②の $l/r$ を以下の量子回路を使って求めます。
$$\Psi_2=\frac{1}{\sqrt{2^n}}\sum_{k=0}^{2^n-1}\ket{k}\otimes U^k\ket{\phi}$$
但し、下部のレジスタは $\ket{\phi_l}\to\ket{1}$ と置きます。
従って、
$$\Psi_2=\frac{1}{\sqrt{2^n}}\sum_{k=0}^{2^n-1}\ket{k}\otimes U^k\ket{1}$$
これに⑤を代入し、②を使うと、
$$\Psi_2=\frac{1}{\sqrt{2^n}}\sum_{k=0}^{2^n-1}\ket{k}\otimes U^k\frac{1}{\sqrt{r}}\sum_{l=0}^{r-1}\ket{\phi_l}$$$$=\frac{1}{\sqrt{2^n}}\sum_{k=0}^{2^n-1}\ket{k}\otimes\frac{1}{\sqrt{r}}\sum_{l=0}^{r-1}e^{2\pi ikl/r}\ket{\phi_l}$$
$$=\frac{1}{\sqrt{r}}\sum_{l=0}^{r-1}\Big(\frac{1}{\sqrt{2^n}}\sum_{k=0}^{2^n-1}e^{2\pi ikl/r}\ket{k}\Big)\otimes\ket{\phi_l}$$
ここで $0\le l/r\lt 1$ であるため、$2^nl/r=l’/r$ と置くと、
$$\Psi_2=\frac{1}{\sqrt{r}}\sum_{l=0}^{r-1}\Big(\frac{1}{\sqrt{2^n}}\sum_{k=0}^{2^n-1}e^{2\pi ik(l’/r)/2^n}\ket{k}\Big)\otimes\ket{\phi_l}$$
括弧の中の０から $r-1$ までの重ね合わせとなっていますが、逆量子フーリエ変換（$\mathrm{QFT^{-1}}$）を行うと、$l’/r$ を求めることができます。
