@yuichirominato 2019.01.11更新 404views

量子ゲートのNISQ向け素因数分解アルゴリズム

NISQ QAOA VQE 素因数分解

はじめに

IBMQのSystem Oneが発表されて汎用型量子コンピュータが盛り上がっていますが、現在の量子コンピュータは中規模エラーありのNISQと呼ばれるマシンとして知られています。このNISQは本来の量子ゲートマシンのようなShorのアルゴリズムや量子フーリエ変換の実行が難しくなっています。そのため代替の素因数分解アルゴリズムが考えられます。

イジングハミルトニアン

量子ゲートのマシンですが、結局やることは量子アニーリングのようなイジングモデルで数式を作り、素因数分解を最小値問題に落とし込んで解きます。

参考

Quantum factorization of 56153 with only 4 qubits

Nikesh S. Dattani,1,2,∗ Nathaniel Bryans3,†
1Quantum Chemistry Laboratory, Kyoto University, 606-8502, Kyoto, Japan, 2Physical & Theoretical Chemistry Laboratory,
Oxford University, OX1 3QZ, Oxford, UK, 3University of Calgary, T2N 4N1, Calgary, Canada. ∗
dattani.nike@gmail.com,

nbryans1@gmail.com

https://arxiv.org/pdf/1411.6758.pdf

Variational Quantum Factoring

Eric R. Anschuetz, Jonathan P. Olson, Alán Aspuru-Guzik, Yudong Cao
(Submitted on 27 Aug 2018)
https://arxiv.org/abs/1808.08927

Prime Factorization Using Quantum Annealing and Algebraic Geometry

https://1qbit.com/wp-content/uploads/2016/09/1QBit-Research-Paper-%E2%80%93-Prime-Factorization-Using-Quantum-Annealing-and-Algebraic-Geometry.pdf

具体的手順

手順はとてもシンプルです。これまでゲート方式はShorのアルゴリズムを使って問題を解いていましたが、そうではなくて最小値問題に落とし込みます。効率的な落とし込みかたがあり、前処理をいれて143の素因数分解は4量子ビットだけで解けます。

1、量子ビットを使って二進数で乗算を考える

2、桁数の特性を生かしてイジング問題を簡略化する

3、単純化されたイジング問題をQAOAアルゴリズムにかけて最小基底状態を求める。

となっています。ちなみにQAOAは量子ゲートマシンで組合せ最適化問題を解くためのアルゴリズムです。下記を参照してみてください。

量子ゲートで組合せ最適化問題を解くQAOAの実装
https://blog.mdrft.com/post/229

まぁ、結局やることはアニーリングとほとんど同じですが、少し優位性がありそうです。早速例題を見てみます。143の素因数分解をまずします。

1、量子ビットを使って二進数の乗算(143の素因数分解)

まず二進数の乗算を考えます。二進数の乗算と加算を学ぶ必要がありますが、乗算は筆算では10進数とほとんど同じです。

引用:https://arxiv.org/pdf/1411.6758.pdf

これは、m=p*qを考えますが、pを二進数で考えて、一番下と一番上の位は1になることはわかっています。一番上が1は自明で、素数なので一番下の位は0ではない(偶数ではない)です。pとqを二進数で表すと上記のようになります。

まずはこれを単純にかけます。$2^0$の位から10進数のようにかけて、ずらして足し合わせてきます。途中carriesというのは桁上がりになります。二進数で1+1をすると桁が上がるので、$Z_{12}$は$2^1$の位から$2^2$の位に上がると言う意味です。

2、桁数の特性を生かしてイジング問題を簡略化する

次に各位を足し合わせます。足し合わせると連立方程式は、

$$\begin{eqnarray}p_1+q_1 &=& 1+2z_{12}\\
p_2+p_1q_1+q_2+z_{12} &=& 1+2z_{23}+4z_{24}\\
1+p_2q_1+p_1q_2+1+z_{23} &=& 1+2z_{34}+4z_{35}\\

q_2+p_2+z_{45}+z_{35} &=& 0+2z_{56}+4z_{57}\\
1+z_{56}+z_{46} &=& 0+2z_{67}\\
z_{67}+z_{57} &=& 1\end{eqnarray}$$

ここで上から見ていくと、、、まず$p_1+q_1=1+2z_{12}$において、1が確定しているため、$p_1$と$q_1$はどちらかが1であるため、2の位はでてこないため、$z_{12}=0$がわかる。

同様に、$p_2+p_1q_1+q_2+z_{12} = 1+2z_{23}+4z_{24}$はまず、上記より$p_1$と$q_1$はどちらかが1でどちらかが0であるため、$p_1q_1=0$がわかる。また、$z_{12}=0$だったため、$p_2+q_2 = 1+2z_{23}+4z_{24}$となる。ここで、前述と同様1が確定しているため、$z_{23}=0,z_{24}=0$がわかる。

また、$1+p_2q_1+p_1q_2+1+z_{23} = 1+2z_{34}+4z_{35}$は、$z_{23}=0$より、$1+p_2q_1+p_1q_2 = 2z_{34}+4z_{35}$となる。まず桁数が合わないので$z_{35}=0$となり、$1+p_2q_1+p_1q_2 = 2z_{34}$ここで、左辺に1があるため、$z_{34}$は0でないので1が確定する。

これらを進めていってまとめると、下記の式が残る。

$$\begin{eqnarray}p_1+q_1-1 &=&0\\
p_2+q_2-1 &=& 0\\
p_2q_1+p_1q_2-1 &=&0
\end{eqnarray}$$

この3つの連立方程式を最小値問題に落とすためには、各方程式を二乗すると必ず0の時に最小になるので、連立方程式から下記のハミルトニアンを得られる。

$$H=(p_1+q_1-1)^2 + (p_2+q_2-1)^2+(p_2q_1+p_1q_2-1)^2\\=5-3p_1-p_2-q_1+2p_1q_1-3p_2q_1+2p_1p_2q_1-3q_2+p_1q_2+2p_2q_2+2p_2q_1q_2$$

これを総当たりでコスト計算してみると、バイナリ値で$\mid 0000 \rangle$から$\mid 1111\rangle$までで、

$5,2,4,1,4,3,0,1,2,0,3,1,1,1,1,3$

となる。$\mid 6 \rangle$と$\mid 9 \rangle$の時に$H=0$となるので、先に対応する、$\mid 0110 \rangle$と$\mid 1001 \rangle$が答えとなり、

$p=13,q=11$と$p=11,q=13$が答えとなる。

3、単純化されたイジング問題をQAOAアルゴリズムにかけて最小基底状態を求める。

今は答え合せをしたが、これを実際のゲートシミュレーションにかけてみて答えが出るかどうかを確認する。まず、Blueqatを呼び出し、ハミルトニアン準備して、QAOAにかける。step数は場合に応じて調整するが、今回は2とか4とか短めでもOK

https://github.com/mdrft/Blueqat

from blueqat import vqe 
from blueqat.pauli import qubo_bit as q 

hamiltonian = -3*q(0)-q(1)-q(2)+2*q(0)*q(2)-3*q(1)*q(2)+2*q(0)*q(1)*q(2)-3*q(3)+q(0)*q(3)+2*q(1)*q(3)+2*q(1)*q(2)*q(3) 
step = 4 

result = vqe.Vqe(vqe.QaoaAnsatz(hamiltonian, step)).run() 
print(result.most_common(5)) 
                                                                                                                                             
#=> (((0, 1, 1, 0), 0.38282701807018904), ((1, 0, 0, 1), 0.17092057836615537), ((1, 1, 1, 0), 0.08073422675654193), ((0, 1, 1, 1), 0.08073422675654193), ((1, 0, 1, 1), 0.045786141364148956))

ここで、きちんと答えがえら得ていて、0110と1001が十分な確率振幅で得られている。このため量子ゲート方式で基底状態が求まり、素因数分解ができた。

より大きな数

同様に、56153も4量子ビットで解くことができ、291311も6量子ビットで解ける。このように汎用量子ゲートマシンを使って素因数分解ができた。

ちなみに量子アニーリング方式でも解くことができるが、この場合には上記にある3量子ビットの多体問題の2体問題への分解が必要となる。量子ゲートでは3量子ビットの相互作用をハミルトニアンに入れたまま計算できるので、量子ゲートの方が前処理がとても簡単に済むと言う利点がある。

あわせて読みたい

SERVICE

汎用量子コンピュータ向けアプリケーション開発SDK

詳しく見る Githubで入手する(無料)

汎用量子コンピュータ向け高速シミュレータ

詳しく見る

量子コンピュータ向けクラウドサービス(準備中)

詳しく見る

イジングマシン向けアプリケーション開発SDK

詳しく見る Githubで入手する(無料)

COMMUNITY

量子コンピュータのことを学びたい、仕事としたいなどの情報交換の場を設け、コミュニティの形成を進めています。オフラインの勉強会と、オンラインのチャットコミュニティの2種類あります。オフラインのConnpassは1400名、オンラインのSlackは880名を超える参加があります。どちらも無料ですのでお気軽にご参加ください。

CONNPASS SLACK

CONTACT

弊社あての連絡はinfo@mdrft.comより用件を明記の上、メールで連絡を頂けますと幸いです。

ブログトップへ Wikiへ移動

量子コンピュータ一般

量子ゲートアルゴリズム

量子アニーリング一般

量子アニーリングアルゴリズム

BlueqatSDKの使い方