量子アニーリングとQAOAで素因数分解（組合せ最適化編）

はじめに

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

大事な知識

今回イジングマシンで素因数分解をする時には多体問題への対応が必要となります。ブール代数やグレブナー基底が出てきます。

早速ときます

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

15 = 3*5

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

量子ビットを用意する

まずは量子ビットを用意します。表現したいのは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に

見やすくするために縦横４量子ビットずつの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のパラメータ設定のレンジをはみ出るので、全体を数分の一します。

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

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

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

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

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

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

つづいてQAOA

QAOAは量子ゲートマシンで量子断熱計算を使って組合せ最適化問題を解くようなアルゴリズムです。イジングハミルトニアンもしくはQUBOをつくって計算します。以前作った式を使って、

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

QAOAをQUBOを使ってハミルトニアンを作成

イジングモデルは量子ゲートモデルでは、パウリZオペレーターでハミルトニアンを書きますが、今回はイジングではなく01バイナリ値のQUBOで問題を書いてますので、自動変換が必要です。blueqatからpauli演算子に直してくれるツールを使います。

from blueqat.pauli import qubo_bit as q
from blueqat.pauli import *
hamiltonian = 128*q(0)*q(1)*q(2)+16*q(0)*q(1)-56*q(0)*q(2)-52*q(0)+48*q(1)*Z(2)-96*q(1)-52*q(2)

これで準備が整いました。

QAOA+VQEを実行

次にVQEを実行します。こちらもBlueqatに入ってます。

from blueqat import vqe

step = 2
result = vqe.Vqe(vqe.QaoaAnsatz(hamiltonian, step)).run()
print(result.most_common(5))

(((1, 0, 1), 0.5016550552468441), ((0, 1, 1), 0.17148299431308803), ((0, 0, 1), 0.08740672548230058), ((1, 1, 1), 0.08029439531924541), ((0, 1, 0), 0.07843866417857855))

(((0, 1, 1), 0.41587841359182315), ((1, 1, 1), 0.22999518869583413), ((1, 1, 0), 0.09621729455616015), ((0, 0, 1), 0.09274077321094935), ((1, 0, 1), 0.08165837751142796))

一番最初に011が出てきました。これは5x3に対応していますので合っています。これによって15=5x3ができました。以上です。

まとめ

量子アニーリングと量子ゲートのおける組合せ最適化の暗号解読は同じ方法が取れますが、多体相互作用が活用できる分量子ゲートの方がやりやすいですが、実機となると結合数の問題もあり今後どうなるかわかりません。