QAOAのアルゴリズム¶

本ページでは、QAOA (Quantum Approximate Optimization Algorithm)[1] の数理的な枠組みを説明します。

QAOA が解く最適化問題¶

QAOA は、量子コンピュータと古典最適化を用いて組合せ最適化問題を解くアルゴリズムです。 QAOAでは Polynomial Unconstrained Binary Optimization (PUBO) と呼ばれるクラスの問題を扱います。

その名の通り、PUBO はバイナリ (binary) 変数 \(x = (x_1, x_2, \ldots, x_n) \quad (x_i \in \{0,1\},\ i=1,2,\ldots,n)\) の多項式 (polynomial) で表される目的関数を、制約条件無し (unconstrained) で最小化する (optimization) 問題です。形式的には、\(f\) を \(x\) の多項式として

\[ \mathrm{minimize}_{x \in \{0,1\}^n} \quad f(x) \]

と書けます。

量子コンピュータでは、バイナリ変数 \(x \in \{0,1\}^n\) よりも、イジング変数 \(z = (z_1, z_2, \ldots, z_n), \quad z_i \in \{-1,1\}\) を用いる方が扱いやすいのが一般的です。そのため、最適化したいバイナリ関数 \(f(x)\) が与えられたとき、変数変換 \(z_i = 2x_i - 1\) を行い、\(\tilde f(z) = f(x)\) となる等価なイジング関数 \(\tilde f\) を定義します。以下では、このイジング関数 \(\tilde f(z)\) の最小化を考えます。

重要

Amplify SDK では、バイナリ変数 \(x \in \{0,1\}\) とイジング変数 \(z \in \{-1,1\}\) は、次の関係を満たすものとします：

\[ z = 2x - 1, \qquad x = \frac{1 + z}{2} \]

イジング変数 \(z\) の定義と、\(f(x)\) が \(x\) の多項式であることから、\(\tilde f(z)\) も \(z\) の多項式となります。

以下、多項式 \(\tilde f(z)\) を構成する各単項式を \(\tilde f_{\alpha}(z)\) と表し、

\[ \tilde f(z) = \sum_{\alpha}\tilde f_{\alpha}(z) \]

と書きます。

量子状態について¶

QAOA の説明に入る前に、量子コンピュータにおいて情報がどのように表現されるかを簡単に確認します。

私たちが通常用いる古典コンピュータでは、情報は \(0\) と \(1\) からなる「ビット」の列として表されます。量子コンピュータの世界では、この「ビット」に対応するものを 量子ビット (qubit) と呼び、これは大きさが 1 に規格化された複素数上の 2 次元ベクトル、すなわち 量子状態 として表現されます。

古典のビットが \(0\) か \(1\) のどちらかの値しか取らないのに対し、量子ビットはより多様な量子状態を取り得ます。数学的には、量子状態 \(\ket{\psi}\) は、\(|\alpha|^2 + |\beta|^2 = 1\) を満たす複素数 \(\alpha, \beta\) を用いて、列ベクトル \((\alpha,\beta)^T\) で表されます。量子情報の分野では、しばしば \(\ket{0} = (1,0)^{T},\quad \ket{1} = (0,1)^{T}\) と定義された正規直交基底 \(\{\ket{0}, \ket{1}\}\) を用いて

\[ \ket{\psi} = \alpha \ket{0} + \beta \ket{1} \]

と表現します。この正規直交基底を計算基底と呼びます。以下では量子状態などの行列表示は計算基底で行うものとします。

一般に、\(n\) 量子ビットの量子状態は \(2^n\) 次元の複素ベクトルで表されます。基本的な考え方は 1 量子ビットの場合と同様です。

ハミルトニアンについて¶

QAOA では与えられた目的関数を量子ビットに作用するエルミート演算子に変換し、その値を量子コンピュータで評価します。この目的関数に対応する演算子をハミルトニアンと呼びます。

数学的にはエルミート演算子とは、共役転置(転置と複素共役を取ったもの)が自身に一致する線形演算子を指します。例として、1量子ビット（2次元複素ベクトル空間）のケースについて行列表示を考えてみましょう。複素数 \(a,b,c,d\) を用いて表される線形演算子

\[\begin{split} A = \begin{pmatrix} a & b \\ c & d \end{pmatrix} \end{split}\]

がエルミート演算子であるというのは、共役転置

\[\begin{split} A^\dagger = \begin{pmatrix} a^* & c^* \\ b^* & d^* \end{pmatrix} \end{split}\]

に対して、\(A^\dagger = A\) が成り立つことを意味します。この関係から、一般に1量子ビットに作用するエルミート演算子 \(A\) は、実数 \(x,y\) と複素数 \(z\) を用いて

\[\begin{split} A = \begin{pmatrix} x & z \\ z^* & y \end{pmatrix} \end{split}\]

と表現されます。

1量子ビットに作用するエルミート演算子の重要な例として、Pauli 演算子があります。行列表示では、

\[\begin{split} I = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}, \,\, X = \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}, \,\, Y = \begin{pmatrix} 0 & -i \\ i & 0 \end{pmatrix}, \,\, Z = \begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix} \end{split}\]

と表されます。それぞれ、\(I\) を恒等演算子、\(X\) を Pauli \(X\) 演算子、\(Y\) を Pauli \(Y\) 演算子、\(Z\) を Pauli \(Z\) 演算子と呼びます。

ハミルトニアンの作成で詳述するように、QAOA では目的関数が持つイジング変数を、Pauli \(Z\) 演算子で置き換えることでハミルトニアンを構成します。

Pauli \(Z\) 演算子の定義から、計算基底 \(\{\ket{0}, \ket{1}\}\) は、Pauli \(Z\) 演算子の固有ベクトルになっています。特に、

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

となります。つまり、量子ビットが \(\ket{0}\) の時 \(Z = 1\)、量子ビットが \(\ket{1}\) の時 \(Z = -1\) となり、計算基底の下で Pauli \(Z\) 演算子がイジング変数のようなふるまいをすることが分かります。この意味で、Pauli \(Z\) 演算子で構成されたハミルトニアンは、元のイジング変数で定義された目的関数と対応しています。またこの関係から、量子状態 \(\ket{0}\) がイジング値 \(1\) に、量子状態 \(\ket{1}\) がイジング値 \(-1\) に対応することも見て取れます。

量子測定について¶

量子コンピュータ上の量子ビットで表される状態に、量子測定を行うことで古典ビットの情報を引き出すことができます。ここでは、最も基礎的な量子測定である、計算基底による量子測定を取り上げます。なお、QAOA で必要とされる量子測定はすべて計算基底による量子測定であるため、以下では特に言及がない限りこれを「量子測定」と呼ぶこととします。

1量子ビット上の量子状態

\[ \ket{\psi} = \alpha\ket{0} + \beta\ket{1} \]

に対する量子測定とは、確率 \(|\alpha|^2\) で値 "0" を、確率 \(|\beta|^2\) で値 "1" を得る操作として理解されます。

この時重要なのが、量子測定を行うと状態 \(\ket{\psi}\) が破壊されてしまうという点です。厳密には、測定によって得られた値が "0" の時、状態が \(\ket{0}\) に、得られた値が "1" の時、状態が \(\ket{1}\) に変化します。量子コンピュータのハードウェアによっては、物理的な制約から量子測定実行後の状態が得られないものもあることから、本ドキュメントでは量子測定後、状態は破壊され二度と使えなくなってしまうものとして話を進めます。

エルミート演算子の期待値評価について¶

エルミート演算子 \(H\) で表される物理量の、状態 \(\ket{\psi}\) での期待値は、

\[ \braket{\psi|H|\psi} \]

で表されます。ここで \(\bra{\psi}\) は、量子状態（複素列ベクトル）\(\ket{\psi}\) の随伴ベクトル（共役転置を取ったもの）と定義されます。例えば、1量子ビットのケースで、\(\ket{\psi} = (a,b)^T\) なら \(\bra{\psi} = (a^*, b^*)\) となり、\(n\) 量子ビットの場合も同様に共役転置で定義されます。

QAOA では、Pauli \(Z\) 演算子の期待値の評価が必要になります。ここでは、量子測定を用いて Pauli \(Z\) 演算子の期待値を評価する方法について解説します。

与えられた量子状態が

\[ \ket{\psi} = \alpha\ket{0} + \beta\ket{1} \]

の時、\(\ket{\psi}\) における Pauli \(Z\) 演算子の期待値は、計算基底での行列表示を用いて

\[\begin{split} \braket{\psi|Z|\psi} = (\alpha^*, \beta^*) \begin{pmatrix} 1 & 0\\ 0 & -1 \end{pmatrix} \begin{pmatrix} \alpha\\ \beta \end{pmatrix} = |\alpha|^2 - |\beta|^2 \end{split}\]

と計算できます。

ここで、状態 \(\ket{\psi}\) が未知（\(\alpha\) と \(\beta\) の値が未知）の際には、期待値を直接厳密に計算することはできません。しかし、未知の量子状態 \(\ket{\psi}\) のコピーを十分大きな数用意して量子測定を繰り返し行うことにより、期待値を近似的に評価することができます。

量子状態 \(\ket{\psi}\) を \(N\) 個用意し、それぞれについて量子測定を行うことを考えます。その結果、"0" が \(N_{\alpha}\) 個、 "1" が \(N_{\beta}\) 個得られたとします。（\(N = N_{\alpha} + N_{\beta}\) です。）この時、十分大きい \(N\) については、

\[ |\alpha|^2 \approx \frac{N_{\alpha}}{N} \ ,\ |\beta|^2 \approx \frac{N_{\beta}}{N} \]

と近似できます。これを用いると、Pauli \(Z\) 演算子の期待値を

\[ \braket{\psi|Z|\psi} = |\alpha|^2 - |\beta|^2 \approx \frac{N_{\alpha} - N_{\beta}}{N} \]

と評価できることが分かります。

ここでは1量子ビットのケースを考えましたが、一般の \(n\) 量子ビットについても同様に Pauli \(Z\) 演算子の期待値が評価できます。

重要

量子測定についての解説で触れたとおり、量子測定を行うと状態 \(\ket{\psi}\) は破壊されてしまいます。そのため、\(\ket{\psi}\) の量子測定を \(N\) 回行う際には、\(\ket{\psi}\) のコピーを \(N\) 個用意する必要があります。この値をショット数あるいはサンプル数と呼びます。

ショット数を大きくとれば計算の精度が良くなることが期待される一方、計算に時間がかかってしまうというトレードオフがあります。そのため QAOA ではショット数を適切に設定することが肝要となります。

QAOA の手続き¶

QAOA は次のような手続きで最適化問題を解きます。

与えられたイジング関数 \(\tilde f\) から、目的関数に対応するハミルトニアン \(H\) を構成する。このとき、\(H\) の最小固有値が \(\tilde f\) の最小値に対応する。
\(H\) の最小固有値（に対応する固有状態）を探索するために、実数パラメータ \(\boldsymbol{\theta} = (\theta_1,\theta_2,\ldots,\theta_k)\) で特徴づけられたパラメトリック量子回路（Ansatz 回路）を構成する。パラメータ \(\boldsymbol{\theta}\) に対応する量子状態を \(\ket{\psi(\boldsymbol{\theta})}\) と書き、Ansatz 状態と呼ぶ。
コスト関数を \(C(\boldsymbol{\theta}) = \bra{\psi(\boldsymbol{\theta})} H \ket{\psi(\boldsymbol{\theta})}\) と定義する。
量子コンピュータ上での \(C(\boldsymbol{\theta})\) の評価と、古典最適化アルゴリズムによるパラメータ \(\boldsymbol{\theta}\) の更新を、ある収束条件を満たすまで繰り返す。

以下、各ステップについて順に説明します。

1. ハミルトニアンの作成¶

QAOA の目的関数として、イジング関数

\[ \tilde f(z) = \sum_{\alpha} \tilde{f}_{\alpha}(z) \]

が与えられているとします。

目的は、\(\tilde f(z)\) を最小化するイジング変数列 \(z = (z_1,\ldots,z_n) \in \{-1,1\}^n\) を見つけることです。

量子コンピュータで最適化を行うには、このイジング関数を量子ビットに作用するエルミート演算子（ハミルトニアン）へと変換します。具体的には、目的関数に対応するハミルトニアン \(H = \sum_{\alpha} H_{\alpha}\) を各単項式 \(\tilde f_\alpha(z)\) に登場するイジング変数 \(z_i\) を、対応する Pauli \(Z\) 演算子 \(Z_i\) に置き換えることで定義します。

具体例を以下に示します。

\(\tilde f_{\alpha}(z) = 2z_1z_2\) のとき

\[ H_{\alpha} = 2 Z_1 Z_2 \]

\(\tilde f_{\alpha}(z) = -3 z_3\) のとき

\[ H_{\alpha} = -3 Z_3 \]

\(\tilde f_{\alpha}(z) = 5\) のような定数項は、恒等演算子 \(I\) の係数に対応し

\[ H_{\alpha} = 5 I \]

となります。このような定数項は、スペクトル全体を一定だけシフトするだけで基底状態は変えないため、多くの場合は無視して構いません（ただしエネルギーの絶対値が必要な場面では保持します）。

ここで \(Z_i\) は「\(i\) 番目の量子ビットに作用する Pauli \(Z\) 演算子」を意味します。本ドキュメントではテンソル積 \(\otimes\) は省略し、\(Z_1 \otimes Z_2\) を \(Z_1 Z_2\) のように書きます。

以上より、\(n\) 変数のイジング関数 \(\tilde f\) を QAOA で最適化したい場合、\(n\) 量子ビット上で定義されたハミルトニアン \(H\) が必要になります。したがって、少なくとも \(n\) 量子ビットを持つ量子コンピュータが必要になります。

2. Ansatz 状態の準備¶

与えられた問題を解くため、パラメータ付きの量子状態（Ansatz 状態）を定義します。Ansatz 状態とは、パラメータで特徴づけられた量子回路を初期状態に作用させて得られる状態 のことです。QAOA では、特定の構造を持つ QAOA Ansatz を用います。QAOA Ansatz を作成する回路は次のようになります。

初期状態¶

QAOA では、多くの場合、初期状態として \(+\) 状態と呼ばれる状態を用います。1 量子ビットの \(+\) 状態は

\[ \ket{+} = \frac{\ket{0} + \ket{1}}{\sqrt{2}} \]

と定義されます。

ヒント

\(+\) 状態は、\(0\) 状態 \(\ket{0}\) に Hadamard ゲート

\[\begin{split} \frac{1}{\sqrt{2}} \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix} \end{split}\]

を作用させることで得られます。

\(n\) 個すべての量子ビットが \(+\) 状態にある \(\ket{+}^{\otimes n}\) を QAOA の初期状態として用います。

QAOA Ansatz の定義¶

QAOA Ansatz は、実数パラメータ列

\[ \boldsymbol{\theta} = (\boldsymbol{\beta},\boldsymbol{\gamma}) = (\beta_1,\ldots,\beta_p,\gamma_1,\ldots,\gamma_p) \]

で特徴づけられる量子状態です。ここで \(p\) は QAOA の「深さ」（層数）です。本ドキュメントでは、パラメータ全体をまとめて \(\boldsymbol{\theta}\) と書きます。QAOA Ansatz を生成する量子回路 \(U(\boldsymbol{\theta})\) を次のように定義します。

\[ U(\boldsymbol{\theta}) = \prod_{j=1}^{p} \left[ \exp\left(-i \beta_j \sum_{k} X_k\right) \exp\left(-i \gamma_j H\right) \right] \]

ここで \(H\) は先ほど定義したコストハミルトニアン、 \(X_k\) は \(k\) 番目の量子ビットに作用する Pauli \(X\) 演算子を表します。因子の積 \(\prod_{j=1}^{p}\) は、右側の \(j=1\) の層から左側の \(j=p\) の層へ向かって順に作用する と解釈します。本ドキュメントでは、\(\gamma_j\) をコストハミルトニアン \(H\) に対応するパラメータ、 \(\beta_j\) を \(X\) によるミキシングに対応するパラメータとして用いています。直感的には、

\(\exp(-i \gamma_j H)\) が Pauli \(Z\) 方向（コスト関数）に沿って状態を発展させ、
\(\exp\left(-i \beta_j \sum_k X_k\right)\) が Pauli \(X\) 方向に沿って状態を混合させる

ことで、多様な量子状態を表現します。

以上より、パラメータ \(\boldsymbol{\theta}\) に対応する QAOA Ansatz 状態を

\[ \ket{\psi(\boldsymbol{\theta})} = U(\boldsymbol{\theta}) \ket{+}^{\otimes n} \]

と定義します。

3. コスト関数の定義¶

コスト関数 \(C(\boldsymbol{\theta})\) は、ハミルトニアン \(H\) の、Ansatz 状態 \(\ket{\psi(\boldsymbol{\theta})}\) における期待値として定義されます。数学的には

\[ C(\boldsymbol{\theta}) = \bra{\psi(\boldsymbol{\theta})} H \ket{\psi(\boldsymbol{\theta})} \]

です。

先述の通り計算基底の行列表示では、量子状態 \(\ket{\psi}\) は複素列ベクトルとして表され、\(\bra{\psi}\) はその随伴ベクトルです。

ハミルトニアン \(H\) の最小固有値を \(\lambda_{\min}\)、その固有ベクトルを \(\ket{\psi_{\min}}\) とすると、\(C(\boldsymbol{\theta})\) は \(\ket{\psi(\boldsymbol{\theta})}\) が \(\ket{\psi_{\min}}\) に一致するときに最小値 \(\lambda_{\min}\) を取ります。

QAOA では、「\(\ket{\psi(\boldsymbol{\theta})}\) のうち、\(C(\boldsymbol{\theta})\) を最小にするものは \(H\) の基底状態（の良い近似）になっているはずだ」という前提のもと、古典的な最適化により \(C(\boldsymbol{\theta})\) を最小化するパラメータ \(\boldsymbol{\theta}\) を探索します。

4. 古典最適化によるパラメータ更新サイクル¶

QAOA の本体とも言えるステップです。ここでは、

量子コンピュータによるコスト関数 \(C(\boldsymbol{\theta})\) の値の評価
古典コンピュータによるパラメータ \(\boldsymbol{\theta}\) の更新

を繰り返し、\(C(\boldsymbol{\theta})\) を最小化する \(\boldsymbol{\theta}^{\textup{opt}}\) を見つけることを目指します。

コスト関数 \(C(\boldsymbol{\theta})\) の値の評価¶

コスト関数 \(C(\boldsymbol{\theta})\) の値を評価するのは量子コンピュータの仕事です。

目的関数から作られたハミルトニアン \(H\) は、その構成方法より

\[ H = \sum_{\alpha} H_{\alpha} = \sum_{\alpha} c_{\alpha} Z_{\alpha} \]

と表すことができます。ここで、\(c_{\alpha}\) は単項式 \(\tilde{f}_{\alpha}(z)\) の係数部分、\(Z_{\alpha}\) は変数部分に対応する Pauli \(Z\) 演算子です。この表式を用いると、コスト関数 \(C(\boldsymbol{\theta})\) は

\[ C(\boldsymbol{\theta}) = \bra{\psi(\boldsymbol{\theta})} H \ket{\psi(\boldsymbol{\theta})} = \sum_{\alpha} c_{\alpha} \bra{\psi(\boldsymbol{\theta})} Z_{\alpha} \ket{\psi(\boldsymbol{\theta})} \]

と表されます。各 \(\bra{\psi(\boldsymbol{\theta})} Z_{\alpha} \ket{\psi(\boldsymbol{\theta})}\) の値は、期待値評価についての解説の通り、\(\ket{\psi(\boldsymbol{\theta})}\) の量子測定の結果を用いて評価することができます。それぞれの \(\bra{\psi(\boldsymbol{\theta})} Z_{\alpha} \ket{\psi(\boldsymbol{\theta})}\) の値を上式に代入することで、コスト関数 \(C(\boldsymbol{\theta})\) の値が評価できます。

パラメータ \(\boldsymbol{\theta}\) の更新¶

量子コンピュータが評価したコスト関数の値をもとに、パラメータ \(\boldsymbol{\theta}\) を更新して最適パラメータを見つけ出すのは古典コンピュータ側の役割です。

パラメータ更新サイクルをまとめると、

あるパラメータ \(\boldsymbol{\theta}\) を用いて QAOA 回路 \(U(\boldsymbol{\theta})\) を実行し、
状態 \(\ket{\psi(\boldsymbol{\theta})}\) に対するハミルトニアン \(H\) の期待値 \(C(\boldsymbol{\theta})\) を測定により推定し、
古典最適化アルゴリズム（勾配法、勾配無し最適化、ベイズ最適化など）を用いて次の \(\boldsymbol{\theta}\) を決める

というステップを、ある収束条件を満たすまで繰り返します。

QAOA まとめ¶

最後に、QAOA の典型的なステップを改めてまとめます。

        flowchart TD
    S1["Step 1: ハミルトニアンの定義"]
    S2["Step 2: Ansatz 回路の構成"]
    S3["Step 3: コスト関数の定義"]
    S4["Step 4: パラメータの最適化"]
    S5["Step 5: 解の抽出"]

    S1 --> S2 --> S3 --> S4
    S4 -->|"未収束"| S4
    S4 -->|"収束"| S5

Step1: ハミルトニアンの定義: 最適化したい古典コスト関数を \(f(z) = \sum_{\alpha} c_{\alpha} f_{\alpha}(z)\) と書く。ここで、\(z = (z_1,\ldots,z_n)\) は \(z_i \in \{-1,1\}\) のイジング変数列、\(c_{\alpha}\) は実数係数、\(f_{\alpha}\) は単項式である。各単項式 \(f_{\alpha}(z)\) に現れるイジング変数 \(z_i\) を対応する Pauli \(Z\) 演算子 \(Z_i\) に置き換え、必要に応じて恒等演算子 \(I\) を用いることで、量子ビット空間上のハミルトニアン \(H = \sum_{\alpha} H_{\alpha}\) を構成する。QAOA の目的は、この \(H\) の最小固有値／固有ベクトルを近似的に求めることで、\(f(z)\) の最小値を達成するイジング変数列 \(z\) を得ることである。
Step2: Ansatz 状態の準備: 上で構成したハミルトニアン \(H\) の最小固有値を探索するため、実数パラメータ列 \(\boldsymbol{\theta} = (\boldsymbol{\gamma},\boldsymbol{\beta})\) で特徴づけられた QAOA Ansatz 回路 \(U(\boldsymbol{\theta})\) を構成する。初期状態 \(\ket{+}^{\otimes n}\) に対し、 \(\ket{\psi(\boldsymbol{\theta})} = U(\boldsymbol{\theta}) \ket{+}^{\otimes n}\) と定義し、この \(\ket{\psi(\boldsymbol{\theta})}\) を Ansatz 状態と呼ぶ。
Step3: コスト関数の定義: コスト関数を \(C(\boldsymbol{\theta}) = \bra{\psi(\boldsymbol{\theta})} H \ket{\psi(\boldsymbol{\theta})}\) と定義する。\(C(\boldsymbol{\theta})\) は、パラメータ \(\boldsymbol{\theta}\) に対応する Ansatz 状態 \(\ket{\psi(\boldsymbol{\theta})}\) におけるハミルトニアン \(H\) の期待値である。
Step4: パラメータのアップデート: 量子コンピュータ上で \(C(\boldsymbol{\theta})\) を評価し、その結果を用いて古典最適化アルゴリズムによりパラメータ \(\boldsymbol{\theta}\) を更新する。この「（量子側での）評価」と「（古典側での）更新」を、所定の収束条件を満たすまで繰り返す。
Step5: 解の抽出: 収束時のパラメータを \(\boldsymbol{\theta}^{\textup{opt}}\) と書く。このとき、\(C(\boldsymbol{\theta}^{\textup{opt}})\) および \(\ket{\psi(\boldsymbol{\theta}^{\textup{opt}})}\) は、ハミルトニアン \(H\) の最小固有値／固有ベクトルの良い近似になっていると期待される。状態 \(\ket{\psi(\boldsymbol{\theta}^{\textup{opt}})}\) での測定結果から得られたイジング変数列 \(z\) ごとに目的関数 \(\tilde{f}(z)\) を計算し、 \(\tilde{f}(z)\) が最小となるものを候補解として選ぶ。測定結果の中で最も多く得られたイジング変数列 \(z^{\textup{opt}}\) は \(\tilde{f}(z)\) の最小値（またはその近傍の値）を与える解になっていると期待される。