制約付き QAOA のアルゴリズム

最適化問題の中には、変数にある種の制約を課した下での最適値を求める、というものがあります。

例えば、イジング変数 \(z\) を用いた目的関数 \({f}(z) = 2 z_1 z_2 + z_0 + z_1 - z_2\) を、「 \(z_0\), \(z_1\), \(z_2\) のうち、ちょうど1個の変数だけが \(-1\) になる 」という制約の下で最小化したいとします。 もし変数に何も制約がなければ、この関数 \({f}(z)\) は \((z_0, z_1, z_2) = (-1, -1, 1)\) で最小値 \({f}(z) = -5\) を取ります。 しかし、この解は「 \(z_0\), \(z_1\), \(z_2\)のうち、ちょうど1個の変数だけが \(-1\) になる 」という制約を満たしません。このような制約の下では \((z_0, z_1, z_2) = (1, -1, 1)\) で最小値 \(f(z) = -3\) を取ります。

変数への制約は様々なものが考えられますが、上記の例で課したような制約は広く用いられます。

ちなみに、変数が \(\{0,1\}\) から成るバイナリ変数の場合には、ちょうど N 個の変数だけが \(1\) になる制約はしばしば N-HOT 制約と呼ばれます。 N-HOT 制約について詳しくは、Wikipedia: One-hot を参照してください。

注釈

ここでは、イジング変数から成る変数列に対して、ちょうど \(n\) 個の変数だけが \(-1\) になる制約についても N-HOT と呼びます。

ただし、Amplify SDK における one_hot()関数はpoly == 1として実装されています。 そのためイジング変数で one_hot 制約を定義するにはequal_to()関数で等式制約として表現する必要があります。

以下では「制約条件」といったとき、この条件を考えます。

Amplify では QAOA を実行する際に、自動で上記の N-HOT 制約が課された最適化問題を検出して、与えられた制約条件に応じた変数のグルーピングを行うことで探索空間を削減し、より効率よく解を求めることができます。自動検出を無効にすることもできます。詳細はQAOAの種別を参照してください。

N-HOT QAOA

ここでは、与えられた制約条件に対して変数のグルーピングを行うことでどのように最適解が得られるのかを説明します。

制約条件を扱えないソルバーで制約条件付きの最適化問題を解く際には、制約条件を満たす解を最適解とする (緩和) 多項式 \({g}\) とペナルティ係数 \(\lambda\) を与え、 \({f}' = {f} + \lambda {g}\) を解くことで制約条件の下での最適解を得ます。

例えば、上記の例のような、目的関数 \({f}(z) = 2 z_1 z_2 + z_0 + z_1 - z_2\) を、「 \(z_0 + z_1 + z_2 = 1\) 」という 等式制約の下で解きたいときは、\({g}(z) = (z_0+z_1+z_2 - 1)^2\) として、適切な \(\lambda\) を選ぶことで、所望の解を得ることができます。 詳しくは ペナルティ法 を参照してください。

一方、 N-HOT QAOA では制約条件を考慮した Ansatz を考えることで、与えられた最適化問題を「制約条件によって制限されたパラメーター空間内でハミルトニアンの最小の固有値と固有ベクトルを求める」問題に帰着させ、より効率的と期待される方法で問題を解きます。

解きたい最適化問題において、\(k\)個の独立した（制約する変数が互いにかぶらない）等式制約が与えられているとします。この制約条件の下で変数 \(z\) は \(z = (z^{(1)},z^{(2)},\ldots,z^{(k)},{z})\) のように \(k+1\) 個のグループに分けられます。ここで、\(z^{(1)}, \ldots, z^{(k)}\) は独立な等式制約に対応するグループで、\({z}\) は制約のない変数のグループです。

Ansatz は、 グループが \(k\) 個あるとき、 \(\ket{\psi(\boldsymbol{\theta})}=\ket{\psi_{\mathrm{group}, 1}(\boldsymbol{\theta}^{(1)})}\otimes\ket{\psi_{\mathrm{group}, 2}(\boldsymbol{\theta}^{(2)})}\otimes\cdots\ket{\psi_{\mathrm{group}, k}(\boldsymbol{\theta}^{(k)})}\otimes\ket{\psi_{\mathrm{ungroup}}(\boldsymbol{{\theta}})}\) のように各グループについて独立に量子回路が作用するように定義します。 このうち、 \(\ket{\psi_{\mathrm{ungroup}}(\boldsymbol{{\theta}})}\) では、独立な Pauli \(X\) 回転ゲート \(R_X(\theta)=\mathrm{e}^{i\frac{\theta}{2} X}\) を作用させます。

回路の概略を示すと下図のようになります。

グループの Ansatz 回路

各グループ \(i = 1,2,\ldots,k\) について Ansatz 回路 \(U(\boldsymbol{\theta}^{(i)})\) は次のように構成されています。

回路図中で 2 量子ビットゲート \(A(\theta)\) は下図のように CNOT ゲートと Pauli \(Y\) 回転ゲート \(R_Y(\theta) = \mathrm{e}^{-i\frac{\theta}{2} Y}\) で実現されます。

このゲート \(A(\theta)\) を行列表示すると

\[\begin{split} A(\theta) = \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & \sin\theta & \cos\theta & 0 \\ 0 & \cos\theta & -\sin\theta & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix} \end{split}\]

となります[1][2]。\(A(\theta)\) を計算基底に作用させたときの結果を見てみると、

\[ \begin{align}\begin{aligned} A(\theta)\ket{00} &= \ket{00},\\A(\theta)\ket{01} &= \sin\theta\ket{01} +\cos\theta\ket{10},\\A(\theta)\ket{10} &= \cos\theta\ket{01} -\sin\theta\ket{10},\\A(\theta)\ket{11} &= \ket{11} \end{aligned}\end{align} \]

となっており、入力が計算基底の時、出力された状態は、入力状態の持つ"1"の数を保存することが分かります。

グループの初期状態

各グループ \(i = 1,2,\ldots,k\) について、初期状態 \(\ket{\psi_{\mathrm{init}, i}}\) は「制約条件で課された \(-1\) の個数だけ"1"を持つ量子状態」に定めます。

注釈

QAOA 理論でも触れたとおり、1量子ビットの計算基底 \(\{\ket{0}, \ket{1}\}\) は Pauli \(Z\) 演算子の固有ベクトルであり、その固有値がイジング変数に対応します。具体的には、

\[\begin{split} \braket{0|Z|0} &= 1 \\ \braket{1|Z|1} &= -1 \end{split}\]

から \(\ket{0}\) が \(1\) に、\(\ket{1}\) が \(-1\) に対応します。

以下で解説する「制約条件で課された \(-1\) の個数だけ"1"を持つ量子状態」というのは、量子ビットのラベル"1"がイジング値 \(-1\) に対応することに留意して、イジング変数に対する制約条件を量子ビットに埋め込むことで得られる量子状態であると解釈されます。

ここで少し数学的な説明をします。グループ \(i\) に属する量子ビットの数を \(n_i\)、制約条件で課された \(-1\) の数を \(l_i\) とします。ここで、ビット列 \(x^n \in \{0,1\}^n\) のハミング重み（列内の"1"の個数）を \(w(x^n)\) と定め、計算基底の部分集合 \(\{\ket{x^{n_i}}: w(x^{n_i}) = l_i\}\) を考えます。これは、"1"の数が \(l_i\) 個である計算基底状態の集合です。

「制約条件で課された \(-1\) の個数だけ"1"を持つ量子状態」とは、この部分集合の要素の任意の重ね合わせ、つまり

\[ \sum_{x^{n_i}:w(x^{n_i}) = l_i} |c_{x^{n_i}}|^2 = 1 \]

なる複素数 \(c_{x^{n_i}}\) を用いて表された状態

\[ \sum_{x^{n_i}:w(x^{n_i}) = l_i} c_{x^{n_i}}\ket{x^{n_i}} \]

を指します。 Amplify では初期状態を

\[ \ket{\psi_{\mathrm{init}, i}} = \ket{\underbrace{1\dots1}_{l_i \text{個}}\underbrace{0\dots0}_{(n_i -l_i) \text{個}}} \]

と定めています。

なぜ制約条件を満たすのか

Ansatz 回路 \(U(\boldsymbol{\theta}^{(i)})\) と初期状態 \(\ket{\psi_{\mathrm{init}, i}}\) の構成を考えると、\(\ket{\psi_{\mathrm{init}, i}}\) に \(U(\boldsymbol{\theta}^{(i)})\) を作用されて得られる状態も、

\[ U(\boldsymbol{\theta}^{(i)})\ket{\psi_{\mathrm{init}, i}} = \sum_{x^{n_i}:w(x^{n_i}) = l_i} c_{x^{n_i}}\ket{x^{n_i}} \]

のように表されます。

例で確認します。以下では、\(i\) 番目の量子ビットと \(j\) 番目の量子ビットに作用するゲート \(A\) を、\(A_{(i,j)}\) と書くことにします。初期状態 \(\ket{\psi_{\mathrm{init}}} = \ket{100}\) にゲート \(A(\theta_1)_{(1,2)}\) を作用させることを考えます。

結果として

\[ A(\theta_1)_{(1,2)}\ket{\psi_{\mathrm{init}}} = \cos\theta_1\ket{010} - \sin\theta_1\ket{100} \]

が得られます。この状態にさらに、ゲート \(A(\theta_2)_{(2,3)}\) を作用させると、

\[ A(\theta_2)_{(2,3)}A(\theta_1)_{(1,2)}\ket{\psi_{\mathrm{init}}} = \cos\theta_1\cos\theta_2\ket{001} - \cos\theta_1\sin\theta_2\ket{010} - \sin\theta_1\ket{100} \]

が出力されます。以下この操作を何度繰り返しても、出力される状態は"1"を1個持つ状態、すなわち「制約条件で課された \(-1\) の個数だけ"1"を持つ量子状態」になります。

以上のように状態 \(U(\boldsymbol{\theta}^{(i)})\ket{\psi_{\mathrm{init}, i}}\) は初期状態が持つ"1"の個数を保存した状態になります。 この Ansatz 状態を用いることで、制約条件を保ちながら最適解を求めることが可能になるのです。

例

ここでは簡単な例を用いて、制約付き QAOA の回路構成を確認します。

問題として、\(f(z) = 2 z_1 z_2 + z_0 + z_1 - z_2\) と定義して

\[ \min_{z: z_0 + z_1 = 0} {f}(z) \]

を考えます。簡単のため、Ansatz 回路の深さ（reps）は \(1\) とします。

この問題では変数 \(z_0\) と \(z_1\) が制約条件 \(z_0 + z_1 = 0\) が課されたグループに属しており、\(z_2\) に制約条件はありません。

この制約条件は、\(z_0\) と \(z_1\) のどちらか片方だけが \(-1\) となることを課すものです。 先述した手順に従うと、Amplify では \(z_0\) と \(z_1\) に関する初期状態が \(\ket{10}\)、\(z_2\) に関する初期状態が \(\ket{0}\) と定まり、制約付き QAOA の回路図は次のようになります。

確かに \(z_0\) と \(z_1\) にかかわる部分の回路では、入力状態の持つ"1"の数と、出力状態の持つ"1"の数が同一であることが分かります。

以上みてきた通り、本ページで導入した Ansatz 状態 \(\ket{\psi(\boldsymbol{\theta})}\) は \(k\) 個の独立な制約条件を満たす状態に制限され、制約を緩和して解を探索する通常の方法と比べて、より効率的に解を求めることができると期待されます。

---

[1]

B.T. Gard, L. Zhu, G.S. Barron et al. Efficient symmetry-preserving state preparation circuits for the variational quantum eigensolver algorithm. npj Quantum Inf 6, 10 (2020).

[2]

Y. Ibe, Y.O. Nakagawa, N. Earnest et al. Calculating transition amplitudes by variational quantum deflation. Phys. Rev. Research 4, 013173 (2022).