読者への演習にしない QAOA アルゴリズム完全チュートリアル

このノートは、量子近似最適化アルゴリズム（Quantum Approximate Optimization Algorithm, QAOA）の手を動かす入門である。代数的な手順を「読者への演習」として残さずに書き下す。焦点は、組合せ最適化で使われる標準的な Ising 型の定式化、それが断熱量子計算とどうつながるか、回路をどう構成するか、そして最も簡単な導出に現れる演算子恒等式をどう評価するかにある。

問題の定義

QAOA は、最適化問題を近似的に解くための変分量子アルゴリズムである。古典的な目的関数をコストハミルトニアン \(C\) に符号化し、アルゴリズムはパラメータ付き量子状態を準備する。その測定分布は、符号規約に応じて、低コストまたは高コストのビット列を優先する。

二値最適化問題では、候補解をビット列として

\[z = z_1 z_2 cdots z_n, qquad z_i in {0,1}.\]

と書く。目的関数は各ビット列に実数値 \(C(z)\) を割り当てる。QAOA では、この古典関数を対角な量子演算子へ持ち上げる。

\[C |zrangle = C(z)|zrangle.\]

アルゴリズムは混合ハミルトニアンも用いる。通常は

\[B = sum_{j=1}^{n} X_j,\]

であり、ここで \(X_j\) は量子ビット \(j\) に作用する Pauli \(X\) 演算子である。深さ \(p\) に対して、QAOA 状態は

\[|gamma,betarangle = e^{-ibeta_p B} e^{-igamma_p C} cdots e^{-ibeta_1 B} e^{-igamma_1 C} |srangle,\]

である。ただし

\[|srangle = |+rangle^{otimes n}\]

は、すべての計算基底状態にわたる一様重ね合わせである。古典的な外側ループは角度

\[(gamma_1,ldots,gamma_p,beta_1, ldots,beta_p)\]

を選び、期待値

\[F_p(gamma,beta)=langle gamma,beta|C|gamma,betarangle.\]

を最適化する。最大化問題では \(F_p\) を最大化しようとする。最小化問題では、同じ式を最小化するか、コストハミルトニアンの符号を反転する。

横磁場 Ising モデル

二値変数は Pauli \(Z\) 演算子で自然に表せるため、多くの QAOA の例では Ising ハミルトニアンを使う。2 量子ビットでは、よく使われる相互作用項は

\[Z_i Z_j.\]

である。グラフに基づくコストハミルトニアンは、しばしば

\[C = sum_{(i,j)in E} w_{ij} Z_i Z_j,\]

という形をとり、場合によっては 1 局所場

\[sum_i h_i Z_i.\]

も加わる。横磁場部分がミキサーである。

\[B = sum_i X_i.\]

したがって、QAOA で交互に現れる 2 つの部分は次の通りである。

  1. 対角な Ising コスト発展 \(e^{-igamma C}\)
  2. 横磁場の混合発展 \(e^{-ibeta B}\)

重要なのは、多くの項が可換であることだ。すべての \(Z_iZ_j\) 項は対角なので互いに可換である。また、すべての \(X_i\) 項も異なる量子ビットに作用するため互いに可換である。これにより、指数演算子を 1 量子ビットゲートと 2 量子ビットゲートの積として実装できる。

断熱量子計算

QAOA は、断熱量子計算をデジタル化し、変分化したものと見ることができる。

断熱的な見方では、まず基底状態を簡単に準備できる易しいハミルトニアンから始める。例えば

\[H_B = -sum_i X_i.\]

である。その基底状態は \(|+rangle^{otimes n}\) である。そこからハミルトニアンを問題ハミルトニアン \(H_C\) へゆっくり変化させる。

\[H(t) = (1-s(t))H_B + s(t)H_C,\]

ここで \(s(0)=0\)、\(s(T)=1\) である。補間が十分に遅く、スペクトルギャップがうまく振る舞うなら、断熱定理により状態は瞬間的な基底状態に近似的に追従する。

QAOA は、この連続過程を交互のパルス

\[e^{-ibeta B}e^{-igamma C}.\]

で置き換える。深さ \(p\) が大きいとき、この列は Trotter 化された断熱経路に似ている。深さが小さいときは、角度を自由な変分パラメータとして扱い、直接最適化する。

回路設計

QAOA の 1 レイヤーの回路は 3 つの部分からなる。

  1. 初期状態を準備する。
\[|0rangle^{otimes n} xrightarrow{H^{otimes n}} |+rangle^{otimes n}.\]
  1. コストユニタリを適用する。
\[U_C(gamma)=e^{-igamma C}.\]

Ising 辺 \((i,j)\) に対して、2 量子ビット項は

\[e^{-igamma w_{ij} Z_iZ_j}.\]

である。標準的な分解は次の通り。

CNOT(i, j)
RZ(2 gamma w_ij) on j
CNOT(i, j)

角度の符号は、量子 SDK が \(R_Z(theta)\) に対して採用している規約に依存する。必ずローカルなゲート定義で確認すること。

  1. ミキサーユニタリを適用する。
\[U_B(beta)=e^{-ibetasum_i X_i}=prod_i e^{-ibeta X_i}.\]

多くの SDK では

\[R_X(theta)=e^{-itheta X/2},\]

と定義されているため、通常は

RX(2 beta) on every qubit

として実装される。ここでも、符号と 2 倍の係数をローカルな SDK 定義と照合する。

深さ \(p\) の完全な回路は、コストブロックとミキサーブロックを繰り返す。

H on every qubit
for layer = 1..p:
    apply cost unitary with gamma[layer]
    apply mixer unitary with beta[layer]
measure

コーディング

最小実装には 3 つの動く部分がある。

  1. 与えられたパラメータに対して QAOA 回路を構築する関数
  2. 測定カウントから期待コストを推定する関数
  3. 角度を更新する古典オプティマイザ

擬似コードは次の通り。

def qaoa_circuit(graph, gammas, betas):
    circuit = QuantumCircuit(len(graph.nodes))

    for q in graph.nodes:
        circuit.h(q)

    for gamma, beta in zip(gammas, betas):
        for i, j, weight in graph.edges(data="weight", default=1.0):
            circuit.cx(i, j)
            circuit.rz(2 * gamma * weight, j)
            circuit.cx(i, j)

        for q in graph.nodes:
            circuit.rx(2 * beta, q)

    circuit.measure_all()
    return circuit

ビット列を評価するには、ハミルトニアンの構築に使ったものと同じコスト関数を定義する。例えば Ising 目的関数では次のようになる。

def spin(bit):
    return 1 if bit == "0" else -1


def ising_cost(bitstring, edges):
    total = 0.0
    for i, j, weight in edges:
        total += weight * spin(bitstring[i]) * spin(bitstring[j])
    return total

次に、カウントから期待値を推定する。

def expected_cost(counts, edges):
    shots = sum(counts.values())
    return sum(ising_cost(bits, edges) * count / shots for bits, count in counts.items())

これは意図的に SDK に依存しない形にしている。実際の実装では、バックエンドやシミュレータのビット順序規約を確認すること。一部のフレームワークは、量子ビット添字に対する見た目の順序とは逆向きのビット列を返す。

自明な状態準備

数日考え、調べた後、自分の疑問に自分で答えることにした。

注：テンソル積記号 otimes は、特に添字が異なる場合など、混乱のおそれがないときには省略する。記号で書けば、A_iB_j = A_i otimes B_j (i neq j) である。

まず、e^{i beta B} Z_i Z_j e^{-i beta B} の場合について、量子ビット j だけを考える。ここで B_e=sum_{k in e}{X_k} である。X_i と X_j は異なる量子ビットに作用するので、

begin{equation*}e^{i{(X_i+X_j)}}=e^{i((X_iotimes I_j)+(I_i otimes X_j))}=e^{iX_i}e^{iX_j}.end{equation*}

となる。

次に、

begin{equation*} begin{aligned} e^{-i beta X} & = e^{-i beta begin{bmatrix}0 & 1 1 & 0end{bmatrix}} & = e^{-i beta begin{bmatrix}frac{1}{sqrt{2}} & frac{1}{sqrt{2}} frac{1}{sqrt{2}} & -frac{1}{sqrt{2}}end{bmatrix} begin{bmatrix}1 & 0 0 & 1end{bmatrix} begin{bmatrix}frac{1}{sqrt{2}} & frac{1}{sqrt{2}} frac{1}{sqrt{2}} & frac{1}{sqrt{2}}end{bmatrix}} & = begin{bmatrix}frac{1}{sqrt{2}} & frac{1}{sqrt{2}} frac{1}{sqrt{2}} & -frac{1}{sqrt{2}}end{bmatrix} begin{bmatrix}e^{-i beta} & 0 0 & e^{-i beta}end{bmatrix} begin{bmatrix}frac{1}{sqrt{2}} & frac{1}{sqrt{2}} frac{1}{sqrt{2}} & frac{1}{sqrt{2}}end{bmatrix} & = begin{bmatrix}cos(beta) & -isin(beta) -isin(beta) & cos(beta)end{bmatrix} & = Icos(beta)-iXsin(beta). end{aligned} end{equation*}

したがって、

begin{equation*}begin{aligned}e^{i beta X}& = Icos(beta)+iXsin(beta).end{aligned}end{equation*}

である。ゆえに、

begin{equation*}begin{aligned}e^{i beta X} Z e^{-i beta X} & = (Icos(beta)+iXsin(beta))Z(Icos(beta)-iXsin(beta)) & = Z cos(2beta) + Ysin(2beta).end{aligned}end{equation*}

となる。

横磁場 Ising ハミルトニアンについて、G_{e=(i,k)}=Z_iZ_k を考える。

e^{i gamma Z_iZ_k} については、次のように評価できる。

begin{equation*} begin{aligned} e^{i gamma Z_iZ_k} = & e^{i gamma begin{bmatrix}1&&&&-1&&&&-1&&&&1end{bmatrix}} = begin{bmatrix}e^{igamma}&&&&e^{-igamma}&&&&e^{-igamma}&&&&e^{igamma}end{bmatrix} = & begin{bmatrix}cosgamma+isingamma &&&&cosgamma-isingamma&&&&cosgamma-isingamma&&&&cosgamma+isingammaend{bmatrix} = & cosgammabegin{bmatrix}1&&&&1&&&&1&&&&1end{bmatrix}+isingammabegin{bmatrix}1&&&&-1&&&&-1&&&&1end{bmatrix} = & I_i I_k cosgamma + i Z_1Z_2 singamma. end{aligned} end{equation*}

2 量子ビット演算は独立に計算できる。

begin{equation*}Y_i (Z_i Z_k) = (Y_i otimes I_k)(Z_i otimes Z_k)=(Y_i Z_i) otimes (I_kZ_k) = i X_i otimes Z_k = i X_i Z_k.end{equation*}

納得できなければ、数値的には、

begin{equation*}Y_i otimes I_k = begin{bmatrix} &&-i&&&&-ii&&&&i&& end{bmatrix}end{equation*}

であり、

begin{equation*}Z_i otimes Z_k = begin{bmatrix} 1&&&&-1&&&&-1&&&& 1end{bmatrix}end{equation*}

であり、

begin{equation*}(Y_i otimes I_k)(Z_i otimes Z_k) = begin{bmatrix} &&i&&&&-ii&&&&-i&&end{bmatrix} = i(X_i otimes Z_k).end{equation*}

である。

ここで、より具体的な例として、

begin{equation*} begin{aligned} e^{-i gamma Z_iZ_k} Y_i e^{i gamma Z_iZ_k} & = (I_i I_k cosgamma - i Z_1Z_2 singamma) (Y_i otimes I_k) (I_i I_k cosgamma + i Z_1Z_2 singamma) & = Y_i cos^2gamma - Y_isin^2gamma - X_i Z_ksingammacosgamma - X_i Z_k singammacosgamma & = Y_i cos 2gamma - X_iZ_ksin 2gamma. end{aligned} end{equation*}

Q.E.D.

参考文献

  1. Choi J, Kim J. A Tutorial on Quantum Approximate Optimization Algorithm (QAOA): Fundamentals and Applications. In: 2019 International Conference on Information and Communication Technology Convergence (ICTC). IEEE; 2019. doi:10.1109/ictc46691.2019.8939749

Leave a Reply