Quantum Alternating Operator Ansatz

このブログの QAOAの応用(問題の定式化)で見たように、コスト関数は、コストすなわち目的関数とハイパーパラメータ $\lambda$ を掛けた成約条件を加えたものになります。この $\lambda$ をどう決めるのかが大きな課題であることは、QAOA 問題定式化の課題 で指摘しました。

$$
C=\operatorname{cost}+\lambda * \text { constraint }
$$

Quantum Alternating Operator Ansatzは、この制約条件を量子ゲートの初期状態に設定し、その後、時間発展計算をするというものです。

QAOAアルゴリズム

QAOAアルゴリズムは、以下の通りでした。

QAOAはニアタームアルゴリズムと呼ばれ、量子ゲートマシンでエラーがありながらもハイブリッドで計算できる方式でよく使われる組み合わせ最適化問題向けのアルゴリズムです。

元々は時間発展アルゴリズムというものがベースとなっており、それを変分アルゴリズムに改造されています。ここでは、ときたいコスト関数を上記のC、QAOAでよく使われる初期化されたコスト関数をBとして、BをCへと断続的に変化させることで、量子断熱計算と呼ばれる手法で、基底状態=最小値を探していきます。

量子変分原理では、量子回路中の角度をパラメータとして、

$$⟨Ψ_1∣C∣Ψ_1⟩$$

ある量子状態でハミルトニアンを測定したときの期待値を最小にするような量子状態を探していきます。この$Ψ_1$はQAOAアルゴリズムによって変分計算で網羅的に探していきます。

初期状態のコスト関数にはPauli-Xを基底($σ^x$)とした、
$$B=\sum_{i=1}^Nσx_i^x$$

を利用します。元のコスト関数は同様にPauli-Zを基底$(σ^z)$として、書き換えることができ、$$C(s)=c+\sum_{i=1}^Nh_iσ_i^z+\sum_{i=1}^N\sum_{j=i+1}^NJ_{ij}σ^z_iσ^z_j$$

こちらを使います。これらのコスト関数は、時間発展を改造したQAOAで量子状態を変化させる形で導入されますが、

$$\left|\Psi_{1}\right\rangle=\left(\prod_{\alpha=p}^{1} U\left(B, \beta_{\alpha}\right) U\left(C, \gamma_{\alpha}\right)\right)\left|\Psi_{0}\right\rangle$$

のように、繰り返しユニタリ行列をかけることで初期の量子状態を変化させることができます。初期の量子状態は今回は、

$$∣Ψ0⟩=∣+⟩^{⊗N}$$

のように、N量子ビットにアダマールゲートを適用し、|+>状態に持っていくことで準備できます。⊗N⊗Nは単にN量子ビットのテンソル積で構成されているということを示しています。

それぞれのユニタリ行列は、

$$U\left(B, \beta_{\alpha}\right)=e^{-i B \beta_{\alpha}}$$

$$U\left(C, \gamma_{\alpha}\right)=e^{-i C \gamma_{\alpha}}$$

のように、時間発展型で記述されます。

Quantum Alternating Operator Ansatzを使用したポートフォリオリバランスのレビュー

Quantum Alternating Operator Ansatz

Quantum Alternating Operator Ansatz は、以下のようなものです。

上記のmixing operator U(B)を改造します。

初期状態に対して、QAOAをかける際に、コスト関数を導入した演算子はそのままで、ドライバーハミルトニアンや、mixing operatorと呼ばれる部分を改造し、制約を考慮した形でゲートの時間発展を実現します。

組み合わせ最適化問題における探索はとても大きな空間を探索することになり、混合演算子(mixing operator)によって、$2^N$の値を探索する必要があります。

Quantum Alternating Operator Ansatzを導入することで、初期状態を制限し、制約条件を維持したまま探索空間を制限することでより効率的な計算ができます。

Quantum Alternating Operator Ansatzの概要レビュー

こでは、探索範囲を狭めることが強調されていますが、制約条件を反映した初期状態とすることも大きな利点であると考えます。具体的な事例は、参考資料を参照してください。

参考資料

Quantum Alternating Operator Ansatzを使用したポートフォリオリバランスのレビュー

Quantum Alternating Operator Ansatzの概要レビュー