第 14 回量子アルゴリズム

本日の内容

14-1. 簡単な量子アルゴリズム
14-2. 量子コンピュータのプログラミング
14-3. 素因数分解
14-4. 有名なアルゴリズム
14-5. 参考文献

$(\begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix}) | ψ ⟩ = ψ_{1, 0} (\begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix}) (\begin{matrix} 1 \\ 0 \end{matrix}) + ψ_{1, 1} (\begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix}) (\begin{matrix} 0 \\ 1 \end{matrix})$ |x> → |1-x>

AND

f(x,y,0)=x,y, x and y

|0> <0| x |0> <0| x I + |0> <0| x |1> <1| x I + |1> <1| x |0> <0| x I + |1> <1| x |1> <1| x (0 1 ; 1 0)

14-3. 素因数分解

量子Fourier変換

複素数ベクトル $x_{0}, ..., x_{N - 1}$ の離散Fourier変換 $y_{0}, ..., y_{N - 1}$ は次式で与えられる

y_{k} = \frac{1}{\sqrt{N}} \sum_{j = 0}^{N - 1} x_{j} e^{2 π ⅈ j k / N} \sum_{j = 0}^{N - 1}

量子Fourier変換は正規直交基底 $| 0 ⟩, ..., | N - 1 ⟩$ に対して次の線形オペレータになる。

\sum_{j = 0}^{N - 1} x_{j} | j ⟩ \to \sum_{k = 0}^{N - 1} (\frac{1}{\sqrt{N}} \sum_{j = 0}^{N - 1} x_{j} e^{2 π ⅈ j k / N}) | k ⟩

ゲート $R_{k}$ を次のように定義する

R_{k} = (\begin{matrix} 1 & 0 \\ 0 & e^{2 π ⅈ / 2^{k}} \end{matrix})

位数発見

14-4. 有名なアルゴリズム

Shor のアルゴリズム

実は、 n Qbit のベクトルに対して、離散フーリエ変換を行ったときの nQbit の関数表は量子多項式時間で求めることができます。

Shor は量子コンピュータを使って、多項式時間で高い確率で、因数分解と、離散対数問題が解けることを示しました。

y^r = 1 mod n となるようなもっとも小さい r を y の mod n のオーダーと言います。もし、非自明な r が求まると、 n の素因数分解ができます。

入力を n とします
n²≤q≤2n² となる「なめらかな整数」q を選びます
n と互いに素な整数 x をランダムに選びます
同じ x を用いてオーダー log q 回繰り返す
1. 二つの量子変数 reg1, reg2 を用意する
2. reg1 は 0 から q-1 までの全ての値の重ね合わせとする
3. reg1 の各値 a に対して、x^a mod n の値の重ね合わせを reg2 に入れる
4. reg2 を観測する。 k' が観測されると、reg1 には x^a' = k mod n となるような a' が観測できる
5. この、 a' を離散フーリエ変換する
6. フーリエ変換の結果を観測すると、ある値 c' が得られる。これは、 q/r の λ 倍になっている
7. c'/q の連分数展開を行うと λ/r が求められる
これによりサンプルがいくつか分かり、最終的に r が求まる。
gcd(x^r/2-1,n) と gcd(x^r/2+1,n) より n を素因数分解する

Groover の選択問題

関数 f(x) が特定の x=x0 で f(x0)=1 になり、他の x では f(x)=0 となるようなことを考えます。

14-5. 参考文献

清水明「新版量子論の基礎　その本質のやさしい理解のために」新物理学ライブラリ別巻2, サイエンス社(2003)
Michael A. Nielsen, Isaac L. Chuang 著、木村達也訳「量子コンピュータと量子通信 I 量子力学とコンピュータ科学」オーム社(2004)
Michael A. Nielsen, Isaac L. Chuang 著、木村達也訳「量子コンピュータと量子通信 II 量子コンピュータとアルゴリズム」オーム社(2005)
Michael A. Nielsen, Isaac L. Chuang 著、木村達也訳「量子コンピュータと量子通信 III 量子通信・情報処理と誤り訂正」オーム社(2005)
上坂吉則著「量子コンピュータの基礎数理」コロナ社(2000)
ランダウ、リフシッツ著、広重徹、水戸巌訳「力学」増訂第3版、ランダウ＝リフシッツ理論物理学教程、東京図書(1974)
高橋康「解析力学を学ぶための解析力学入門」増補第2版、講談社サイエンティフィック(2000)

坂本直志 <sakamoto@c.dendai.ac.jp>
東京電機大学工学部情報通信工学科

第 14 回 量子アルゴリズム