QAOA 详解：一步步求解 Max-Cut

QAOA（量子近似优化算法）是最受追捧的近期量子算法之一——这是有充分理由的。它是组合优化问题上实现量子优势的真正候选者，能在当今的 NISQ 硬件上运行，而且简单到可以在一个下午内实现。

本指南从零开始构建完整的 QAOA 流程，以 Max-Cut 作为示例问题。读完之后，你将理解 QAOA 究竟做了什么、如何实现它，以及何时值得使用它。

什么是 Max-Cut？

Max-Cut 是一个图划分问题：给定一个图，将节点分成两组（0 和 1），以最大化跨越两组之间的边的数量。它在一般情况下是 NP-hard 的，出现在 VLSI 芯片设计、聚类和网络分析中，并且能够干净地映射到量子硬件上。

这是一个简单的 4 节点图：

0 --- 1
|   \ |
3 --- 2

这个图的最大割是 4（边 0-1、1-2、2-3、3-0 全部跨越）。我们的目标：找到实现这一结果的比特串 0101 或 1010。

QAOA 的思想

QAOA 是一种变分混合算法。它交替执行两个参数化操作：

1. 问题酉算子 U_C(γ) —— 将代价函数（边的跨越）编码为相位回踢
2. 混合酉算子 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=3 或更高。在 NISQ QPU 上，p=1 或 p=2 通常是实际的上限。

QAOA 何时值得使用？

目前适用于：

• 对 NISQ 设备进行基准测试（QAOA 是一种标准的基准电路）
• 关于变分量子算法的学术研究
• 模拟器上的小型图（少于 20 个节点）

尚不适用于：

• 大规模真实硬件上的生产级优化——经典启发式方法（模拟退火、禁忌搜索）在实际问题上仍然优于 QAOA
• 大型图——电路深度随图的密度而增长

前景展望： 在未来具备高深度电路的容错硬件上，大 p 的 QAOA 可能为稠密的 NP-hard 优化提供真正的加速。其理论基础是扎实的；只是硬件还未跟上。

后续步骤

• PennyLane SDK 指南 —— 设置 PennyLane 以运行更多变分算法
• VQE 指南 —— 面向量子化学的姊妹算法
• HLQuantum —— 用一套 API 在任意后端上运行 QAOA