@yuichirominato 2018.06.17更新

D-Waveで素因数分解をした

QUBO イジング 量子アニーリング

はじめに

自社で借りているカナダのD-Waveをつかって、量子コンピュータで素因数分解します。ただ、今回使うのは量子アニーリングのイジング型のマシンで、みなさんが思っているゲートのshorを使った解法とは違うものになります。

引用元:https://www.dwavesys.com/resources/media-resources

引用元:https://www.dwavesys.com/resources/media-resources

詳細はカナダのホームページを参照してくださいませ。
https://www.dwavesys.com/

日本語サイトもあります。
http://dwavejapan.com/

大事な知識

今回イジングマシンで素因数分解をする時には多体問題への対応が必要となります。
ブール代数やグレブナー基底が出てきますが、簡単に説明していきます。
参考は下記から
「ブール代数を使ったイジングの多体問題の2体問題への分解」
http://blog.mdrft.com/post/147

早速解いていきましょう

今回は例題はなんでもいいですが、例題なのであまり大きすぎない適度な数字で。
ちなみに1Qbitという会社では200099までD-Waveに実装できているようですが今回はお手柔らかに、、、

$
15 = 5*3
$

くらいでやり方を見ていきます。

量子ビットを用意する

まずは量子ビットを用意します。
表現したいのは5と3です。
求めたい素因数分解の解を下記の通りおいてみて、$p$と$q$を求めます。

$
15 = p*q
$

答えを知ってしまっているので、それぞれの数字を2進数で表現できるように変形します。
また、素因数分解ですので基本的に偶数がでませんので、最初の1は必ず使います。
そうすることによって3量子ビットを使って解くことができます。

$
p = 1+2q_0+4q_1\\
q = 1+2q_2
$

立式

量子アニーリング、イジングモデルの場合には問題を最小値問題に落とし込みます。
今回素因数分解を最小値問題に落とし込むには、左辺から右辺を引いて二乗します。
解くべき数式のハミルトニアンは下記のようになります。

$
H = (15-p*q)^2
$

これを最小の0にできたとき、素因数分解が完了します。基本的にはどんな素因数分解も上記のように解くことができます。

早速展開してみる

先ほどの式を展開してみます。まずは、pとqに先ほどの量子ビット表記した形を代入して、

$
H = \{15-(1+2q_0+4q_1)(1+2q_2)\}^2
$

こちらを展開します。展開した式は面倒ですが、、、

$
H = 16q_0^2q_2^2 + 16q_0^2q_2 + 4q_0^2 + 64q_0q_1q_2^2 + 64q_0q_1q_2 + 16q_0q_1 + 16q_0q_2^2 – 104q_0q_2 – 56q_0 + 64q_1^2q_2^2 + 64q_1^2q_2 + 16q_1^2 + 32q_1q_2^2 – 208q_1q_2 – 112q_1 + 4q_2^2 – 56q_2 + 196
$

ここで、バイナリ値なので$q_i^2=q_i$よりもう少し整理できます。

$
16q_0q_2 + 16q_0q_2 + 4q_0 + 64q_0q_1q_2 + 64q_0q_1q_2 + 16q_0q_1 + 16q_0q_2 – 104q_0q_2 – 56q_0 + 64q_1q_2 + 64q_1q_2 + 16q_1 + 32q_1q_2 – 208q_1q_2 – 112q_1 + 4q_2 – 56q_2 + 196
$

これをまとめて、綺麗な形にできます。

$
H = 128q_0q_1q_2 + 16q_0q_1 – 56q_0q_2 – 52q_0 – 48q_1q_2 – 96q_1 – 52q_2 + 196
$

三体問題の分解を使う

今回三体問題は$q_0q_1q_2$なので、新しい量子ビット$q_3$を使って、

$
q_1q_2 = q_3
$

と表現します。その時に、$q_1,q_2,q_3$が満たすべき条件を綺麗な式で表します。
ペナルティ項を導入すると、元のハミルトニアンは、

$
H = 128q_0q_3 + 16q_0q_1 – 56q_0q_2 – 52q_0 – 48q_1q_2 – 96q_1 – 52q_2 + 196 + \delta(3q_3+q_1q_2-2q_1q_3-2q_2q_3)
$

となりました。

得られたハミルトニアンをQUBOmatrixに

見やすくするために縦横4量子ビットずつのQUBOmatrixに配置して見ます

$
\begin{array}
-&q_0&q_1&q_2&q_3\\
q_0 & -52 & 16 & -56 & 128\\
q_1 & & -96 & \delta-48 & -2\delta \\
q_2 & & & -52 & -2\delta\\
q_3 & & & & 3\delta
\end{array}
$

次にこちらをイジングに直します

通常はソフトウェアが自動変換してくれます。

$
\begin{array}
-&q_0&q_1&q_2&q_3\\
q_0 & -4 & 4 & -14 & 32\\
q_1 & & -0.25\delta-56 & 0.25\delta-12 & -0.5\delta \\
q_2 & & & -0.25\delta-52 & -0.5\delta\\
q_3 & & & & 0.5\delta+32
\end{array}
$

D-Waveにかける

このままではD-Waveのパラメータ設定のレンジをはみ出るので、全体を数分の一します。

これをかけていきますが、これは4量子ビットの完全結合ですので、D-Waveのキメラグラフに実装するには分解する必要があります。4量子ビットの完全結合は6量子ビットあれば表現できます。

今回は下記のようにエクセルでガンマの値や全体の倍率を決めてみました(D-Waveにかけるときに-1から1の間にパラメータが落ち着かないといけないので)。

これを入れてみると、できました!

複数の解が出てきましたが、一番エネルギーの低いのが基底状態のようです。確認してみます。

$q_0=-1,q_1=1,q_2=1$かつ、$q_3=1$となり、余剰量子ビットとboolean reductionを用いた次元の削減も成功しています。ということで、無事解けました。ただ、これまでの問題の中で一番苦労しました。。。

D-Waveで暗号を解くのはとても大変な苦労です。。。

あわせて読みたい