QAOA（量子近似最適化アルゴリズム）は、最も注目を集めている近未来の量子アルゴリズムの一つであり、それには正当な理由があります。組合せ最適化問題における量子優位性の真の候補であり、今日のNISQハードウェア上で動作し、しかも午後の数時間で実装できるほど手軽です。
このガイドでは、Max-Cutを例題として、QAOAの完全なパイプラインをゼロから構築します。読み終える頃には、QAOAが実際に何をするのか、どう実装するのか、そしていつ使う価値があるのかを理解できるでしょう。
Max-Cutとは何か
Max-Cutはグラフ分割問題です。与えられたグラフに対して、ノードを2つのグループ（0と1）に分け、グループ間をまたぐエッジの数を最大化します。一般にはNP困難であり、VLSIチップ設計、クラスタリング、ネットワーク解析などに現れ、量子ハードウェアにきれいにマッピングできます。
こちらはシンプルな4ノードのグラフです：
0 --- 1
| \ |
3 --- 2
このグラフの最大カットは4です（エッジ0-1、1-2、2-3、3-0がすべてまたぐ）。私たちの目標は、これを達成するビット列 0101 または 1010 を見つけることです。
QAOAの発想
QAOAは変分ハイブリッドアルゴリズムです。2つのパラメータ化された演算を交互に適用します：
- 問題ユニタリ
U_C(γ)— コスト関数（エッジのまたぎ）を位相キックバックとしてエンコードする - ミキサーユニタリ
U_B(β)— 解の間を混ぜ合わせる（X回転）
これらの交互のユニタリを p 層重ねることで、QAOAは測定すると良い解が得られやすい量子状態を準備します。古典最適化器が 2p 個の角度 (γ, β) を調整し、期待カット値を最大化します。
PennyLaneでQAOAを構築する
import pennylane as qml
import numpy as np
from scipy.optimize import minimize
# Graph edges
edges = [(0, 1), (1, 2), (2, 3), (3, 0)]
n_qubits = 4
dev = qml.device("default.qubit", wires=n_qubits)
def cost_unitary(gamma):
"""Encode the Max-Cut cost into phases."""
for u, v in edges:
qml.CNOT(wires=[u, v])
qml.RZ(2 * gamma, wires=v)
qml.CNOT(wires=[u, v])
def mixer_unitary(beta):
"""Apply X-rotation mixer to all qubits."""
for i in range(n_qubits):
qml.RX(2 * beta, wires=i)
@qml.qnode(dev)
def qaoa_circuit(params, p=1):
gammas = params[:p]
betas = params[p:]
# Start in uniform superposition
for i in range(n_qubits):
qml.Hadamard(wires=i)
# Alternate p layers
for layer in range(p):
cost_unitary(gammas[layer])
mixer_unitary(betas[layer])
return qml.probs(wires=range(n_qubits))
def expected_cut(params, p=1):
"""Classical cost function: expected number of cut edges."""
probs = qaoa_circuit(params, p)
total = 0.0
for bitstring_idx, prob in enumerate(probs):
bits = format(bitstring_idx, f'0{n_qubits}b')
cut = sum(1 for u, v in edges if bits[u] != bits[v])
total += prob * cut
return -total # Minimize negative cut
# Optimize p=1 QAOA
p = 1
init_params = np.random.uniform(0, np.pi, 2 * p)
result = minimize(expected_cut, init_params, method='COBYLA',
options={'maxiter': 200})
print(f"Optimized params: {result.x}")
print(f"Expected cut: {-result.fun:.3f} / 4.0 maximum")
これを実行すると、p=1 で典型的には expected_cut ≈ 3.5 に達します — 最大カットの87.5%です。
最良解のサンプリング
最適化の後、回路をサンプリングして最も可能性の高い良い解を見つけます：
@qml.qnode(dev)
def sample_circuit(params, p=1, shots=1000):
gammas = params[:p]
betas = params[p:]
for i in range(n_qubits):
qml.Hadamard(wires=i)
for layer in range(p):
cost_unitary(gammas[layer])
mixer_unitary(betas[layer])
return qml.sample(wires=range(n_qubits))
samples = sample_circuit(result.x, shots=1000)
# Count cut values for each bitstring
from collections import Counter
cut_counts = Counter()
for bits in samples:
key = ''.join(str(b) for b in bits)
cut = sum(1 for u, v in edges if bits[u] != bits[v])
cut_counts[(key, cut)] += 1
# Show top 5 most frequent bitstrings
for (bits, cut), count in sorted(cut_counts.items(), key=lambda x: -x[1])[:5]:
print(f"{bits} cut={cut} frequency={count/10:.1f}%")
期待される出力：
0101 cut=4 frequency=28.3%
1010 cut=4 frequency=27.1%
0110 cut=3 frequency=8.4%
...
最適解（0101 と 1010）が支配的になります — QAOAがそれらの確率を増幅したのです。
同じ問題をHLQuantumで
HLQuantumの組み込みQAOAを使えば、回路の構築を完全に省略できます：
import hlquantum as hlq
graph = [(0, 1), (1, 2), (2, 3), (3, 0)]
result = hlq.algorithms.qaoa(
graph=graph,
problem='max_cut',
p=2,
backend='pennylane',
shots=2000,
)
print(result.best_solution) # '0101' or '1010'
print(result.cut_value) # 4
print(result.approximation_ratio) # ~0.96 for p=2
単一のフラグでバックエンドを切り替えられます：
# Run on Qiskit Aer
result_qiskit = hlq.algorithms.qaoa(graph=graph, problem='max_cut', p=2, backend='qiskit')
# Run on real IonQ hardware (if you have credits)
result_ionq = hlq.algorithms.qaoa(graph=graph, problem='max_cut', p=2,
backend='ionq', device='aria-1')
より良い結果のためにpを増やす
QAOAの近似比は深さ p とともに向上します。p→∞ では、QAOAは問題を厳密に解きます。実際には：
| p | Max-Cutでの典型的な近似比 | 必要なゲート数 |
|---|---|---|
| 1 | ~0.75 | 2×edges + 4n |
| 2 | ~0.86 | 4×edges + 8n |
| 3 | ~0.91 | 6×edges + 12n |
| 5 | ~0.95 | 10×edges + 20n |
トレードオフとして、深い回路は実ハードウェア上でより多くのノイズを蓄積します。シミュレータ上では p=3 以上を使いましょう。NISQ QPU上では、p=1 または p=2 が通常の実用的な限界です。
QAOAはいつ使う価値があるのか
現在有用な用途：
- NISQデバイスのベンチマーク（QAOAは標準的なベンチマーク回路）
- 変分量子アルゴリズムに関する学術研究
- シミュレータ上の小規模グラフ（20ノード未満）
まだ有用ではない用途：
- 実ハードウェア上での大規模な本番最適化 — 古典的ヒューリスティクス（シミュレーテッドアニーリング、タブーサーチ）は実用的な問題において依然としてQAOAを上回る
- 大規模グラフ — 回路の深さはグラフの密度とともに増大する
その可能性： 高深度回路を扱える将来の誤り耐性ハードウェア上では、大きな p でのQAOAが密なNP困難最適化に対して真の高速化をもたらしうるかもしれません。理論的基盤は堅固ですが、ハードウェアはまだそこに達していません。
次のステップ
- PennyLane SDKガイド — より多くの変分アルゴリズムのためにPennyLaneをセットアップする
- VQEガイド — 量子化学のための姉妹アルゴリズム
- HLQuantum — 一つのAPIで任意のバックエンド上でQAOAを実行する