yenomotoです。QAOAについての理論、情報について調べてみました。
こんな人に読んでほしい
・ぶっちゃげQAOAって何よ、を知りたい人
・QAOAをこれから勉強するにあたり、とっかかりの情報が欲しい人
・量子コンピュータに詳しい方 ※ご指摘をいただきたいです・・・。
QAOAってなに？
Quantum Approximate Optimazation Algorithm (QAOA)「量子近似最適化アルゴリズム」
「量子ゲート方式」の量子コンピュータで組み合わせ最適化問題を解くアルゴリズムです。[1]
組み合わせ最適化問題を物理モデルであらわし、
物理モデルが安定的な状態＝エネルギーが低い状態を探します。
何の役に立つの？
QAOAで解く組み合わせ最適化問題としてよく扱われるのはネットワーク経路を分割する「Maxcut問題」です。
「Maxcut問題」は定式化の理論が確立されており、
グラフがQAOAで扱いやすいため実装例が多く報告されています。
現実世界のMaxcutの活用方法としては、領域抽出やノイズ除去などの画像処理が挙げられます。
このほか、物理モデル化＝定式化が可能なものは理論上、QAOAにて解を求めることが可能です。
・巡回セールスマン問題
・スケジューリング問題
etc・・・
理論
（前提）
量子状態∣ψ>|ψ>∣ψ> は、演算子ハミルトニアンHHH を作用させることで、
・エネルギー固有値E0E_0E0
・エネルギー固有値に対応する固有状態
が得られます。
このエネルギー固有値が最も小さい固有状態を、「基底状態」と呼びます。
これを式で表すと
H∣ψ>=E0∣ψ>H|ψ>=E_0|ψ>H∣ψ>=E0∣ψ>
<ψ∣H∣ψ>≧E0<ψ|H|ψ>≧E_0<ψ∣H∣ψ>≧E0
量子状態∣ψ>|ψ>∣ψ> → 扱う系の状態
演算子ハミルトニアンHHH → 求めたい組み合わせ最適化問題
H∣ψ>H|ψ>H∣ψ> の基底状態 → 組み合わせ最適の状態
こんな感じでH∣ψ>H|ψ>H∣ψ>の基底状態を探そう！というのが「固有値問題」です。
QAOAは「固有値問題」を解くアルゴリズムとして提供されています。
（QAA）
QAOAで計算を行う流れはQAA：量子断熱計算に基づいています。
「自明なハミルトニアンからゆっくり時間を発展させて
目的のハミルトニアンに変化させていけば目的の状態を得られる」という理論です。
上記で出てきた求めたい組み合わせ最適化問題にあたるハミルトニアンをHcostH_{cost}Hcost とします。
一方で初期状態とするエネルギー固有値が自明なハミルトニアンをHrefH_{ref}Href とします。
時間をttt をし、 0→TTT の間で発展させると時間tttにおけるハミルトニアンは
H(t)=(1−t/T)Href+t/THcostH(t)=(1−t/T)H_{ref}+t/TH_{cost}H(t)=(1−t/T)Href+t/THcost
であらわせます。
（QAA→QAOA）
ハミルトニアンH(t)の式は、シュレーディンガー方程式の解として
i∂/∂t∣ψ>=H(t)∣ψ>i∂/∂t∣ψ>=H(t)∣ψ> i∂/∂t∣ψ>=H(t)∣ψ>
として書くことができ、
時間順積分したものが以下のようになる
U(t)=exp(−i∫H(t)∂t)=exp(−iH(t)∂t)exp(−iH(t−∂t)∂t)････exp(−iH(∂t)∂t)exp(−iH(0)∂t)U(t)=exp(−i∫H(t)∂t)=exp(−iH(t)∂t)exp(−iH(t−∂t)∂t)････exp(−iH(∂t)∂t)exp(−iH(0)∂t)U(t)=exp(−i∫H(t)∂t)=exp(−iH(t)∂t)exp(−iH(t−∂t)∂t)････exp(−iH(∂t)∂t)exp(−iH(0)∂t)
時間依存のハミルトン演算子はトロッター分解を用いて
exp(−iH(∂t)∂t)≈exp(−i(1−t)∂tHref)exp(−it∂tHcost)exp(−iH^(∂t)∂t)≈exp(−i(1−t)∂tH_{ref})exp(−it∂tH_{cost})exp(−iH(∂t)∂t)≈exp(−i(1−t)∂tHref)exp(−it∂tHcost)
と表現できます。
※式を簡略化するため、トロッター数（分割する次数）を1としています。
さらに時間発展するパラメータをそれぞれ
γ=t∂tγ=t∂t γ=t∂t
β=(1−t)∂tβ=(1−t)∂tβ=(1−t)∂t
で表現すると
U(t)=exp(−iβpHref)exp(−iγpHcost)････exp(−iβ1Href)exp(−iγ1Hcost)U(t)=exp(−iβ_pH_{ref})exp(−iγ_pH_{cost})････exp(−iβ_1H_{ref})exp(−iγ_1H_{cost})U(t)=exp(−iβpHref)exp(−iγpHcost)････exp(−iβ1Href)exp(−iγ1Hcost)
となります。pは時間発展tをp回のステップで再現する次数です。
γ=γ1,････,γp, β=β1,････,βpγ=γ_1,････,γ_p, β=β_1,････,β_p γ=γ1,････,γp, β=β1,････,βp と1~ｐの次数のパラメータ分ステップを実施するとし、
HrefH_{ref}Href に対応する初期状態∣s>|s>∣s> にU(t)U(t)U(t) を作用させることにより、
∣γ，β>|γ，β>∣γ，β>
を得ます。
＜γ，β｜Hcost∣γ，β>＜γ，β｜H_{cost}|γ，β>＜γ，β｜Hcost∣γ，β>
の期待値を得ることで、それを提供する最適なγ，βを求めます。
(QAOAの量子回路イメージ)
これまで出た式をQAOA回路に割り当てます。
QAOA回路の例は、Regettiの論文[2]が上記数式と対応がつけやすいです。
①量子ビットを重ね合わせ、∣s>=∣+>1∣+>2...∣+>n∣s>=∣+>_1∣+>_2...∣+>_n∣s>=∣+>1∣+>2...∣+>nの初期状態を作る
②∣γ，β>=exp(−iβHref)exp(−iγHcost)∣ψ>|γ，β>=exp(−iβH_{ref})exp(−iγH_{cost})|ψ> ∣γ，β>=exp(−iβHref)exp(−iγHcost)∣ψ> の状態を作成
※∣ψ>|ψ>∣ψ>…1回目は|s>、それ以降は前に行った③測定を行った状態である
③ 測定
④ ①(②)～③を複数回行い期待値<γ,β|H^cost|γ,β> を求める
⑤ 古典PCでベイズ最適化を行い、次の(γ,β)にして②～④を再度行う
以上をp回繰り返すことで、最適解を得ます。
図のDriver Unitaryはexp(−iβHref)exp(−iβH_{ref})exp(−iβHref)部分 であり
初期状態|s>、
初期状態のエネルギー固有値σxσ_xσx に対応しています。
一方Cost Unitaryはexp(−iγHcost)exp(−iγH_{cost})exp(−iγHcost) であり、
観測対象の状態∣γ，β>∣γ，β>∣γ，β>
求めたいエネルギー固有値＜γ，β｜Hcost∣γ，β>＜γ，β｜H_{cost}|γ，β>＜γ，β｜Hcost∣γ，β>に対応しています。
（理論に関しては参考文献[3]の構成を参考に記載しています。
そのほか、[4][5][6]より情報を引用しています。）
比較
古典アルゴリズムや、解法がQAOAに近いVQE,量子アニーリングとの差分をみてみます。
（vs 古典アルゴリズム）
QAOAは計算量がビット数nではなく、計算の繰り返し回数p、トロッター数ｍで決まります。
これによりQAOAはビット数ｎが大きくなっても、古典アルゴリズムのような計算量の爆発が
起きません。
これがQAOAの「大きな最適化問題も比較的短時間で解ける」という強調ポイントの根拠になっています。[1]
（vs VQE）
同じところはコストハミルトニアンHcostH_{cost}Hcostを使った固有値問題であること
違うところはVQEは時間発展の概念がないところ、ハミルトニアンを作る方法が違うところです。
QAOAはイジングモデル、という組み合わせを配列で表現したものを使用するのに対し、
VQEは実在する分子のスピンを扱う量子化学のプログラムを使います。
※VQEについてはこちらのブログでもとりあげています。
（vs 量子アニーリング)
同じところは多く、固有値問題を扱うところ。QAAを基にしているところ。
イジングモデルでハミルトニアンHcostH_{cost}Hcostを作るところです。
違うところはQAOA=デジタル、アニーリング=アナログであるところで
QAAの時間発展をステップに分けて実現するか、連続的に行うかが主な違いのひとつです。[7]
何の役に立つの？（2回目）
「物理モデル化＝定式化が可能なものは『理論上』、QAOAにて解を求めることが可能です。」
と書きましたが現時点でアプリケーションへの応用が可能か？についてです。
これは残念ながら「No」です。
・量子ゲートで使える量子ビット数が少ない
・精度を上げるために反復回数pを多くすると、量子回路が長くなる→ノイズが大きくなる
QAOAに限らず、量子コンピューティングハード/ソフト両面では日々改善されているので、
今はまだ「今後に期待」といったところでしょうか。
投稿を終えて
前回のブログで調べてみたVQEは物理モデルそのものを扱うのに対し、
QAOAは問題を物理モデルに落とし込み時間発展させるため難易度が高い印象を受けました。
時間発展は実用面で一歩進んでいる量子アニーリングにも絡む理論なので、
この機会を皮切りに学びを深めたいです。
■参考文献
[1]「A Quantum Approximate Optimization Algorithm」
https://arxiv.org/pdf/1411.4028.pdf
[2]「Unsupervised Machine Learning on a Hybrid Quantum Computer」
https://arxiv.org/pdf/1712.05771.pdf
[3]「QAOA - ゲート式量子コンピューターで最適化問題を解く近似アルゴリズム」
https://qiita.com/snhrhdt/items/ae55a94b25c06142528a
[4]「量子ゲートで組合せ最適化問題を解くQAOAの実装」
https://qiita.com/YuichiroMinato/items/a13ad99162e29de94f01
[5]「QAOA(Quantum Approximate Optimization Algorithm)」
https://qiita.com/KeiichiroHiga/items/88bf1cb601e7422b4bea
[6]「5-3. Quantum Approximate Optimazation Algorithm (QAOA): 量子近似最適化アルゴリズム — Quantum Native Dojo ドキュメント」
https://dojo.qulacs.org/ja/latest/notebooks/5.3_quantum_approximate_optimazation_algorithm.html
[7]「QAOA vs QA and SA」
https://qiita.com/snhrhdt/items/1f5415dca2a0be8e1040
[8]「QAOAのミキサーの機能と概要について簡単にまとめてみました。」