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

はじめに

現在の量子コンピュータは中規模エラーありの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,
†
URLが不正です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-–-Prime-Factorization-Using-Quantum-Annealing-and-Algebraic-Geometry.pdf

具体的手順

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

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

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

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

となっています。ちなみにQAOAは量子ゲートマシンで組合せ最適化問題を解くためのアルゴリズムです。まぁ、結局やることはアニーリングとほとんど同じですが、少し優位性がありそうです。早速例題を見てみます。143の素因数分解をまずします。

１、量子ビットを使って二進数の乗算（143の素因数分解）

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

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

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

２、桁数の特性を生かしてイジング問題を簡略化する次に各位を足し合わせます。足し合わせると連立方程式は、

ここで上から見ていくと、、、まずp_1+q_1=1+2z_{12}において、１が確定しているため、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が確定する。

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

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

これを総当たりでコスト計算してみると、バイナリ値で\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が答えとなる。

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

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

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))

(((0, 1, 1, 0), 0.3845439630296796), ((1, 0, 0, 1), 0.18859194621329145), ((1, 1, 1, 0), 0.06978817939665743), ((0, 1, 1, 1), 0.06978817939665743), ((0, 0, 0, 0), 0.04335938358902308))

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

より大きな数

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

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