External Memory

プログラミング周辺知識の備忘録メイン

量子Fourier変換と素因数分解問題

量子Fourier変換

量子Fourier変換は量子力学的振幅に対してFourier変換を実行するための効率的アルゴリズムであり、位数発見、素因数分解、離散対数問題などを効率的に解くことが可能となる。

正規直交基底|0〉,...,|N-1〉上の量子Fourier変換は以下の作用をする線形オペレータとして定義される。

|\displaystyle j\rangle→1/\sqrt{N}\sum_{k=0}^{N-1} e^{2\pi ijk/N} |k\rangle
任意の状態に対しては、

\displaystyle \sum_{j=0}^{N-1} x_j|j\rangle→\sum_{k=0}^{N-1} y_k|k\rangle
\displaystyle y_k\equiv 1/\sqrt{N}\sum_{j=0}^{N-1} x_je^{2\pi ijk/N}

振幅y_kは振幅x_jの離散Fourier変換である。Fourier変換はユニタリー性を有する。

N=2^n、|0\rangle,...|2^n -1\rangleはn個のqビットの計算基底である。
状態 |j\rangleを2進小数j_l/2+j_l/4+\ldots+j_m/2^{m-l+1}を表す記号0.j_lj_{l+1}...j_mを使う。
すると量子Fourier変換の積表現を以下の式のように表される。
|j_1,...,j_n\rangle\\
→1/2^{n/2}(|0\rangle+e^{2\pi i0.j_n}|1\rangle)(|0\rangle+e^{2\pi i0.j_{n-1}j_n}|1\rangle)...(|0\rangle+e^{2\pi i0.j_1j_2...j_n}|1\rangle)

これは上述の量子Fourier変換の定義と等価である。

量子Fourier変換はアダマールゲートとゲートR_k\equiv \begin{pmatrix}1 & 0 \\ 0 &e^{2\pi i/2^k}\end{pmatrix}

を用いて、入力|j_1...j_n\rangleに対して最初のビットにアダマールR_2,R_3,\ldots,R_nを順次適用する。
また第m-qビットに対して、アダマールR_2,R_3,...R_{n-m+1}を適用し、
交換操作を行うと量子Fourier変換の積表現が得られる。
交換操作は制御NOTを制御ビットを互い違いに変えて計3回繰り返す。

位相推定アルゴリズム

位相推定アルゴリズム素因数分解などのいろいろな量子アルゴリズムの基礎となる。
入力として|0〉に初期化されたt個のqビットと(第1レジスタ)
固有値e^{2\pi i\varphi_u}を持つUの固有状態|u〉(第2レジスタ)
整数jに対して制御U^j演算を行うブラックボックスを適用し
\varphi_uに対するnビット近似\widetilde{\varphi_u}を推定する。

初期状態に対して|0〉にアダマール変換を施し重ね合わせた後、ブラックボックス演算を適用する。
演算を適用すると\displaystyle /2^{t/2}(|0\rangle+e^{2\pi i0.\varphi_t}|1\rangle)(|0\rangle+e^{2\pi i0.\varphi_{t-1}\varphi_t}|1\rangle)...(|0\rangle+e^{2\pi i0.\varphi_1..\varphi_t}|1\rangle)となる。

Fourier逆変換を適用して、第一レジスタの測定を行う。
逆変換は

\displaystyle 1/2^{t/2}\sum_{j=0}(2^t-1) e^{2\pi i\varphi_j|\rangle}|u\rangle→|\widetilde{\varphi}\rangle|\rangle

|\widetilde{\varphi}\rangleは測定されると\varphiの推定量を与える。

2^-nの精度で1-εの成功確率でφを得るには
p(|m-b|>error)\le \frac{1}{2(2^{t-n} -2)}と書けるので(mは測定結果で、bはターゲット)
t=n+\lceil log(2+1/2\epsilon)\rceil
のqビットが必要である。
これはFourier逆変換後の状態が

\displaystyle 1/2^t\sum_{k,l=0}^{2^t-1} e^{-2\pi ikl/2^t}e^{2\pi i\varphi k}|l\rangle

だから振幅は

\displaystyle 1/2^t\sum_{k=0}^{2^t-1}(e^{2\pi i(\varphi-(b+l)/2^t)})^k
であり、測定結果mを観測する確率が導かれる。

素因数分解問題

位数発見

y∈{0,1}^Lとしてある巡回群Z_Nの単元をxとしその位数は以下のユニタリーオペレータで表される。
U|y\rangle \equiv|xy(mod N)\rangle

位数rに対して0≦s≦r-1とすると
\displaystyle |u_s\rangle \equiv1/\sqrt{r}\sum_{k=0}^{r-1} exp[-2\pi isk/r]|x^k mod N\rangle

この状態は以下の式によりUの固有状態であることが分かる。
\displaystyle U|u_s\rangle=1/\sqrt{r}\sum_{k=0}^{r-1} exp[-2\pi isk/r]|x^k+1\ mod N\ \rangle\\
\ \ \ \ \ \ \ \ \ \ =exp[2\pi is/r]|u_s\rangle

固有値exp(2\pi is/r)が得られて位数rが得られる。
Uはxが単元なのでユニタリーである。

ある個数 t=2L+1+[log(3+1/2\epsilon) のqビット初期状態|0〉とL個のqビット状態|1〉に対してアダマール演算を行い、

|j\rangle|k\rangle→|j\rangle|x^{jk}\ mod\ N\rangle

を実行するブラックボックスU_x,Nを適用する。

第一レジスタにFourier逆変換を行い、測定を行った後、連分数アルゴリズムを用いる。
連分数アルゴリズムを用いると、s/rが|s/r-\varphi|\le 1/2rを満たせば、2^{-2L-1}の精度で近似収束値が得られる。
この場合失敗する確率はεであり、素数の数からアルゴリズムを2log(N)回繰り返すと高確率で互いに素なs,rが得られ、rが得られる。

素因数分解

N=p_1^{\alpha_1}...p_m^{\alpha_m}の正の合成数であるとする。Nは奇数でとする。偶数であれば2で除する。xを1≦x≦N-1の範囲でランダムに選び、gcd(x,N)>1でなければ、xの位数rの発見アルゴリズムを用いる。
xが1≦x≦N、rが偶数においてx^r/2=1(mod N)の自明でない解(≠±1)であれば、
gcd(x^r/2-1,N)またはgcd(x^r/2+1,N)はNの有意な素因数であることを利用して素因数を導く。rが偶数かつx^r/2≠-1(mod N)の確率は1-1/2^mであるので1/2以上の高い確率で素因数を導き出せる。

例えば、N=91ならばx=4としてr=6なので、x^r/2 mod 91 =64
よってgcd(64-1,91)=7である。