Cloud support

Nobisuke

Dekisugi

RAG

量子コンピュータデータサイエンティスト講座：QAOA

Yuichiro Minato

2021/02/21 12:51

#量子ゲート

3.QAOA

VQEはansatzを高度化することで問題特化型のアルゴリズムとして発展をさせることができます。ここでは、VQEの変分法をベースに、ansatzを組合せ最適化問題に特化した形で発展をしたQAOA(Quantum Approximate Opitmization Alogirthm)をみてみます。

3-1.量子断熱計算

量子断熱計算は、状態ベクトルを断続的に変化させることで基底状態をキープしたまま時間発展を行うことができる理論です。

初期状態のハミルトニアンを $H_{start}$ として、最終的に求めたい問題のハミルトニアンを $H_{final}$ としたときに、時間 $t$ と全体のスケジュール $T$ から、

H_{temp} = (1-\frac{t}{T})H_{start} + \frac{t}{T}H_{final}

としたときに $T\rightarrow\infty$ とすれば、時間発展で変化させた状態ベクトルが、その瞬間瞬間のハミルトニアンに追従し、固有状態をとり固有値 $\lambda$ を持つようにすることができます。

H_{temp}\mid \psi \rangle = E_{0temp}\mid \psi \rangle

時間発展計算は、

\mid \psi_{t+1} \rangle = U \mid \psi_t \rangle = e^{-iHt} \mid \psi_t \rangle

となります。課題は基底状態と第一励起状態が最接近する部分ですが、 $E_1(t)-E_0(t)$ のエネルギー差に注意して計算することによって、基底状態をキープできます。

3-2.QAOA回路

QAOAは上記の量子断熱計算の時間発展計算をansatzとして変分アルゴリズムに適用したものです。

|0> --H-- --RZZ--RZ-- --RX-- --RZZ--RZ-- --RX--
            |                  |
|0> --H-- --RZZ--RZ-- --RX-- --RZZ--RZ-- --RX--

全体構成を大きく分けて、

1.mixerを選ぶと、初期状態が決まる
2.定式化をQUBOもしくはZで作る

です。2番目の定式化は自動的に時間発展されます。

一番左は初期固有状態|+>を作っています。これに対応するハミルトニアンXは時間発展の形でRxで出てきます。通常はmixerはデフォルトではXを選び、初期状態はそれに対応する|+>を作るために、 $H^ {\otimes N}$ が利用されることが多いです。

また、CX-Rz-CXは問題設定のハミルトニアンのウェイトに対応し、次のRzはハミルトニアンのバイアスに対応しています。

blueqatのQaoaAnsatzはハミルトニアンとステップ分割数を決めれば、自動的にこの時間発展のansatzを構成してくれます。ライブラリ側で適切な計算をしてくれているので、私たちがするのはハミルトニアンの定式化とmixerの選択です。簡単な定式化を解いてみましょう。

例題１：イジング定式化

イジングモデルと呼ばれる物理モデルを利用して組合せ最適化問題を解きます。イジングモデルでは通常スピンの上下を利用して問題を定式化します。定式化では演算子としてZを利用します。Zは+1と-1を期待値としてもとめられます。

H = -Z_0 -Z_0*Z_1

の定式化を解いてみたいと思います。まずはこの定式化（ハミルトニアン）を準備します。


from blueqat.pauli import X, Y, Z, I
h = -Z(0) - Z(0)*Z(1)


from blueqat import vqe

step = 2
result = vqe.Vqe(vqe.QaoaAnsatz(h, step)).run()
print(result.most_common(12))

(((0, 0), 0.5350949496829284), ((1, 1), 0.4591659519005235), ((0, 1), 0.005446334815783367), ((1, 0), 0.0002927636007645282))

初期状態ではmixerはX、初期状態は重ね合わせが適用されますので、イジングの定式化だけを準備すれば大丈夫です。最初の数字が答えの候補で、次の数字はそれが現れる確率です。

例題２：QUBO

つぎに、上記ハミルトニアンZの定式化から派生して、0と1で定式化をするQUBOを確認します。QUBOはZの定式化を書き換えた形になりますが、blueqatでは自動変換してくれるツールがあります。

定式化は、

H = 2q_1-4q_0q_1

としてみたいと思います。


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

h = 2*q(1)-4*q(0)*q(1)
step = 2

result = vqe.Vqe(vqe.QaoaAnsatz(h, step)).run()
print(result.most_common(12))

(((1, 1), 0.50830736293327), ((0, 0), 0.48747761964605385), ((1, 0), 0.00392041281078928), ((0, 1), 0.00029460460988603226))

これを解くことで、量子ビットが共に1の時に最小値が得られます。

例題３：mixerの利用

これまで設定してきた定式化は最終的に解きたい問題のハミルトニアンですが、初期ハミルトニアンを変更することで制約条件などを設定するなどの工夫をすることができます。

3-4.制約条件を満たすmixerを選択する

次にmixerの利用を見ます。mixerを利用することで量子もつれや重ね合わせを利用して解をより効率的に探索できます。ここでは、XYmixerと呼ばれる一般的なmixerを見てみたいと思います。利用するハミルトニアンを、

H = 2q_1-4q_0q_1

として、次はmixerを導入し、初期状態を01と10のもつれ状態からスタートしてみます。


from blueqat import Circuit

#mixer and init state
mixer = 0.5*X[0]*X[1] + 0.5*Y[0]*Y[1]
init = Circuit().h[0].cx[0,1].x[0]

mixerは今回はXYmixerというものを採用します。これは、

X= \begin{bmatrix} 0&1\\ 1&0 \end{bmatrix}

と

Y= \begin{bmatrix} 0&-i\\ i&0 \end{bmatrix}

を組み合わせて、

(X_0X_1 + Y_0Y_1)/2 = \begin{bmatrix} 0&1\\ 1&0 \end{bmatrix} \otimes \begin{bmatrix} 0&1\\ 1&0 \end{bmatrix} /2 + \begin{bmatrix} 0&-i\\ i&0 \end{bmatrix} \otimes \begin{bmatrix} 0&-i\\ i&0 \end{bmatrix} /2 \\ = \begin{bmatrix} 0&0&0&1\\ 0&0&1&0\\ 0&1&0&0\\ 1&0&0&0 \end{bmatrix} /2 + \begin{bmatrix} 0&0&0&-1\\ 0&0&1&0\\ 0&1&0&0\\ -1&0&0&0 \end{bmatrix} /2 = \begin{bmatrix} 0&0&0&0\\ 0&0&1&0\\ 0&1&0&0\\ 0&0&0&0 \end{bmatrix}

これは、01と10の状態を入れ替える操作に対応しています。

また、これは行列の形ですが、この固有状態は簡単に求まります。今回初期状態として準備するのは、これに対応する固有状態で、

\begin{bmatrix} 0\\1\\1\\0 \end{bmatrix}

を準備します。これらは、もつれを使って実現できます。

|0> --H--*--X-- --RZZ--RZ-- --RXX--RYY-- --RZZ--RZ-- --RXX--RYY--
         |        |           |    |       |           |    |
|0> -----X----- --RZZ--RZ-- --RXX--RYY-- --RZZ--RZ-- --RXX--RYY--

量子回路も以前とはちょっと変わりました。


h = 2*q(1)-4*q(0)*q(1)
step=2

result = vqe.Vqe(vqe.QaoaAnsatz(h, step, init, mixer)).run()
print(result.most_common(12))

(((1, 0), 0.9032776521655371), ((0, 1), 0.09672234783446146), ((0, 0), 7.896312771987667e-33), ((1, 1), 4.8148248609680896e-33))

これは、先ほどと同じ定式化ですが、制約がかかっていて、01か10のどちらかしか出ないようになっていますので、答えは、10が出ています。このように制約を利用することによって出るべきでない解に制約をかけるなど工夫することで正答率を上げることができます。


result.circuit

Circuit(2).h[0].cx[0, 1].x[0].cx[0, 1].rz(15.55850370291395)[1].cx[0, 1].rz(-15.55850370291395)[0].h[0].h[1].cx[0, 1].rz(11.22067765633707)[1].cx[0, 1].h[0].h[1].rx(-1.5707963267948966)[0].rx(-1.5707963267948966)[1].cx[0, 1].rz(11.22067765633707)[1].cx[0, 1].rx(1.5707963267948966)[0].rx(1.5707963267948966)[1].cx[0, 1].rz(57.652110188386146)[1].cx[0, 1].rz(-57.652110188386146)[0].h[0].h[1].cx[0, 1].rz(-10.518914223265991)[1].cx[0, 1].h[0].h[1].rx(-1.5707963267948966)[0].rx(-1.5707963267948966)[1].cx[0, 1].rz(-10.518914223265991)[1].cx[0, 1].rx(1.5707963267948966)[0].rx(1.5707963267948966)[1]