Quantum Alternating Operator Ansatzの概要レビュー

Yuichiro Minato

2021/01/23 02:09

はじめに

量子コンピュータで組合せ最適化問題を解きたい時には、通常イジングモデルと呼ばれる物理統計モデルを利用します。そのなかでコスト関数と呼ばれる式を作っていくのが問題を解くことに対応するのですが、その中で大きな問題となるのが、ソフト制約と呼ばれる満たすべき組み合わせ最適化問題の制約条件を式の中に入れる必要があり、問題を解く際に大きな障壁となっています。

量子ゲート方式の量子コンピュータでは、この組合せ最適化問題をイジングモデルで解くためにはQAOAというアルゴリズムを最近はよく使います。QAOAは量子断熱過程を再現したアルゴリズムを変分計算の形に書き直しています。

\langle \Psi_1 \mid C \mid \Psi_1 \rangle

の期待値を求めることで、最小基底状態の期待値を量子古典ハイブリッド計算で求めることができます。Cはコスト関数、 $\Psi_1$ は測定時の量子状態です。

イジングモデルは、

C(s) = c + \sum_{i=1}^N h_i s_i + \sum_{i=1}^N\sum_{j=i+1}^N J_{ij}s_is_j

のような形でコスト関数が書かれ、sの代わりにZ基底を利用することでゲート演算の時間発展として解くことができます。

QAOAでは、時間発展の量子断熱計算に、上記の変分原理を導入した形で問題をときますが、上記の最小エネルギーの期待値を求めるために、自明な量子状態 $\Psi_0$ から非自明な状態の $\Psi_1$ に変化させるために断続的なゲート演算の適用である、

\mid \Psi_1 \rangle = \left( \prod_{\alpha=p}^1 U(B,\beta_\alpha)U(C,\gamma_\alpha)\right) \mid \Psi_0 \rangle

を利用します。初期の量子状態に２種類のユニタリ行列を交互にかけることで量子状態を変化させることができます。初期の量子状態は下記を準備することが通常です。

\mid \Psi_0 \rangle = \mid + \rangle^{\otimes N}

ここで、Bは、

B = \sum_{i=1}^N \sigma_i^x

のように時間発展の形で導入され、

U(B,\beta_\alpha) = e^{-iB\beta_\alpha}

のような形になります。Bはmixing operatorと言って量子ビットの値を変化させることで解を探索しますが、今回はこのmixing operatorをうまく変形することで探索を効率的に行おうというものになります。

参考資料

From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz

Stuart Hadfield, Zhihui Wang, Bryan O'Gorman, Eleanor G. Rieffel, Davide Venturelli, Rupak Biswas (Submitted on 11 Sep 2017 (v1), last revised 28 Feb 2019 (this version, v2))

https://arxiv.org/abs/1709.03489

QAOA

Quantum Approximate Optimization Algorithmは量子断熱計算を利用して組合せ最適問題をときますが、上記の式をまとめて、

C(s) = c + \sum_{i=1}^N h_i \sigma^z_i + \sum_{i=1}^N\sum_{j=i+1}^N J_{ij}\sigma^z_i\sigma^z_j

の形で書かれる最適化問題を、

\mid \Psi_1 \rangle = \left( \prod_{\alpha=p}^1 e^{-iB\beta_\alpha} e^{-iC\gamma_\alpha}\right) \mid + \rangle^{\otimes N}

の形で量子状態を変化させて、

\langle \Psi_1 \mid C \mid \Psi_1 \rangle

の値の最小値を求めます。

繰り返しになりますが、Cには求めたいコスト関数を導入する一方、Bには、ここで、Bは、

B = \sum_{i=1}^N \sigma_i^x

となるmixing operatorを導入します。

一方Quantum Alternating Operator Ansatz

もう一つのQAOA、Quantum Alternating Operator Ansatzは、上記のmixing operator U(B)を改造します。

初期状態に対して、QAOAをかける際に、コスト関数を導入した演算子はそのままで、ドライバーハミルトニアンや、mixing operatorと呼ばれる部分を改造し、制約を考慮した形でゲートの時間発展を実現します。

組み合わせ最適化問題における探索はとても大きな空間を探索することになり、混合演算子(mixing operator)によって、 $2^N$ の値を探索する必要があります。

Quantum Alternating Operator Ansatzを導入することで、初期状態を制限し、制約条件を維持したまま探索空間を制限することでより効率的な計算ができます。

Quantum Alternating Operator Ansatzは特定のmixing operatorを指すわけではなく、様々なテクニックの総称みたいなので、多くのテクニックがありそうです。

参考２

わかりやすい参考があったので、

[QAOA]SWAPの時間発展で|10>と|01>とを入れ替える
https://qiita.com/gyu-don/items/c51a9e3d5d16a6d5baf6

こちらも参考にしてみてください。基本的な考え方は、|01>と|10>状態のようなものに対して、SWAPゲートを適用して、入れ替えることを時間発展を通じて行います。

初期状態として、|00>と|11>の確率振幅を0にした上で、上記のSWAPの時間発展を混合演算子（ここではただの時間発展でシミュレート）として利用することで、QAOAにおけるmixing operatorとして使えることを示しています。|00>と|11>を探索する必要がなくなるので、とても便利そうです。


from blueqat import Circuit, pauli, vqe
from blueqat.pauli import qubo_bit as q
from math import pi
import numpy as np

def an(index):
    return 0.5 * pauli.X[index] + 0.5j * pauli.Y[index]

def cr(index):
    return 0.5 * pauli.X[index] - 0.5j * pauli.Y[index]

op = (cr(1) * an(0) + cr(0) * an(1)).to_expr().simplify()
print(op)
x = []
y00 = []
y01 = []
y10 = []
y11 = []
evos = [term.get_time_evolution() for term in op.terms]
for i in range(100):
    c = Circuit().h[0].cx[0, 1].x[1]
    for evo in evos:
        evo(c, i / 100 * pi)
    c.rz(i / 100 * pi)[1]
    for evo in evos:
        evo(c, i / 100 * pi)
    c.rz(i / 100 * pi)[1]
    state = c.run()
    _a, _b, _c, _d = list(np.abs(state) ** 2)
    x.append(i)
    y00.append(_a)
    y10.append(_b)
    y01.append(_c)
    y11.append(_d)

import matplotlib.pyplot as plt
plt.plot(x, y00, label='|00>')
plt.plot(x, y10, label='|10>')
plt.plot(x, y01, label='|01>')
plt.plot(x, y11, label='|11>')
plt.legend()
plt.show()

0.5*X[0]*X[1] + 0.5*Y[0]*Y[1]

<Figure size 432x288 with 1 Axes>