Cloud support

Nobisuke

Dekisugi

RAG

ゼロからQAOAを説明してみる。～基本原理からblueqat実行まで～

量子熊

2021/01/16 10:48

#第２回量子説明コンテスト

QAOAとは何か

QAOA(Qauntum Approximate Optimization Algortihm, 量子近似最適化アルゴリズム)とは、量子アルゴリズムの一種です。

組み合わせ最適化問題を古典よりも高速に、あるいは省エネルギーで(?)解くことが期待されています。

本記事の想定読者は「ベクトルや行列はわかるが、組み合わせ最適化や量子はわからない」人です。

組み合わせ最適化問題

組み合わせ最適化問題は、膨大にある選択肢からコストが最小となるようものを見つける問題です。

例えば、

$n$ 個のコインを投げる時、表の枚数の合計をコスト $C$ とします。表裏のパターン $2^{n}$ 通りからコスト $C$ が最小になるようなものを見つけること

コインの数 $n=1,2,3$ 程度であれば総当りでもよいですが、 $n$ が増えると難しくなります。

数式に落とし込んで、賢いアルゴリズムで解を探索していく必要があります。

我々はこれを量子のパワーで賢く解いてやろうというわけです。

もちろんこの例に限っては、最小コストが $C=0$ (即ち {裏,裏,...,裏})であることは明らかですが、

一般の問題は制約条件があることがほとんど（例えば、隣り合うコインは裏表が異なっていなければならない）です。

簡単に解を思いつく事はできません。

状態とコストをベクトルと行列で書く

今後便利のために、コインの裏表 $q_{1},q_{2},...,q_{n}$ をベクトルで表す記法を導入します。

$n=2$ の時を考え、表を $1$ ,裏を $0$ と表す時、裏表のパターンは $(0,0),(0,1),(1,0),(1,1)$ の $4$ 通りあります。

そこで、 $4$ 成分のベクトル $\vec{q}$ を導入して

$(0,0)$ のときは $\vec{q} = [1,0,0,0]^{T}$

$(0,1)$ のときは $\vec{q} = [0,1,0,0]^{T}$

$(1,0)$ のときは $\vec{q} = [0,0,1,0]^{T}$

$(1,1)$ のときは $\vec{q} = [0,0,0,1]^{T}$

と表すことにします。ベクトルの成分のどれか1つだけが1になります。

$\vec{q}$ に対して、その共役複素数かつ転置したものを $\vec{q}^{\dagger}$ と表します。

また、 $\vec{q}$ を $|q \rangle$ 、 $\vec{q}^{\dagger}$ を $\langle q|$ と表記します。

このとき、コスト(例えば表の数の合計)を巧みな行列記法で表すことができます。

$|q \rangle$ に作用する（うまい） $2^{n} \times 2^{n}$ 行列 $H$ を考えて、 $\langle q|H|q \rangle$ と表現できます。

ぱっと見難しそうですが、

横ベクトル×行列×縦ベクトル = 横ベクトル×縦ベクトル = ベクトル内積 = スカラー　

となりますので、たしかに $\langle q|H|q \rangle$ はベクトル(コインの裏表の情報)を受け取ってスカラー(コスト)を返す関数になっています。

量子

ここから、量子版を説明します。

状態とコスト

量子になっても、状態（コインの裏表の情報）をベクトル $|q \rangle$ で表すことも、コスト $C$ を行列 $H$ を使って $\langle q|H|q \rangle$ と表すことも変わりません。

しかし、ベクトルの自由度が拡張されます。

ベクトルの成分は勝手な複素数を取ることが出来る

ただし、ベクトルの大きさ（長さ）は1でなければならない。

よって、古典的には解釈できない状態が許容されます。例えば、

$|q \rangle = \frac{1}{\sqrt{2}}[1,1,0,0]^{T}$

という状態は、許容されます。

これを古典的な状態に無理やり分解しようとすると、

$|q \rangle = \frac{1}{\sqrt{2}}[1,0,0,0] + \frac{1}{\sqrt{2}}[0,1,0,0]$

という形になります。コインが $(裏,裏)$ の状態と $(裏,表)$ の状態の”和”　です。

そのため、重ね合わせ状態とも呼ばれます。

しかし、状態をベクトルで表現し、その”和を取る”という操作が何を意味するのか、全くわかりません。

更に古典的な解釈が難しい状態をみてみます。

$|q \rangle = e^{j\phi}[1,0,0,0]^{T}$

これも大きさ1のベクトルですので、何らかの量子状態を表現しています

しかし　状態を複素数倍する　というのは、古典的には意味不明です。

直感的なイメージというよりは、ベクトル（と行列）の計算だと割り切ることをおすすめします。

次にコスト $C$ を考えます。

先に述べたように表式は古典と変わらず、 $C = \langle q|H|q \rangle$ です。

ただし状態ベクトルが複素数であることを許しましたので、 $C$ は一般に複素数になりますが、今回は実数になるような $C$ しか使いません。

$H$ がエルミート行列であるとき、 $C$ が実数になります。

コスト最小化

組み合わせ最適化問題を解くことは、コスト $C$ を最小化するような状態 $|q \rangle$ を見つけることです。

状態ベクトルを変化させる

解を探索するには、量子的な状態 $|q \rangle$ を色々と取り替えながら、コスト $C$ を計算する必要があります。

量子状態を操作するにはどうしたらいいでしょうか？

いかなる量子状態も、

ベクトルの成分は勝手な複素数を取ることが出来る

ただし、ベクトルの大きさ（長さ）は1でなければならない。

という条件を満たす必要があります。

実はベクトルの大きさを変えないような変換とは、ユニタリ行列 $U$ のことであって

|q \rangle \to U|q \rangle

と表されます。

$U$ をかけて状態を変化させながら、コストが最小になるようなものを見つければよいのです。

ユニタリ行列 $U$ は、量子コンピューターでは　量子ゲート　と呼ばれます。

状態ベクトルを変化させるユニタリ行列 $U$ をパラメータで表す

ユニタリ行列 $U$ を色々と試して状態を探索するといっても、ユニタリ行列の成分には無数のパターンがあります。

そこで、例えば実数の角度パラメータ $\theta$ を使って

U(\theta) = \left( \begin{array}{cc} \cos(\frac{\theta}{2}) & \sin(\frac{\theta}{2})\\ -\sin(\frac{\theta}{2}) & \cos(\frac{\theta}{2}) \end{array} \right)

のように $U$ を限定します。（簡単のために、1量子の状態ベクトルへの作用を考えました）

これで、 $\theta$ が決まればユニタリ行列 $U$ が決まります。

このようなパラメータ化の方法は色々あります。(上記の例は　回転ゲート　と呼ばれるものです）

$U$ が1つだけだと都合よく解にたどり着くことは難しいので、複数のパラメータ付き $U$ を連結させて

$U(\theta_{n})....U(\theta_{2})U(\theta_{1})$

とします。このようなゲートの連続を「量子回路」と呼びます。

QAOA

ここまでのことがわかれば、QAOAの動作が説明できます。

QAOAの動作は以下のとおりです。

適当な量子（初期）状態 $|q_{init} \rangle$ を用意する。

$2p$ 個のパラメータ付き量子ゲート $U(\beta_{1}), U(\gamma_{1}), ...., U(\beta_{p}), U(\gamma_{p})$ を用意する

上記のゲートからなる量子回路を作り、量子状態に作用させる。

$|q_{init} \rangle \to |q \rangle = U(\beta_{p})U(\gamma_{p}), ...., U(\beta_{1})U(\gamma_{1})|q_{init} \rangle$

$p$ が大きいほど回路が”深く”なり、いろいろな量子状態を探索できるようになります。 $p$ をレイヤー数やラウンド数といいます。

得られた量子状態 $|q \rangle$ におけるコスト $C$ を計算する。

$C = \langle q|H|q \rangle$ なお、行列 $H$ は上記計算が組み合わせ最適化問題のコストの計算に一致するようにうまく選んでおきます。

$C$ がより小さくなるように、量子ゲートのパラメータ $\beta_{1}, \gamma_{1},...,\beta_{p}, \gamma_{p}$ をアップデートします。

アップデートの計算には、古典的な最適化アルゴリズムが使えます。

調子に乗って $p$ を大きくしていると、ここでパラメータの数が増えて最適化が大変になります。

最適化が収束したら、量子状態 $|q \rangle$ を測定し、解を得ます。

例として $p=2$ のQAOAを示します。

2.のパラメータ付き量子ゲートの個数や行列成分の決め方は、天下り的に思えます。

実は背景には量子断熱定理というものがあるのですが、これを知らなくてもQAOAは使えますので、今は良いことにしましょう。

QAOAを使った最適化の具体例

では実際に使ってみましょう。

解く問題はグラフの問題で、MACXCUTと呼ばれるものです。

ここでは4つの頂点からなるグラフを考えます。

問題設定やコストの定式化の詳細については

外部サイト

(5-3. Quantum Approximate Optimazation Algorithm (QAOA): 量子近似最適化アルゴリズム)

https://dojo.qulacs.org/ja/latest/notebooks/5.3_quantum_approximate_optimazation_algorithm.html

をご確認ください。

この問題の解は、 $(1,0,1,0)$ と $(0,1,0,1)$ の2つです。

blueqatで解いてみましょう。


#pip install blueqat


from blueqat import vqe, pauli
import numpy as np
edges = [(0, 1), (1, 2), (2, 3), (0, 3)] # graph to be solved
p = 5 # number of round
H = sum([pauli.Z(i) * pauli.Z(j) for i, j in edges]) # matrix to calc. cost
ansatz = vqe.QaoaAnsatz(H, p) #trial (parametrized) circuit
result = vqe.Vqe(ansatz).run() # Execute QAOA simulation

QAOAが終わりました。たったこれだけ。。

blueqatは、このようにコーディングが圧倒的に簡単化できますので、良いですね。

結果を可視化する関数を書きます。

これは状態 $|q \rangle$ の各成分の絶対値(の二乗)を表示します。


# プロットする
import matplotlib.pyplot as plt
import numpy as np
%matplotlib inline

def myplot_histogram(result,n):
    probs = np.array(list(result.probs.values()))
    ## z方向に射影測定した時に得られる可能性があるビット列
    z_basis = [format(i,"b").zfill(n) for i in range(probs.size)]

    plt.figure(figsize=(20, 10))
    plt.xlabel("states")
    plt.ylabel("probability(%)")
    plt.bar(z_basis, probs*100)
    plt.show()


myplot_histogram(result,4)

<Figure size 1440x720 with 1 Axes>

$(1,0,1,0)$ と $(0,1,0,1)$ が大きいことが分かります。

確かに問題が解けています。

たまにQAOAでうまく解けないことがありますので、その場合は何度か実行してみてください。

2つの解が同時に求まったことになりますが、実はこれは $|q \rangle$ が先に述べた「重ね合わせ状態」というのになっています。

答えが複数ある時、量子計算の結果として　答えのの重ね合わせ状態が得られる　ということは、よく起きます。

このあたりも、古典計算と少し違うところですね。

色々いじってみる

せっかくなので少し遊んでみましょう。ラウンド数 $p$ を減らすとどうなるでしょうか。


p = 1 # number of round
ansatz = vqe.QaoaAnsatz(H, p) #trial (parametrized) circuit
result = vqe.Vqe(ansatz).run() # Execute QAOA simulation
myplot_histogram(result,4)

<Figure size 1440x720 with 1 Axes>

解ではない状態が育ってきてしまいましたね。

QAOAの課題

このように、QAOAは量子コンピュータで組み合わせ最適化問題を解けるアルゴリズムです。

数値最適化に落とし込むんでいるので、多少雑音があっても動きます。

現状の量子コンピュータは雑音が大きいため、このアプローチは確かに魅力的です。

ただ、round数 $p$ を増やしたり（回路が長く、複雑になる）、解く問題のスケールを大きくしたりする（必要な量子ビット数が増える）と QAOAであっても実行が厳しくなってきます。

例えば、湊さんの

Googleの最新SycamoreプロセッサでのQAOA組合せ最適化問題の論文の解説

https://qiita.com/YuichiroMinato/items/3aa39b335450789db050

などを参照して論文を読んでみるとよいかと思います。

まとめ

ゼロからQAOAを頑張って説明してみました。

簡単化のために扱っていない事項も多々ありますが、ご容赦ください。