はじめに

従来の計算機では解くことが難しい組合せ最適化問題を量子コンピュータで解くことで、様々な社会問題が解決されると期待されています。その解法として、量子アニーリング方式と量子ゲート方式があります。前者は、量子断熱アルゴリズム（QAA: Quantum Adiabatic Algorithm）[1][2]、後者は量子近似最適化アルゴリズム（QAOA: Quantum Approximate Optimization Algorithm）[3]に基づいて最適化計算が実行されます。最近では、どちらの方式にも属さない中性原子配列を用いた変分量子断熱アルゴリズム（VQAA: Variational Quantum Adiabatic Algorithm）が提案されており、注目を集めています[4]。いずれの手法も、初期状態に対して何らかの量子力学的操作を施すことで、最適解を得ることを目的としています。 この記事では、まずQAOAにおける具体的なゲート操作について説明します。次に、QAOAとQAA（量子アニーリングのアルゴリズム）との関係を説明します。最後に、簡単な問題を通して、QAOAが比較的少ないゲート操作で最適解を探索する様子をQniを用いて示します。

QniはTIS株式会社が開発したブラウザで動作するリアルタイム量子コンピュータシミュレータです。TISでは量子コンピュータ未経験のエンジニアを対象とした量子コンピュータチュートリアルを公開しています。このチュートリアルでは「量子重ね合わせ」や「量子もつれ」といった量子プログラミングに不可欠な概念と、その基本的な使い方をQniを用いたハンズオンを通して学べます。是非ご活用ください。

QAOAにおける変分試行状態と量子アニーリングによる状態変化

ここでは、ゲート操作で得られるQAOA変分試行状態の一般的な表式について説明します。次に、量子アニーリングの確率過程は、QAOAにおける特別なゲート操作に該当することを示します。

QAOAにおける変分試行状態

ゲート方式による組み合わせ最適化問題に対する解法として、QAOAが提案されています。QAOAでは、2p個のパラメータ{βl,γl}を割り当てられた量子回路によって量子状態|Ψp({βl,γl})>が生成されます。この模式図が図1になります。ここで、位相分離演算子UP(γl)とミキシング演算子UM(βl) は、一般に以下の形で書けます。
UP(γl) = exp(-iγlHP)
UM(βl) = exp(-iβlHM)
ここで、HPはコスト関数をマッピングしたイジングモデルのエネルギー関数、HMは通常以下の形を取ります。 HM＝-ΣjXjここで、Xjはj番目の量子ビットに作用するパウリX行列です。ここで生成される量子状態に対してサンプリングを行うことでコスト関数の期待値が次式によって求まります。
Fp({βl,γl})=<Ψp({βl,γl})|HP|Ψp({βl,γl})>
この期待値を最小にするように、2p個のパラメータを調整することで、組み合わせ最適化問題に対する最適解、あるいはその近似解を得ます。この近似の精度はpの値を大きく取ることで向上することが知られています[3]。

図1. QAOAにおける変分試行状態（引用元量子ゲート方式による最適化アルゴリズム)

量子アニーリングにおける状態変化

組み合わせ最適化問題に対する解法として提案された量子アニーリングは、初期状態として準備した量子状態の時間変化を追うことで最適解を求めるように設計されています。この時間変化は、実時間をt、実行時間をTとして、以下のハミルトニアンによって記述されます。
H(t) = (t/T)HP + (1 – t/T)HM
ここで、ハミルトニアンとは量子系のエネルギー関数です。t=0における初期状態(H|0>)⊗Nは、HMの最低エネルギー状態です。これはあらゆる組み合わせのパターン（古典状態）を重ね合わせた量子状態に対応します(図2.左図)。上式に従ってハミルトニアンを十分にゆっくりと変化させると、t=Tにおいて要求通りHPの最低エネルギー状態が得られます（図2.右図）。


図2. 量子断熱時間発展（引用元量子アニーリングの解説)

ゲート操作による量子アニーリング

量子アニーリングには回路の概念が存在しません。そこで、量子回路上で量子アニーリングを実現するために、実行時間Tを微小な時間単位に分割することを考えます。この分割数をpとすると、量子状態の時間変化は演算子UM(βl)とUP(γl)の交互作用で表現できるため、図1の量子回路で計算できます。ここで、βlとγlは以下の形を取ります。
βl = [2p-(2l-1)]T/2p2
γl= (2l-1)T/2p2
このように、QAOAは量子アニーリングを包含する枠組みとなっています。特にpを十分に大きくとることで、量子アニーリングと同様に最適解を得ることが理論的に保証されています。ここで導入した連続時間を離散化する近似についてはC.Wlfeによる記事がわかりやすいです。図3にゲート操作による確率分布の変化を例示します。これは量子アニーリングにおける確率分布の時間変化と対応します。詳しくは次章の「簡単な問題」を参照してください。

図3. 確率分布の時間変化。ここで、t/Tは量子アニーリングの実行時間に対する経過時間を表す。

簡単な問題

組み合わせ最適化問題におけるコスト関数をマッピングしたイジングモデルHPは、相互作用項と局所ポテンシャル項で構成されます。これまでの議論はHPの形によらないものでした。以下では、ゲートが煩雑になることを避けるため、相互作用項を除いた以下の簡単な問題について考えます。
HP＝Z0-Z1+Z2-Z3
これは24=16の古典状態に対して自明な解|0101>を持ち、次式を満たします。
HP|0101>=-4|0101>
この問題を通して量子アニーリングとQAOAが最適解を得る様子を示します。相互作用がある場合のQAA回路についてはblueqat社による記事を参考にしてください。

p=5のゲート操作と量子アニーリング

ここでは、簡単な問題に対して量子アニーリングを実行した結果を示します。量子アニーリングの実行時間をT=2πと設定し、QAOAブロックUP(γ)UM(β)の数をp=5とした場合の量子回路を図4に示します。ゲート操作とX、Z量子回転ゲートとの対応は以下の通りです。
UM(βl)＝Πj RXj[-2βl]
UP(γl)＝Πj RZj[(-1)j2γl]
ここで、jは量子ビットのラベルで回路図の上から順番にj=0, 1, 2, 3の値を取ります。図4から、時間の経過と共に量子状態が|0101>の最適解に向けて漸近する様子が確認できます。図3は、ここで計算した確率分布の時間変化とコスト関数を同時にプロットした結果になります。図4の量子回路はQniで描画しています。ブラウザで動作するQniでは、マウスオーバーによってゲート操作の任意の段階（青線）における量子状態を下のパネルで確認できます。パネルに描かれた円はビット列に対する重み（水色の円）と位相（半直線）を表したものです。また、ブロッホ球を回路に挿入することによって、量子ビットの局所状態（球上の赤点）を確認できます。是非、ご自身でマウスを動かしてみてください。

図4. p=5のQAOAで表現した量子アニーリングによる時間発展（Qniによる描画）

p=1のQAOAによる最適化計算

次に、QAOAで最適解を探索する様子を示します。ここでは、量子回路のQAOAブロックを1つに制限したp＝1の場合について考えます。QAOAではエネルギー期待値F1(β, γ)を最小にする(β, γ)を探索します。図5にF1(β, γ)を示します。図5の代表的な点(β, γ)=(a) (π/12, π/12)、(b) (π/6, π/6)、(c) (π/4, π/4)について、対応する量子回路とF1(β, γ)の計算結果を図6に示します。図5と6からp=1の近似の範囲内で(β∗, γ∗)=(π/4, π/4)が最適解を与えることがわかります。対応するビット列は以下の通りです。
|Ψ1(β∗, γ∗)>=|0101>
明らかにこの結果はHPに対する厳密な最適解です。今回の簡単な問題では、少ないゲート操作で最適解を発見できました。このように、p=1で最適解が得られるQAOAは決定論的QAOAと呼ばれます。この問題のクラスにおいては、量子アニーリングや古典的なシミュレーテッドアニーリングと比較して、QAOAによって効率良く解を発見できることが知られています[5]。一方、p=1で解が得られない問題に対しては、p≥1の量子回路で生成された量子状態に対するビット列の分布から、統計的手法によって最適解を推定する必要があります。

図5. p=1のQAOAで求めたイジングモデルのエネルギー期待値F1(β, γ)

図6. p=1の変分試行状態（Qniによる描画）

まとめ

この記事では、QAOAにおけるゲート操作について説明しました。量子アニーリングにおける状態変化はQAOAにおける特別なゲート操作に該当することを明示しました。また、量子アニーリングは、時間経過と共に量子状態が最適解に漸近する手法であることを示しました。一方、QAOAは時間経過を辿るのではなく、量子回路の深さを制限し、古典的な手法でEp({βl, γl})を最小とするパラメータセット{βl∗, γl∗}と対応するビット列|Ψp({βl∗, γl∗})>を探索する手法であることを示しました。次回はQAOAの量子古典ハイブリットアルゴリズムの具体的な計算手順を紹介する予定です。

[1]: E. Farhi, J. Goldstone, S. Gutmann, and M. Sipser. “Quantum computation by adiabatic evolution” arXiv:quant-ph/0001106 (2000).

[2]: T. Kadowaki and H. Nishimmori. “Quantum annealing in the transverse Ising model” Phyical Review E, 58, 5355 (1998).

[3]: E. Farhi, J. Goldstone, and S. Gutmann. “A quantum approximate optimization algorithm” arXiv:1411.4028 (2014).

[4]: S. Ebadi, A. Keesling, M. Cain et al. “Quantum Optimization of Maximum Independent Set using Rydberg Atom Arrays” arXiv: 2202.09372 (2022).

[5]: M. Streif and M. Leib. “Forbidden subspaces for level-1 quantum approximate optimization algorithm and instantaneous quantum polynomial circuits” Phyical Review A, 102, 042416 (2020).