イオントラップ型量子コンピュータのIonQ実機で組合せ最適化問題を解くQAOAでmaxcut実行してみた

Yuichiro Minato

2021/07/05 15:47

今回はQAOAについて確認します。量子ゲートで組合せ最適化問題を解きます。まずはblueqat cloudでの計算を確かめます。
https://blueqat.com/gyu-don/87fcb9ce-f5c2-4f9e-8697-191c8781d70b


from bqcloud import load_api
from bqcloud import Device
from blueqat import Circuit
import math

#apiキーを読み込みます
api = load_api()


#回路を書いてみます。rxxゲートを使ってpi/2の角度をしてすることでもつれを作ることができます。
qc = Circuit().rxx(math.pi/2)[0,1]


#まずはシミュレータで実行
qc.m[:].run(shots=100)

Counter({'00': 46, '11': 54})


#次にIonQの実機で実行します。
qc = Circuit().rxx(math.pi/2)[0,1]
task = api.execute(qc, Device.IonQDevice, 10)


#タスクが処理されました
print(task.status())

Status.QUEUED


#結果を表示してみます
result = task.wait(timeout=3600)
if result:
    print(result.shots())
else:
    print("timeout")

Counter({'00': 5, '11': 5})

無事計算結果が出ました。では、IonQでQAOAをやってみます。

まずは簡単な式から、３つの頂点のmaxcut問題を考えてみます。
3つの頂点を考え、辺の重みをすべて1としてみます。

定式化はイジングモデルを考えます。ハミルトニアンという式を作ります。頂点に量子ビットを割り当て、それぞれの値が1もしくは-1を取るとします。

定式化は、

H_c = Z_0Z_1 + Z_1Z_2 + Z_2Z_0

と置くことができます。Zの前の係数はそれぞれ辺の重みに対応しています。

次にもう一つ定式化を準備する必要があります。それが、解を探索するためのミキサーです。これは通常では一番簡単なXを利用します。

H_{init} = X_0+X_1+X_2

上記定式化においてもう一つ準備する必要があるのが、 $H_{init}$ に対応した固有状態である重ね合わせ状態です。こちらは、アダマールゲートを適用することで作ることができます。

そして、量子状態を時間発展させます。時間発展させる式は、時間tに対して、ハミルトニアンを少しずつ入れ替える操作を行います。時間発展は、

\mid \psi_{t+1} \rangle = U \mid \psi_t \rangle

かけるハミルトニアンは、上記の二つのハミルトニアンを入れ替える過程の、

H_t = s*H_{init} + (1-s)*H_c

で時間発展演算子 $e^{-iHt}$ を利用します。

トロッタ展開やらほにゃほにゃすると、QAOAを利用した回路は、p=1という1ステップで解く回路は、

|0> --H--RZZ(beta)-------------RZZ(beta)--RX(gamma)--
         |                     |   
|0> --H--RZZ(beta)--RZZ(beta)--|----------RX(gamma)--
                    |          |   
|0> --H-------------RZZ(beta)--RZZ(beta)--RX(gamma)--

こちらのbetaとgammaを最適化することで回転角を求めて実行することができます。もともとblueqatにはQAOAを実行する機能があります。この回路のことをAnsatzと呼びます。


from blueqat.pauli import Z
from blueqat import vqe

hamiltonian = Z[0]*Z[1] + Z[1]*Z[2] + Z[2]*Z[0]

result = vqe.Vqe(vqe.QaoaAnsatz(hamiltonian, 1)).run()
print(result.most_common(12))

(((1, 0, 0), 0.162033015432909), ((1, 1, 0), 0.162033015432909), ((0, 0, 1), 0.162033015432909), ((0, 1, 1), 0.162033015432909), ((0, 1, 0), 0.16203301543290893), ((1, 0, 1), 0.16203301543290893), ((0, 0, 0), 0.013900953701272978), ((1, 1, 1), 0.013900953701272978))

回路を確認する機能があります。


result.circuit

Circuit(3).h[:].cx[0, 1].rz(-25.930489083659825)[1].cx[0, 1].cx[0, 2].rz(-25.930489083659825)[2].cx[0, 2].cx[1, 2].rz(-25.930489083659825)[2].cx[1, 2].rx(0.4578213663591716)[:]

rzzは以前はcx,rz,cxの組合せで書かれていました。こちらの回路の状態ベクトルを確認してみると、


beta = -25.930489083659825
gamma = 0.4578213663591716

Circuit(3).h[:].cx[0, 1].rz(beta)[1].cx[0, 1].cx[0, 2].rz(beta)[2].cx[0, 2].cx[1, 2].rz(beta)[2].cx[1, 2].rx(gamma)[:].run()

array([-0.02214869+0.11580323j,  0.27513225-0.29382863j,

        0.27513225-0.29382863j,  0.27513225-0.29382863j,

        0.27513225-0.29382863j,  0.27513225-0.29382863j,

        0.27513225-0.29382863j, -0.02214869+0.11580323j])

rzzで書き直したものと比較してみると、


Circuit(3).h[:].rzz(beta)[0,1].rzz(beta)[0,2].rzz(beta)[1,2].rx(gamma)[:].run()

array([-0.02214869+0.11580323j,  0.27513225-0.29382863j,

        0.27513225-0.29382863j,  0.27513225-0.29382863j,

        0.27513225-0.29382863j,  0.27513225-0.29382863j,

        0.27513225-0.29382863j, -0.02214869+0.11580323j])

同じですね。IonQは基本のゲートにrzzやrxxを利用するので、こちらのほうがqaoaが簡単にきれいに書けました。では、さっそく実機にかけてみます。


task = api.execute(Circuit(3).h[:].rzz(beta)[0,1].rzz(beta)[0,2].rzz(beta)[1,2].rx(gamma)[:], Device.IonQDevice, 100)


#タスクが処理されました
print(task.status())

Status.QUEUED


#結果を表示してみます
result = task.wait(timeout=3600)
if result:
    print(result.shots())
else:
    print("timeout")

Counter({'110': 19, '101': 19, '100': 18, '001': 16, '011': 13, '010': 12, '111': 2, '000': 1})

以上、IonQの実機でqaoaが実行できました。思ったよりも精度が高いです。