QAOA -- 量子近似优化算法(Quantum Approximate Optimization Algorithm)

使用 pyqpanda3 的量子近似优化算法解决组合优化问题。

问题

量子硬件上的组合优化

许多现实世界问题可以归结为在离散选择集合中寻找最佳分配。这些组合优化(Combinatorial Optimization)问题广泛出现在科学和工程中：

MaxCut -- 将图顶点分成两个集合以最大化跨越边数（网络设计、聚类）
MAX-SAT -- 找到满足布尔公式中最多个句子的变量赋值
投资组合优化(Portfolio Optimization) -- 在给定风险预算下选择使收益最大化的资产
调度(Scheduling) -- 在满足约束条件下将任务分配到时间槽

所有这些问题在最坏情况下都是 NP 困难的。经典精确求解器指数增长，而启发式近似不能提供通用性能保证。

为什么选择 QAOA？

量子近似优化算法(Quantum Approximate Optimization Algorithm, QAOA) 由 Farhi、Goldstone 和 Gutmann 于 2014 年提出，提供了一个产生具有可证明保证的近似解的框架。QAOA 制备参数化量子态并测量以产生候选解。经典优化器调整参数以改进解的质量。

QAOA 具有两个使其具有吸引力的性质：

性能保证 -- 在深度 $p = 1$ 时，QAOA 对 3-正则图上的 MaxCut 实现至少 0.6924 的近似比，超过了发表时已知的最佳经典算法。
硬件近期可行性 -- 每个 QAOA 层仅需浅层电路，双量子比特门与问题图结构匹配。

QAOA 框架

QAOA 将组合问题编码到代价哈密顿量(Cost Hamiltonian) $H_{C}$ 中，其基态对应最优解。它制备态

| γ, β ⟩ = \prod_{l = 1}^{p} e^{- i β_{l} H_{M}} e^{- i γ_{l} H_{C}} | + ⟩^{\otimes n}

其中：

$H_{C}$ 是编码目标函数的代价哈密顿量(Cost Hamiltonian)
$H_{M} = \sum_{i = 0}^{n - 1} X_{i}$ 是混合哈密顿量(Mixer Hamiltonian)
$γ = (γ_{1}, \dots, γ_{p})$ 和 $β = (β_{1}, \dots, β_{p})$ 是经典参数
$| + ⟩^{\otimes n} = H^{\otimes n} | 0 ⟩^{\otimes n}$ 是均匀叠加
$p$ 是 QAOA 深度（交替层数）

算法随后：

在计算基中测量 $| γ, β ⟩$ 获得候选比特串
在该比特串上评估经典目标
使用经典优化器调整 $(γ, β)$ 以最小化 $⟨ H_{C} ⟩$

当 $p \to \infty$ 时，QAOA 收敛到绝热路径并找到精确最优解。

方案

逐步 QAOA 方法

步骤 1：将问题表述为 Ising 哈密顿量

将组合目标表示为 Pauli $Z$ 算子的加权和。对于图 $G = (V, E)$ 上的 MaxCut：

H_{C} = \sum_{(i, j) \in E} \frac{1}{2} (I - Z_{i} Z_{j})

当量子比特 $i$ 和 $j$ 有不同值（ $Z_{i} Z_{j} = - 1$ ）时，每条边 $(i, j)$ 对切割贡献 $+ 1$ ；当它们相同（ $Z_{i} Z_{j} = + 1$ ）时贡献 $0$ 。

步骤 2：构建 p 层 QAOA Ansatz

构建交替两种酉操作的量子电路：

代价酉操作(Cost Unitary) $e^{- i γ_{l} H_{C}}$ ：在图边连接的量子比特之间施加 $R Z Z$ 门
混合酉操作(Mixer Unitary) $e^{- i β_{l} H_{M}}$ ：在所有量子比特上施加 $R X$ 旋转

步骤 3：定义代价函数

代价函数是 $H_{C}$ 对 QAOA 态的期望值：

C (γ, β) = ⟨ γ, β | H_{C} | γ, β ⟩

步骤 4：经典优化参数

使用经典优化器（COBYLA、Nelder-Mead、L-BFGS-B 等）找到使 $C (γ, β)$ 最小的 $(γ^{*}, β^{*})$ 。由于非凸性，推荐多次随机重启。

步骤 5：采样和解释结果

多次运行优化后的电路，对每个测量的比特串评估经典目标以找到最佳解。

代码

4 节点环图上的 MaxCut 与 QAOA p=1

我们在具有边 $(0, 1)$ 、 $(1, 2)$ 、 $(2, 3)$ 、 $(3, 0)$ 的 4 节点环图上演示完整的 QAOA 工作流程。最优 MaxCut 将顶点分为 ${0, 2}$ 和 ${1, 3}$ ，切割所有 4 条边。

定义问题图

python

from pyqpanda3 import core
import numpy as np

# Define a 4-vertex ring graph
edges = [(0, 1), (1, 2), (2, 3), (3, 0)]
n_qubits = 4
n_edges = len(edges)

print(f"Graph: {n_qubits} vertices, {n_edges} edges")
print(f"Edges: {edges}")
print(f"Optimal MaxCut value: {n_edges}")

构建代价哈密顿量

每条边贡献一个 $Z_{i} Z_{j}$ 项。当代价哈密顿量被最小化时，期望值趋近 $- | E |$ （所有边被切割）。

python

from pyqpanda3 import hamiltonian

# Cost Hamiltonian: H_C = sum_{(i,j) in E} Z_i Z_j
# When all edges are cut, Z_i Z_j = -1 for every edge,
# so H_C = -|E| (minimum value).
cost_terms = {}
for i, j in edges:
    cost_terms[f"Z{i} Z{j}"] = 1.0

cost_hamiltonian = hamiltonian.PauliOperator(cost_terms)
print(f"Cost Hamiltonian terms: {cost_terms}")

构建 QAOA 电路

环图上一个 QAOA 层的电路结构：

python

def build_qaoa_circuit(n_qubits: int, edges: list, gamma: list, beta: list) -> core.QProg:
    """
    Build a QAOA circuit for MaxCut.

    Args:
        n_qubits: Number of qubits (one per graph vertex).
        edges: List of (i, j) tuples defining graph edges.
        gamma: Cost parameters, one per QAOA layer.
        beta: Mixer parameters, one per QAOA layer.

    Returns:
        QProg containing the QAOA ansatz.
    """
    p = len(gamma)
    assert len(beta) == p, "gamma and beta must have the same length"

    prog = core.QProg()

    # Initialize in uniform superposition |+>^n
    for q in range(n_qubits):
        prog << core.H(q)

    for layer in range(p):
        # Cost unitary: e^{-i * gamma * H_C}
        # For each edge, apply RZZ(i, j, 2 * gamma)
        for i, j in edges:
            prog << core.RZZ(i, j, 2 * gamma[layer])

        # Mixer unitary: e^{-i * beta * sum X_i}
        # Apply RX on every qubit
        for q in range(n_qubits):
            prog << core.RX(q, 2 * beta[layer])

    return prog


# Test with p=1
p = 1
gamma_init = [0.5]
beta_init = [0.25]
test_prog = build_qaoa_circuit(n_qubits, edges, gamma_init, beta_init)
print("QAOA p=1 circuit built successfully")

定义代价函数

python

def qaoa_cost(params: np.ndarray, n_qubits: int, edges: list,
              p: int, cost_H: hamiltonian.PauliOperator) -> float:
    """
    Compute the QAOA cost function: expectation of H_C.

    Args:
        params: Flat array [gamma_0, ..., gamma_{p-1}, beta_0, ..., beta_{p-1}].
        n_qubits: Number of qubits.
        edges: Graph edges.
        p: Number of QAOA layers.
        cost_H: Cost Hamiltonian as a PauliOperator.

    Returns:
        Expectation value of the cost Hamiltonian.
    """
    gamma = params[:p].tolist()
    beta = params[p:2 * p].tolist()

    prog = build_qaoa_circuit(n_qubits, edges, gamma, beta)

    # Compute <H_C> using statevector expectation
    expectation = core.expval_pauli_operator(prog, cost_H)
    return expectation


# Evaluate at initial parameters
params_init = np.array(gamma_init + beta_init)
cost_0 = qaoa_cost(params_init, n_qubits, edges, p, cost_hamiltonian)
print(f"Initial cost at gamma={gamma_init}, beta={beta_init}: {cost_0:.6f}")

使用 scipy 优化

python

from scipy.optimize import minimize

# Multiple random restarts to avoid local minima
best_cost = float('inf')
best_params = None
n_restarts = 10

for restart in range(n_restarts):
    np.random.seed(restart)
    theta0 = np.random.uniform(0, np.pi, 2 * p)

    result = minimize(
        qaoa_cost,
        theta0,
        args=(n_qubits, edges, p, cost_hamiltonian),
        method='COBYLA',
        options={'maxiter': 300, 'rhobeg': 0.5}
    )

    if result.fun < best_cost:
        best_cost = result.fun
        best_params = result.x.copy()

    print(f"  Restart {restart}: cost = {result.fun:.6f}")

print(f"\nBest cost found (p=1): {best_cost:.6f}")
print(f"Best gamma: {best_params[:p]}")
print(f"Best beta:  {best_params[p:]}")

采样和解释结果

找到最优参数后，对电路进行采样以获得候选解：

python

# Build circuit at optimal parameters
optimal_gamma = best_params[:p].tolist()
optimal_beta = best_params[p:].tolist()
optimal_prog = build_qaoa_circuit(n_qubits, edges, optimal_gamma, optimal_beta)

# Add measurement and sample
optimal_prog << core.measure(list(range(n_qubits)), list(range(n_qubits)))

machine = core.CPUQVM()
n_shots = 10000
machine.run(optimal_prog, n_shots)
counts = machine.result().get_counts()

# Evaluate each bitstring's cut value
def compute_cut(bitstring: str, edges: list) -> int:
    """Count the number of edges crossing the cut defined by the bitstring."""
    return sum(1 for i, j in edges if bitstring[i] != bitstring[j])

print("\nTop solutions by frequency:")
sorted_counts = sorted(counts.items(), key=lambda x: x[1], reverse=True)

for bitstring, count in sorted_counts[:5]:
    cut = compute_cut(bitstring, edges)
    prob = count / n_shots
    print(f"  {bitstring}: cut={cut}, count={count}, probability={prob:.3f}")

# Find the overall best solution
best_cut = 0
best_bitstring = None
for bitstring, count in counts.items():
    cut = compute_cut(bitstring, edges)
    if cut > best_cut:
        best_cut = cut
        best_bitstring = bitstring

print(f"\nBest solution: {best_bitstring} with cut={best_cut}/{n_edges}")
print(f"Approximation ratio: {best_cut / n_edges:.4f}")

4 顶点环图 p=1 的预期输出：

Top solutions by frequency:
  0101: cut=4, count=1800, probability=0.180
  1010: cut=4, count=1750, probability=0.175
  0110: cut=2, count=800, probability=0.080
  ...
Best solution: 0101 with cut=4/4
Approximation ratio: 0.7500~1.0000

两个最优解（0101 和 1010）对应分区 ${0, 2}$ 与 ${1, 3}$ ，切割所有 4 条边。

p=2 的 QAOA 及与 p=1 的比较

增加 QAOA 深度 $p$ 添加更多变分参数，允许电路探索希尔伯特空间的更大区域。对于 $p$ 层，有 $2 p$ 个参数： $γ_{1}, \dots, γ_{p}, β_{1}, \dots, β_{p}$ 。

python

# Run QAOA with p=2 layers
p2 = 2
best_cost_p2 = float('inf')
best_params_p2 = None

for restart in range(10):
    np.random.seed(restart + 100)
    theta0 = np.random.uniform(0, np.pi, 2 * p2)

    result = minimize(
        qaoa_cost,
        theta0,
        args=(n_qubits, edges, p2, cost_hamiltonian),
        method='COBYLA',
        options={'maxiter': 500, 'rhobeg': 0.5}
    )

    if result.fun < best_cost_p2:
        best_cost_p2 = result.fun
        best_params_p2 = result.x.copy()

print(f"p=1 best cost: {best_cost:.6f}")
print(f"p=2 best cost: {best_cost_p2:.6f}")
print(f"Expected optimum (all edges cut): {-n_edges:.1f}")

近似比(Approximation Ratio) $α$ 衡量解的质量：

α = \frac{| ⟨ H_{C} ⟩_{QAOA} |}{MaxCut (G)}

python

# Approximation ratios
alpha_p1 = abs(best_cost) / n_edges
alpha_p2 = abs(best_cost_p2) / n_edges

print(f"Approximation ratio (p=1): {alpha_p1:.4f}")
print(f"Approximation ratio (p=2): {alpha_p2:.4f}")

对于 4 顶点环图，p=1 通常达到约 0.75~1.0 的近似比，而 p=2 更一致地接近 1.0。

通用 MaxCut 求解器函数

以下函数封装了适用于任意无向图的完整 QAOA 工作流程：

python

def solve_maxcut_qaoa(
    edges: list,
    n_qubits: int,
    p: int = 1,
    n_restarts: int = 20,
    maxiter: int = 300,
) -> dict:
    """
    Solve MaxCut using QAOA for an arbitrary undirected graph.

    Args:
        edges: List of (i, j) tuples defining the graph edges.
        n_qubits: Number of vertices.
        p: QAOA depth parameter.
        n_restarts: Number of random restarts for optimization.
        maxiter: Maximum optimizer iterations per restart.

    Returns:
        Dictionary with keys:
        - best_cost: minimum expectation value of cost Hamiltonian
        - best_params: optimal parameter array
        - best_cut: best classical cut value found by sampling
        - optimal_cut: maximum possible cut value (= number of edges for ring)
        - approximation_ratio: best_cut / optimal_cut
        - counts: measurement counts from the optimal circuit
    """
    # Build cost Hamiltonian
    cost_terms = {f"Z{i} Z{j}": 1.0 for i, j in edges}
    cost_H = hamiltonian.PauliOperator(cost_terms)

    best_cost = float('inf')
    best_params = None

    for restart in range(n_restarts):
        np.random.seed(restart)
        theta0 = np.random.uniform(0, np.pi, 2 * p)

        def cost_fn(params):
            gamma = params[:p].tolist()
            beta = params[p:2 * p].tolist()
            prog = build_qaoa_circuit(n_qubits, edges, gamma, beta)
            return core.expval_pauli_operator(prog, cost_H)

        result = minimize(cost_fn, theta0, method='COBYLA',
                          options={'maxiter': maxiter, 'rhobeg': 0.5})

        if result.fun < best_cost:
            best_cost = result.fun
            best_params = result.x.copy()

    # Sample the optimal circuit
    gamma = best_params[:p].tolist()
    beta = best_params[p:].tolist()
    optimal_prog = build_qaoa_circuit(n_qubits, edges, gamma, beta)
    optimal_prog << core.measure(list(range(n_qubits)), list(range(n_qubits)))

    machine = core.CPUQVM()
    machine.run(optimal_prog, 10000)
    counts = machine.result().get_counts()

    # Find best bitstring by classical evaluation
    best_cut = 0
    for bitstring in counts:
        cut = sum(1 for i, j in edges if bitstring[i] != bitstring[j])
        best_cut = max(best_cut, cut)

    return {
        'best_cost': best_cost,
        'best_params': best_params,
        'best_cut': best_cut,
        'optimal_cut': len(edges),
        'approximation_ratio': best_cut / len(edges),
        'counts': counts,
    }


# Example 1: 5-vertex path graph
path_edges = [(0, 1), (1, 2), (2, 3), (3, 4)]
result_path = solve_maxcut_qaoa(path_edges, n_qubits=5, p=2)
print(f"Path graph: cut={result_path['best_cut']}/{result_path['optimal_cut']}, "
      f"ratio={result_path['approximation_ratio']:.4f}")

# Example 2: 6-vertex complete graph K_3,3
k33_edges = [(i, j) for i in range(3) for j in range(3, 6)]
result_k33 = solve_maxcut_qaoa(k33_edges, n_qubits=6, p=2)
print(f"K_3,3 graph: cut={result_k33['best_cut']}/{result_k33['optimal_cut']}, "
      f"ratio={result_k33['approximation_ratio']:.4f}")

从测量样本评估切割值

用于计算测量比特串的经典切割值的辅助函数：

python

def evaluate_cut_distribution(counts: dict, edges: list) -> dict:
    """
    Analyze the cut value distribution from QAOA measurement counts.

    Args:
        counts: Dictionary mapping bitstrings to measurement counts.
        edges: Graph edges as list of (i, j) tuples.

    Returns:
        Dictionary with cut value statistics.
    """
    total_shots = sum(counts.values())
    cut_counts = {}
    total_cut = 0

    for bitstring, count in counts.items():
        cut = compute_cut(bitstring, edges)
        cut_counts[cut] = cut_counts.get(cut, 0) + count
        total_cut += cut * count

    avg_cut = total_cut / total_shots
    max_cut = max(cut_counts.keys())
    optimal_cut = len(edges)

    print("Cut value distribution:")
    for cut_val in sorted(cut_counts.keys(), reverse=True):
        cnt = cut_counts[cut_val]
        bar = '#' * int(50 * cnt / total_shots)
        print(f"  cut={cut_val}: {cnt:5d} ({cnt/total_shots:.3f}) {bar}")

    print(f"\nAverage cut value: {avg_cut:.4f}")
    print(f"Best cut found:    {max_cut}")
    print(f"Optimal cut:       {optimal_cut}")
    print(f"Approximation ratio: {max_cut / optimal_cut:.4f}")

    return {
        'avg_cut': avg_cut,
        'max_cut': max_cut,
        'cut_counts': cut_counts,
    }


# Example usage with p=1 results
optimal_prog_eval = build_qaoa_circuit(n_qubits, edges, best_params[:1].tolist(), best_params[1:].tolist())
optimal_prog_eval << core.measure(list(range(n_qubits)), list(range(n_qubits)))

machine = core.CPUQVM()
machine.run(optimal_prog_eval, 10000)
counts_p1 = machine.result().get_counts()
evaluate_cut_distribution(counts_p1, edges)

解析

QAOA 电路结构：交替的代价和混合层

QAOA 电路由 $p$ 个相同的"块"组成，每个包含一个代价酉操作后跟一个混合酉操作。这种结构反映了量子退火的 Trotter 化。

代价酉操作

代价酉操作实现 $e^{- i γ H_{C}}$ 。对于 MaxCut 代价哈密顿量 $H_{C} = \sum_{(i, j) \in E} Z_{i} Z_{j}$ ，代价酉操作分解为双量子比特门的乘积：

e^{- i γ \sum_{(i, j)} Z_{i} Z_{j}} = \prod_{(i, j) \in E} e^{- i γ Z_{i} Z_{j}} = \prod_{(i, j) \in E} R Z Z (i, j, 2 γ)

每个 $R Z Z$ 门是绕 $Z Z$ 轴的旋转：

R Z Z (θ) = e^{- i \frac{θ}{2} Z \otimes Z} = (\begin{matrix} e^{- i θ / 2} & 0 & 0 & 0 \\ 0 & e^{i θ / 2} & 0 & 0 \\ 0 & 0 & e^{i θ / 2} & 0 \\ 0 & 0 & 0 & e^{- i θ / 2} \end{matrix})

混合酉操作

混合酉操作实现 $e^{- i β H_{M}}$ ，其中 $H_{M} = \sum_{i} X_{i}$ 。由于 $X_{i}$ 算子对易（作用在不同量子比特上），它分解为单量子比特门：

e^{- i β \sum_{i} X_{i}} = \prod_{i = 0}^{n - 1} e^{- i β X_{i}} = \prod_{i = 0}^{n - 1} R X (i, 2 β)

每个 $R X$ 旋转通过创建叠加来探索解空间：

R X (θ) = e^{- i \frac{θ}{2} X} = (\begin{matrix} \cos (θ / 2) & - i \sin (θ / 2) \\ - i \sin (θ / 2) & \cos (θ / 2) \end{matrix})

完整层结构

一个 QAOA 层（ $p = 1$ ）施加：

所有 $n$ 个量子比特上的 Hadamard： $| 0 ⟩^{\otimes n} \to | + ⟩^{\otimes n}$
代价酉操作：所有边上的 $R Z Z$ 门，角度 $2 γ_{1}$
混合酉操作：所有量子比特上的 $R X$ ，角度 $2 β_{1}$

对于 $p$ 层，步骤 2 和 3 以不同的参数 $(γ_{l}, β_{l})$ 对每层 $l$ 重复。

与量子退火的关系

QAOA 可以理解为量子退火(Quantum Annealing)（也称为量子绝热算法）的离散化版本。在量子退火中，系统在含时哈密顿量下缓慢演化：

H (t) = (1 - \frac{t}{T}) H_{M} + \frac{t}{T} H_{C}

从 $H_{M}$ 的基态（均匀叠加）开始，到 $H_{C}$ 的基态（最优解）结束。

通过将这种连续演化 Trotter 化为 $p$ 个离散步骤，我们得到恰好是 QAOA 电路。每个 QAOA 层对应一个 Trotter 步骤：

e^{- i H (t) Δ t} \approx e^{- i γ_{l} H_{C}} e^{- i β_{l} H_{M}}

其中 $γ_{l}$ 和 $β_{l}$ 与退火调度和时间步长相关。

关键洞察：当 $p \to \infty$ 时，QAOA 精确重现绝热路径，保证收敛到最优解（假设满足绝热条件）。对于有限 $p$ ，参数 $(γ, β)$ 可自由优化，这实际上可能比退火路径的朴素 Trotter 化产生更好的结果。

近似比分析

近似比(Approximation Ratio) $α$ 量化 QAOA 解与真实最优解的接近程度：

α = \frac{E [QAOA 切割值]}{MaxCut (G)}

理论保证

图类型	QAOA 深度	近似比	参考
3-正则	$p = 1$	$α \geq 0.6924$	Farhi 等人 (2014)
3-正则	$p = 2$	$α \geq 0.7574$	Wurtz 和 Love (2021)
3-正则	$p \to \infty$	$α \to 1.0$	收敛保证
一般	$p = 1$	$α > 0.5$ （超过随机）	通用界限

作为比较，经典 Goemans-Williamson 算法对一般图达到 $α \geq 0.8785$ ，但预期 QAOA 在特定图族和量子硬件上具有竞争力。

实际观察

在小图（4~8 顶点）上， $p = 1$ ~ $2$ 的 QAOA 通常达到：

环图： $p = 1$ 时 $α \approx 0.75$ ~ $1.0$ ， $p = 2$ 时接近 $1.0$
路径图： $p = 1$ 时 $α \approx 0.8$ ~ $1.0$
完全图： $p = 2$ 时 $α \approx 0.7$ ~ $0.9$

参数初始化策略

初始参数的选择显著影响收敛速度和解的质量。以下是几种策略：

策略 1：均匀随机

python

theta0 = np.random.uniform(0, np.pi, 2 * p)

简单且无偏。多次重启效果好，但对某些图收敛可能较慢。

策略 2：退火启发

初始化参数以近似线性退火调度：

python

# gamma decreases, beta increases (or vice versa)
gamma_init = np.linspace(np.pi / (2 * p), 0, p)
beta_init = np.linspace(0, np.pi / (2 * p), p)
theta0 = np.concatenate([gamma_init, beta_init])

这模拟了绝热路径，通常比随机初始化收敛更快。

策略 3：从较低 p 插值

使用深度 $p - 1$ 的最优参数初始化深度 $p$ ：

python

def interp_from_lower_p(optimal_params_p1, p_new):
    """
    Initialize p_new parameters by interpolating from p=1 optimal.
    Insert a new layer at the midpoint of the annealing schedule.
    """
    gamma_old, beta_old = optimal_params_p1[:1], optimal_params_p1[1:]
    # For p=2, duplicate the p=1 parameters as starting point
    gamma_new = np.concatenate([gamma_old, gamma_old])
    beta_new = np.concatenate([beta_old, beta_old])
    return np.concatenate([gamma_new, beta_new])

theta0_p2 = interp_from_lower_p(best_params, p_new=2)

策略 4：网格搜索热启动

对于小 $p$ ，扫描 $(γ, β)$ 值的粗网格并从最佳网格点启动优化器：

python

def grid_search_init(n_qubits, edges, p, cost_H, grid_size=20):
    """Find the best starting point from a coarse grid."""
    best_energy = float('inf')
    best_theta = None

    gamma_vals = np.linspace(0, np.pi, grid_size)
    beta_vals = np.linspace(0, np.pi / 2, grid_size)

    for g in gamma_vals:
        for b in beta_vals:
            theta = np.array([g] * p + [b] * p)
            energy = qaoa_cost(theta, n_qubits, edges, p, cost_H)
            if energy < best_energy:
                best_energy = energy
                best_theta = theta.copy()

    return best_theta, best_energy

grid_theta, grid_energy = grid_search_init(n_qubits, edges, p, cost_hamiltonian)
print(f"Grid search best: cost={grid_energy:.6f} at {grid_theta}")

问题规模和 QAOA 深度的标度

电路规模

QAOA 电路中的门数量标度为：

组件	门数量	每层
初始化	$n$	$n$ 个 Hadamard 门
代价酉操作	$\| E \|$	$\| E \|$ 个 RZZ 门（每条边一个）
混合酉操作	$n$	$n$ 个 RX 门
每层总计	$n + \| E \|$	单加双量子比特门
$p$ 层总计	$n + p (n + \| E \|)$	包括初始化

对于 $| E | = O (n^{2})$ 条边的稠密图，电路深度为 $O (p n^{2})$ 。对于 $| E | = O (n)$ 的稀疏图，深度为 $O (p n)$ 。

经典优化代价

经典优化代价取决于：

参数数量： $2 p$ 个参数待优化
每次评估代价：一次电路执行加期望值计算
优化器迭代：COBYLA 通常 $O (100)$ ~ $O (1000)$
重启次数：推荐 10~50 次

总代价： $O (restarts \times iterations \times cost_per_eval)$

MaxCut 标度表

量子比特	边数（环）	p=1 参数	p=1 门数	p=2 参数	p=2 门数	模拟时间估计
4	4	2	12	4	20	< 1 sec
8	8	2	24	4	40	~1 sec
16	16	2	48	4	80	~10 sec
20	20	2	60	4	100	~1 min
25	25	2	75	4	125	~5 min

模拟时间假设 20 次重启，每次 300 COBYLA 迭代。

与 QAOA 理论保证的联系

Farhi-Goldstone-Gutmann 定理

原始 QAOA 论文确立了对任意固定 $p$ ，QAOA 产生态 $| γ, β ⟩$ 使得测量到最优解的概率至少为 $Ω (1 / poly (n))$ （对某些问题类）。这意味着 QAOA 可以用多项式数量的采样获得最优解。

集中性质(Concentration Property)

对许多图族（包括随机正则图），QAOA 输出的代价分布随问题规模增长集中在其均值附近：

Pr [| \frac{C (x)}{E [C]} - 1 | > ϵ] \to 0 当 n \to \infty

这意味着准确测量期望值 $⟨ H_{C} ⟩$ 可以预测采样解的典型切割值。

量子优势前景

QAOA 是在优化问题上展示量子优势的主要候选。理论证据表明：

浅层电路（ $p = 1, 2$ ）已经可以在特定图族上匹配或超过简单经典启发式。
在中等深度（ $p \in [10, 20]$ ），QAOA 可能在某些图类上超越最佳经典近似算法。
热启动 QAOA 使用经典计算的解（如 Goemans-Williamson）可以提升性能。

局限性

贫瘠高原：对很深的电路（ $p ≫ 1$ ），梯度可能指数衰减，使优化不可行。
噪声敏感性：在真实硬件上，门误差随深度累积，限制了实际可行的 $p$ 值。
经典竞争：先进经典算法（半定规划、张量网络）在许多问题规模上仍具有竞争力。

将 QAOA 适配到其他问题

QAOA 框架不限于 MaxCut。任何可以表示为局域项之和的组合问题都可以编码。

MAX-2-SAT

2-SAT 子句 $(x_{i} \lor x_{j})$ 映射到哈密顿量：

H_{i j} = \frac{1}{2} (I - Z_{i}) + \frac{1}{4} (I + Z_{i}) (I + Z_{j}) - \frac{1}{2} (I - Z_{i}) (I - Z_{j})

简化为 $Z_{i}$ 、 $Z_{j}$ 和 $Z_{i} Z_{j}$ 项之和。QAOA 电路使用相同的 $R Z Z$ 和 $R X$ 门。

加权 MaxCut

为每条边分配权重 $w_{i j}$ ：

H_{C} = \sum_{(i, j) \in E} w_{i j} Z_{i} Z_{j}

唯一的变化在 PauliOperator 系数中；电路结构完全相同。

投资组合优化

资产选择的二进制编码映射为：

H_{C} = - μ^{T} x + λ x^{T} Σ x

其中 $μ$ 是期望收益， $Σ$ 是协方差矩阵。这产生 $Z_{i}$ （线性）和 $Z_{i} Z_{j}$ （二次）项。

总结

概念	在 pyqpanda3 中的实现
代价哈密顿量	`hamiltonian.PauliOperator({"Z0 Z1": 1.0, ...})`
代价酉操作	每条边 `core.RZZ(i, j, 2 * gamma)`
混合酉操作	每个量子比特 `core.RX(q, 2 * beta)`
期望值	`core.expval_pauli_operator(prog, cost_H)`
采样	`core.CPUQVM().run(prog, shots); result.get_counts()`
经典优化	`scipy.optimize.minimize` 配合 COBYLA

后续步骤

变分电路 -- 构建和微分参数化电路
模拟 -- 为问题规模选择合适的模拟器
哈密顿量与 Pauli 算子 -- 定义可观测量和期望值
噪声模拟 -- 在真实噪声模型下运行 QAOA

QAOA -- 量子近似优化算法(Quantum Approximate Optimization Algorithm) ​

问题 ​

量子硬件上的组合优化 ​

为什么选择 QAOA？ ​

QAOA 框架 ​

方案 ​

逐步 QAOA 方法 ​

步骤 1：将问题表述为 Ising 哈密顿量 ​

步骤 2：构建 p 层 QAOA Ansatz ​

步骤 3：定义代价函数 ​

步骤 4：经典优化参数 ​

步骤 5：采样和解释结果 ​

代码 ​

4 节点环图上的 MaxCut 与 QAOA p=1 ​

定义问题图 ​

构建代价哈密顿量 ​

构建 QAOA 电路 ​

定义代价函数 ​

使用 scipy 优化 ​

采样和解释结果 ​

p=2 的 QAOA 及与 p=1 的比较 ​

通用 MaxCut 求解器函数 ​

从测量样本评估切割值 ​

解析 ​

QAOA 电路结构：交替的代价和混合层 ​

代价酉操作 ​

混合酉操作 ​

完整层结构 ​

与量子退火的关系 ​

近似比分析 ​

理论保证 ​

实际观察 ​

参数初始化策略 ​

策略 1：均匀随机 ​

策略 2：退火启发 ​

策略 3：从较低 p 插值 ​

策略 4：网格搜索热启动 ​

问题规模和 QAOA 深度的标度 ​

电路规模 ​

经典优化代价 ​

MaxCut 标度表 ​

与 QAOA 理论保证的联系 ​

Farhi-Goldstone-Gutmann 定理 ​

集中性质(Concentration Property) ​

量子优势前景 ​

局限性 ​

将 QAOA 适配到其他问题 ​

MAX-2-SAT ​

加权 MaxCut ​

投资组合优化 ​

总结 ​

后续步骤 ​

QAOA -- 量子近似优化算法(Quantum Approximate Optimization Algorithm)

问题

量子硬件上的组合优化

为什么选择 QAOA？

QAOA 框架

方案

逐步 QAOA 方法

步骤 1：将问题表述为 Ising 哈密顿量

步骤 2：构建 p 层 QAOA Ansatz

步骤 3：定义代价函数

步骤 4：经典优化参数

步骤 5：采样和解释结果

代码

4 节点环图上的 MaxCut 与 QAOA p=1

定义问题图

构建代价哈密顿量

构建 QAOA 电路

定义代价函数

使用 scipy 优化

采样和解释结果

p=2 的 QAOA 及与 p=1 的比较

通用 MaxCut 求解器函数

从测量样本评估切割值

解析

QAOA 电路结构：交替的代价和混合层

代价酉操作

混合酉操作

完整层结构

与量子退火的关系

近似比分析

理论保证

实际观察

参数初始化策略

策略 1：均匀随机

策略 2：退火启发

策略 3：从较低 p 插值

策略 4：网格搜索热启动

问题规模和 QAOA 深度的标度

电路规模

经典优化代价

MaxCut 标度表

与 QAOA 理论保证的联系

Farhi-Goldstone-Gutmann 定理

集中性质(Concentration Property)

量子优势前景

局限性

将 QAOA 适配到其他问题

MAX-2-SAT

加权 MaxCut

投资组合优化

总结

后续步骤