QAOAアルゴリズムの量子回路の仕組みを理解する

量子コンピュータのアルゴリズムを勉強しているとQAOAという手法をよく見かけますが、量子回路の仕組みを理解するのはなかなか難しいですよね。

この記事ではQAOAアルゴリズムの基礎として量子回路の成り立ちについて紹介します。

QAOAアルゴリズムとは

QAOA(Quantum Approximate Optimization Algorithm)とは組み合わせ最適化問題をエネルギー最小化問題として解決するためのアルゴリズムです。

NISQアルゴリズムとして量子計算による高速化は保証されないものの、シンプルな構造を持ち現状のハードウェアでも実行が可能です。

QAOAのベースとなるアイデアは量子断熱計算

具体的な量子回路の構造を説明する前に、QAOAのベースとなっている量子断熱計算という考え方を理解しましょう。

量子断熱計算とは、問題の解が物理系のハミルトニアン$H$の基底状態であるときに、自然現象を使って初期状態から解となる基底状態を得る手法です。

この手法は量子アニーリングと共通点が多く、代表例であるD-Waveマシンは同じように自然現象の量子効果を使って最適化問題を解くように実装されています。

という疑問が浮かぶと思いますが、実は下のような関係でつなげることが出来るのです。

つまり、組み合わせ最適化問題を数理モデル化したときに、数学的に等価な物理系と対応させることができれば量子断熱計算を利用することで解を求めることが出来るということです。

最適化問題の多くはQUBOという数理モデルで表すことができ、これはイジングモデルという物理系と等価であることが知られています。

QUBOとイジングモデルの関係については下の記事を参考にしてください。

QAOAアルゴリズムの量子回路の仕組みを理解する

ベースの考え方を理解したところで本題の量子回路の仕組みに移りましょう。まずQAOAアルゴリズムは以下の手順で計算されます。

アルゴリズムの全体像は以下のようになります。

初期状態の準備

初期状態$|s\rangle$および初期ハミルトニアン(ミキサハミルトニアンとも呼びます)$H_X$は決まったものである必要は無く、効率的な計算となる適切なものを用意できればよいです。

一般的には初期ハミルトニアンは$X$ゲートとその固有状態の$|+\rangle$が利用されます。

H_X=\sum^n_{j=1}X_j

ユニタリゲートの構築

量子断熱計算を行う量子ゲートを構築します。量子断熱計算ではハミルトニアンは下のように表すことができます。

H(t)=(1-\frac{t}{T})H_X+\frac{t}{T}H_C

状態の時間発展はシュレーディンガー方程式から計算することができます。

この計算は全体の時間$T$を微小区間$\Delta t$に分け、その範囲でハミルトニアンは一定であると近似することで手法がよくとられます。

\begin{aligned}
|\psi(t)\rangle&=e^{iH(t)t}|s\rangle \\
&= e^{i\Delta tH(T,T-\Delta t)}e^{i\Delta tH(T-\Delta t, T-2\Delta t,)}\cdots e^{i\Delta tH(\Delta t, 0)}|s\rangle \\
&=\Pi_j e^{i\Delta tH(j\Delta t, (j+1)\Delta t)}|s\rangle \\
&=\Pi_j e^{-i\beta_jH_X}e^{-i\gamma_jH_C}|s\rangle
\end{aligned}

計算式を変換していくことでアルゴリズムの説明で登場したパラメータを2つもった量子ゲートが必要な理由がわかりました。

エネルギー最適化問題の計算

アルゴリズムの手順3以降は問題の数理モデルと対応する物理系のハミルトニアン$H_C$のエネルギー最小化問題の計算を行っています。

この部分は他のアルゴリズムと共通でハミルトニアンの期待値$\langle \beta, \gamma|H_C|\beta, \gamma\rangle$からエネルギーがわかるので最小化するようにパラメータを調整するという手順となります。

まとめ

この記事ではQAOAアルゴリズムの量子回路の構造について、ベースの量子断熱計算のアイデアを踏まえて紹介しました。

詳細はこちらの参考文献を勉強するとより理解が深まります。量子コンピュータを勉強する方はぜひ一読することをおすすめします。