Recursive QAOA のアルゴリズム

Recursive QAOA[1]（以下、RQAOA）は、深さの浅い Ansatz 回路による QAOA を繰り返し実行し、段階的に問題サイズを縮小しながら最適解を特定する手法です。通常の QAOA で問題となる回路の深さの制約を緩和し、大規模な問題への適用を目指します。通常の QAOA の理論についての解説は QAOA 理論 を参照してください。

注釈

RQAOA は制約付きの問題には対応していません。制約がある場合には、ペナルティ項を導入して制約なし問題へ Amplify SDK が自動で変換します。詳細は制約条件とペナルティ関数を参照してください。

RQAOA の手続き

RQAOA は次のような手続きで実行されます。

  • Step 1: 深さの浅い QAOA を利用した変数削減サイクル

    • 手順1: 浅い回路を用いて QAOA を実行する

    • 手順2: QAOA の結果を用いて消去する変数を決定する

    • 手順3: 変数を削減して新しい問題を構成する

  • Step 2: 変数を十分な数削減した問題の最適解の発見

  • Step 3: 変数を削減した問題の解から元の問題の最適解の導出

../../_images/rqaoa_flowchart.drawio.ja.svg

RQAOA の詳細

以下ではより詳しく各ステップで行われる手続きについて見ていきます。

各項目の説明に際して、簡単な例としてイジング関数

\[f(z) = 4z_0z_1 +3z_1z_2 + 2z_0 + z_2\]

を最小化する問題を考えていきます。

Step 1. 変数削減サイクル

RQAOA の中核をなすステップです。変数削減サイクルでは以下の手順を問題のサイズ（変数の数）が十分小さくなるまで繰り返し実行します。

  1. イジング変数で構成された目的関数 \({f}(z)\) に対して、深さの浅い（\(p = 1\) などの）Ansatz 状態 \(\ket{\psi(\boldsymbol{\theta})}\) を用いた QAOA を実行し、その終状態 \(\ket{\psi}\) を計算基底で測定する。

  2. 測定結果をもとに、目的関数 \({f}(z)\) の各項の期待値を求め、期待値の絶対値が最も大きい項に注目する。ここで、その期待値の正負に応じて、\(\sigma = 1\) または \(\sigma = -1\) と定義する。

  3. 注目した項に対して、 \({\rm 項}_{\mathrm{max}}= \sigma\) という関係を導入する。この関係をもとに変数を消去して新しい目的関数 \({f}_{\mathrm{new}}(z)\) を定義する。

より詳細にそれぞれの手順を解説します。

1. 浅い回路での QAOA 実行

RQAOA の繰り返し手順の最初では、与えられた最適化問題を浅い回路による QAOA を用いて近似的に解き、その終状態 \(\ket{\psi}\) の測定結果を取得します。

測定結果はこの先の手順でどの変数を削除するのかにのみ用いられるため、厳密な最適解を返す必要はありません。これが浅い Ansatz 回路の使用を許容できる理由になっています。

2. 消去する変数の決定

手順1で得られた測定結果から、目的関数の各項の中で「最も値が確からしい」項を決定します。そのために各項の期待値を計算します。

例

\[{f}(z) = 4z_0z_1 +3z_1z_2 + 2z_0 + z_2\]

を見てみましょう。この場合には、目的関数をハミルトニアンに変換したうえで、各項の変数部分に対応する Pauli \(Z\) 演算子の期待値 \(\braket{\psi|Z_0Z_1|\psi}\)、\(\braket{\psi|Z_1Z_2|\psi}\)、\(\braket{\psi| Z_0 |\psi}\)、\(\braket{\psi| Z_2 |\psi}\) をそれぞれ計算します。変換の詳細はQAOA理論を参照してください。

最も期待値の絶対値が大きかった Pauli 演算子を \(Z_{\mathrm{max}}\) とします。 そして、\(Z_{\mathrm{max}}\) に対応する項を \({\rm 項}_{\mathrm{max}}\) として、その値を \({\rm 項}_{\mathrm{max}} = \sigma \in \{-1,1\}\) で定めます。 もし \(\langle \psi|Z_{\mathrm{max}}|\psi\rangle\) が正なら \(\sigma = 1\) と、反対に \(\langle \psi|Z_{\mathrm{max}}|\psi\rangle\) が負なら \(\sigma = -1\) と定めます。定義より \(-1 \leq \langle \psi|Z_{\mathrm{max}}|\psi\rangle \leq 1\) です。

多項式

\[{f}(z) = 4z_0z_1 +3z_1z_2 + 2z_0 + z_2\]

で、例えば

\[ \begin{align}\begin{aligned} \begin{aligned} \braket{\psi|Z_0Z_1|\psi} &= -0.4\\\braket{\psi|Z_1Z_2|\psi} &= -0.6\\\braket{\psi|Z_0|\psi} &= -0.3\\\braket{\psi|Z_2|\psi} &= -0.2 \end{aligned} \end{aligned}\end{align} \]

という期待値計算の結果が得られたとしましょう。 この時、\(Z_{\mathrm{max}} = Z_1Z_2\) であり、\({\rm 項}_{\mathrm{max}} = z_1z_2\) となります。 \(\braket{\psi|Z_1Z_2|\psi} = -0.6<0\) であることから、\(\sigma = -1\) と定め、\({\rm 項}_{\mathrm{max}} = \sigma\)、つまり \(z_1z_2 = -1\) という関係式が得られます。

この操作は次のような意味を持ちます。\(Z_{\mathrm{max}}\) の期待値の絶対値が最も大きいというのは、その対応する変数 \({\rm 項}_{\mathrm{max}}\) の値が \(+1\) あるいは \(-1\) に最も近かったということです。この意味で、もし目的関数の各項の値をどれか一つだけ決め打つのなら、\({\rm 項}_{\mathrm{max}}\) が一番もっともらしい選択であるということになります。そこで、\(Z_{\mathrm{max}}\) の期待値の正負によってその項の値を \({\rm 項}_{\mathrm{max}} = 1\) または \({\rm 項}_{\mathrm{max}} = -1\) と決め打ち、問題のサイズを小さくしていくのです。

3. 変数削減

手順2で導入した \({\rm 項}_{\mathrm{max}} = \sigma\) という関係を利用して変数削減を行います。

\({\rm 項}_{\mathrm{max}}\) が一次の場合

この場合、ある非負整数 \(i\) を用いて \({\rm 項}_{\mathrm{max}}\) = \(z_i\) と表され、「\(z_i\) の値が一番確からしく \(\sigma\) になる」ということになります。そこで、元のハミルトニアン \(H\) において \(z_i = \sigma\) と置き換えて新しい目的関数 \({f}_{\mathrm{new}}\) を得ます。

\({\rm 項}_{\mathrm{max}}\) が二次以上の場合

例

\[ {f}(z)= 4z_0z_1 +3z_1z_2 + 2z_0 + z_2\]

を再び考えます。

手順2で設定したように、\(z_1z_2 = -1\) と定まったとします。 これはすなわち、\(z_1\) と \(z_2\) の間に \(z_1 = -z_2\) という関係が成り立つことを示唆しています。そのため、元の目的関数 \({f}(z)\) に、\(z_1 = -z_2\) を代入することによって

\[{f}_{\mathrm{new}}(z) = -4z_0z_2 + 2z_0 + z_2 -3\]

が得られます。イジング変数 \(z \in \{-1,1\}\) に対して、\(z^2 = 1\) であることに注意してください。結果的に、変数が一つ減った新しい目的関数が得られていることが分かります。

この例では二次の問題を扱っていますが、より高次の項に注目して変数を削減する場合も同様の手順で行います。一般の場合について詳しくは参考文献の Appendix C を参照してください。

手順1-3の結果、新しい目的関数 \({f}_{\mathrm{new}}(z)\) の変数の数が十分小さい場合にはサイクルを抜け出します。そうでない場合には、\({f}_{\mathrm{new}}(z)\) を用いて再度手順1から変数を削減します。

Step 2. 変数削減後の最適化問題の求解

変数削減サイクルを繰り返して問題のサイズが十分小さくなったら、総当たりなどで最適解を求めます。

ここでも例を考えてみましょう。

Step 1 で見た通り、

\[{f}(z) = 4z_0z_1 +3z_1z_2 + 2z_0 + z_2\]

において、\(z_1z_2 = -1\) の関係式に基づいて

\[{f}_{\mathrm{new}}(z) = -4z_0z_2 + 2z_0 + z_2 -3\]

という新しい目的関数が得られたとします。総当たりの結果、\({f}_{\mathrm{new}}(z)\) を最小化する値として、

\[(z_0, z_2) = (-1,-1)\]

という解を得ます。

Step 3. 元の問題の最適解の導出

RQAOA の最後のステップでは、Step 2 で得られた変数削減後の問題の解から、元の最適化問題 \({f}(z)\) の最適解を構成します。この最適解の導出は、Step 1 の手順3で得られた変数削減のための関係式 \({\mathrm{項}}_{\mathrm{max}} = \sigma\) を逆向きにたどっていくことで行われます。

Step 2 では、変数削減後の問題 \({f}_{\mathrm{new}}(z) = -4z_0z_2 + 2z_0 + z_2 -3\) の最適解 \((z_0, z_2) = (-1,-1)\) を得ました。このステップでは、変数削減の際に用いた

\[z_1 = -z_2\]

に従って \(z_1\) の値を導出します。今回のケースでは、

\[z_1 = 1\]

と求まります。こうして、元の最適化問題 \({f}(z) = 4z_0z_1 +3z_1z_2 + 2z_0 + z_2\) の最適解として、

\[z = (z_0,z_1,z_2) = (-1,1,-1)\]

が得られます。

まとめ

このように、RQAOA は QAOA を繰り返し利用して段階的に最適化問題のサイズを削減することで最適解を計算する手法です。 アルゴリズム内で QAOA は最適解を計算するのではなく、あくまで削減対象の変数を決定することに用いるため、最適解を計算する時よりも浅い回路を使用できることが期待されます。

通常の QAOA では、大規模な問題を解く際に深さの大きい回路が必要になり計算時間が増大してしまうことや、回路の大きさやハードウェアノイズなどが原因で QAOA におけるパラメータの更新がうまくいかなくなってしまう現象が指摘されていました（後者の現象は "Barren Plateau" と呼ばれて研究されています [2]）。

RQAOA では、量子コンピュータを浅い回路での QAOA のみに用いることから、こうした問題を回避しながら最適化問題の解がより精度良く効率的に得られることが期待されます。