common.title

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

量子熊 2 years ago

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

5

QAOAとは何か

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

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

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

組み合わせ最適化問題

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

例えば、

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

image.png

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

image.png

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

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

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

q|q \rangleに作用する(うまい)2n×2n2^{n} \times 2^{n}行列HHを考えて、qHq \langle q|H|q \rangleと表現できます。

image.png

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

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

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

量子

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

状態とコスト

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

次にコストCCを考えます。

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

image.png

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

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

コスト最小化

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

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

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

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

いかなる量子状態も、

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

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

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

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

qUq|q \rangle \to U|q \rangle

と表されます。

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

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

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

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

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

U(θ)=(cos(θ2)sin(θ2)sin(θ2)cos(θ2)) 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)

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

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

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

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

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

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

image.png

QAOA

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

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

  1. 適当な量子(初期)状態 qinit|q_{init} \rangle を用意する。

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

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

qinitq=U(βp)U(γp),....,U(β1)U(γ1)qinit|q_{init} \rangle \to |q \rangle = U(\beta_{p})U(\gamma_{p}), ...., U(\beta_{1})U(\gamma_{1})|q_{init} \rangle

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

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

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

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

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

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

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

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

image.png

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

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

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

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

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

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

image.png

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

外部サイト

(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)(1,0,1,0)(0,1,0,1)(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|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>output

image.png

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

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

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

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

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

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

色々いじってみる

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

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

image.png

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

QAOAの課題

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

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

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

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

例えば、湊さんの

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

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

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

まとめ

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

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

量子熊

@Kuma

Let's make everything quantum.

About us | Terms of Service | © 2022, Copyright © 2022, blueqat Inc. All rights reserved