位数の計算

/回路技術

位数計算

位数とは、互いに素の $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$ 等分割された単位円上の点の座標を足し合わせる問題となり、常に0となります。$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}$$

括弧の中の0から $r-1$ までの重ね合わせとなっていますが、逆量子フーリエ変換($\mathrm{QFT^{-1}}$)を行うと、$l’/r$ を求めることができます。

 

物理学
力学、連続体力学、電磁気学、波動・光学、相対論、熱力学、高校理科
散策路TOP
古典物理、量子力学、物性論、数学、応用数学、力学、電磁気学、相対論、熱・統計力学、解析学、代数学、幾何学、統計分析、情報

 

タイトルとURLをコピーしました