ゆるふわ量子コンピュータ
VQEと並ぶNISQ期の主役が QAOA（Quantum Approximate Optimization Algorithm）。組合せ最適化を量子×古典で近似的に解きます。この記事では定番の「最大カット問題」をQiskitで解き、最適な2分割を見つけます。
最大カット問題とは
グラフの頂点を2グループに分けたとき、「グループをまたぐ辺（カット）」が最大になる分け方を探す問題です。配置・分割・クラスタリングなど応用が広い、NP困難の代表例です。
QAOAの2層を繰り返す
コスト層
問題を位相に埋め込む
ミキサー層
探索を広げる
最適化
パラメータを調整
準備
pip install qiskit qiskit-aer numpy① グラフとカット値
4頂点の輪（正方形）を例にします。最適解は交互に塗る 1010 / 0101（カット=4）。
import numpy as np
from qiskit import QuantumCircuit
from qiskit_aer import AerSimulator
edges = [(0, 1), (1, 2), (2, 3), (3, 0)]
def cut_value(bits):
return sum(1 for i, j in edges if bits[i] != bits[j])② QAOA回路（p=1）
コスト層は各辺に Rzz、ミキサー層は各ビットに Rx。
def qaoa_circuit(gamma, beta):
qc = QuantumCircuit(4, 4)
qc.h(range(4)) # 一様な重ね合わせから開始
for i, j in edges:
qc.rzz(2 * gamma, i, j) # コスト層：辺を位相に埋め込む
for q in range(4):
qc.rx(2 * beta, q) # ミキサー層：探索を混ぜる
qc.measure(range(4), range(4))
return qc
def avg_cut(gamma, beta, shots=1000):
counts = AerSimulator().run(qaoa_circuit(gamma, beta), shots=shots).result().get_counts()
total = 0
for b, c in counts.items():
bits = [int(x) for x in b[::-1]] # Qiskitは右端がqubit0
total += cut_value(bits) * c
return total / shots③ 最適なパラメータを探す
γ・βの2次元をグリッド探索して、平均カットが最大になる角度を見つけます。
best = (-1, 0, 0)
for g in np.linspace(0, np.pi, 20):
for be in np.linspace(0, np.pi / 2, 20):
v = avg_cut(g, be, 500)
if v > best[0]:
best = (v, g, be)
print("最良の平均カット:", round(best[0], 2))
# 最良パラメータで多めにサンプリング
counts = AerSimulator().run(qaoa_circuit(best[1], best[2]), shots=3000).result().get_counts()
top = sorted(counts.items(), key=lambda x: -x[1])[:2]
for b, c in top:
bits = [int(x) for x in b[::-1]]
print(b, "カット=", cut_value(bits), "回数=", c)出力はおおよそ:
最良の平均カット: 3.06
1010 カット= 4 回数= 841
0101 カット= 4 回数= 808最頻の答えが 1010 と 0101＝カット4の最適解。QAOAが最大カットを見つけました。
p を増やすと精度が上がる
今回はコスト＋ミキサーを1回だけ（p=1）。この2層を p 回繰り返すほど最適解に近づきます。ただしパラメータが増えて最適化は難しくなる——精度と学習コストのトレードオフです。
必ず古典に勝つわけではない
QAOAは"近似"アルゴリズムで、小さな問題では古典の厳密解や高性能ヒューリスティックに敵いません。「量子で最適化」の可能性を探る研究段階、というのが2026年の実情です。
まとめ
- QAOAはコスト層（Rzz）＋ミキサー層（Rx）を繰り返す変分アルゴリズム
- 最大カット問題を解いて
1010/0101（カット4）の最適解を発見 - p を増やすほど精度が上がるが最適化は難化
- NISQ期に現実的だが、古典に必ず勝つわけではない
📚 もう少し詳しく（背景と理論）気になる人向け・タップで開く
QAOA は Farhi, Goldstone, Gutmann (2014) が提案した組合せ最適化の変分アルゴリズムで1、コスト・ハミルトニアン（問題）とミキサー・ハミルトニアン（探索）を交互に p 回作用させます。p→∞ の極限では断熱量子計算に一致し最適解に収束しますが、実機では p は小さく抑えざるを得ません2。
p=1 でも MaxCut に近似保証（一定比率以上のカット）が示されていますが3、古典の Goemans–Williamson 近似（0.878）を一般に上回るかは未解決で、「量子優位」は限定的です。パラメータ最適化のコスト、バレンプラトー、ノイズも実用の壁で、現状は研究段階と位置づけられます4。
次の一歩 🌸
もう一つの変分アルゴリズムVQE入門、勾配計算はパラメータシフト則、専用機の量子アニーリングへどうぞ。
Footnotes
-
Farhi, E., Goldstone, J., Gutmann, S. (2014). "A Quantum Approximate Optimization Algorithm." arXiv:1411.4028. ↩
-
QAOA は断熱定理（Adiabatic Theorem）に基づく断熱量子計算の Trotter 化とみなせる。層数 p を増やすほど断熱極限＝厳密最適に近づく。 ↩
-
p=1 の QAOA は3-正則グラフの MaxCut で近似比 0.6924 以上を保証する（Farhi et al.）。ただし古典の Goemans–Williamson (1995) は 0.878 を保証しており、量子が一般に勝つとは示されていない。 ↩
-
小規模問題では古典の厳密解法・高性能ヒューリスティックに及ばないことが多い。QAOA の価値検証は活発な研究テーマ。 ↩