量子近似优化算法（QAOA）¶

量子近似优化算法（Quantum Approximate Optimization Algorithms, QAOA）是一类变分量子算法，旨在为组合优化问题寻找近似解。这类算法的研究价值颇高，因为它们被认为非常适配近期量子计算机（即NISQ设备，Noisy Intermediate-Scale Quantum devices）。

以下是其基本原理：

问题编码（Problem Encoding）：首先需将经典优化问题转化为量子问题。这一过程通常涉及将问题的目标函数映射为一个哈密顿量（Hamiltonian），该哈密顿量常被称为“成本哈密顿量”（cost Hamiltonian，记为Hp）。例如，在最大割问题（Max-Cut problem）中，目标是将图的顶点划分为两个集合，使得两个集合之间的边数最大化；该问题可映射为伊辛模型（Ising-type）的哈密顿量。
变分ansatz（Variational Ansatz）：QAOA采用量子电路作为变分ansatz（“ansatz”指量子态的试探性表达式，可理解为“量子电路模板”）。该电路通过交替应用两类操作（或称为“层”）构建而成，且需重复多次；这些层由角度参数（$\gamma, \beta$）控制，这些参数由经典优化器优化。QAOA变分ansatz的层操作如下：
- 成本哈密顿量层（Hp层）：该层在特定时间内应用成本哈密顿量（Hp），时间由参数“$\gamma$”调控。其作用是将问题的约束条件与目标函数编码到量子态中。
- 混合哈密顿量层（Hx层）：该层在特定时间内应用“混合哈密顿量”（mixing Hamiltonian，记为Hx）——通常是对每个量子比特施加泡利-X（Pauli-X）算子的总和，时间由参数“$\beta$”调控。此层的作用是探索解空间并产生叠加态，使算法能够在不同的潜在解之间切换。
上述两层操作重复“p”次（“p”为电路深度），构成QAOA变分ansatz的核心。通常而言，“p”值越大，近似解的精度越高，但也需要更深的量子电路（对量子设备的硬件要求更高）。
测量与期望值（Measurement and Expectation Value）：将QAOA电路作用于初始量子态（通常为所有可能状态的叠加态，例如所有计算基态的等权叠加态）后，需对得到的量子态进行测量。测量结果用于估算成本哈密顿量的期望值——该期望值对应当前参数集所找到解的“质量”（即解与最优解的接近程度）。
经典优化循环（Classical Optimization Loop）：变分算法的核心思想是利用经典优化器寻找最优参数，具体流程如下：
- 由经典计算机为参数（gamma和beta）选择初始值；
- 量子计算机使用这些参数执行QAOA电路；
- 量子计算机对结果进行测量，并将估算出的期望值（或成本值）反馈给经典计算机；
- 经典优化器根据反馈调整参数，以最小化该期望值——这一过程本质是寻找能使原始问题接近最优解的最佳角度组合。上述步骤会迭代重复，直至满足收敛条件（例如参数调整幅度小于阈值、期望值不再显著下降等）。
解提取（Solution Extraction）：当经典优化器找到最优参数后，使用这些参数运行QAOA电路，并在计算基下对输出量子态进行多次测量。测量频率最高的比特串（或一组比特串）即被视为经典优化问题的近似解。

本质上，QAOA的工作逻辑是：将经典优化问题转化为量子问题，以参数化量子电路作为解的“试探模板”，再通过经典优化器不断优化电路参数，最终找到尽可能优的近似解。

QAOA（量子近似优化算法）原理详细解析¶

QAOA（Quantum Approximate Optimization Algorithm，量子近似优化算法）是当前NISQ（含噪声中等规模量子）时代解决组合优化问题的核心算法之一。以下将从问题定位、核心思想、算法步骤和有效性分析四个维度，结合公式推导与原理拆解，系统阐述其工作机制。

1. 它要解决什么问题？——组合优化的“量子方案”¶

QAOA的核心应用场景是组合优化问题：这类问题的本质是在离散的、指数级增长的解空间中，寻找满足目标函数的最优解（或近似最优解）。经典计算机在问题规模扩大时（如顶点数>20），会因“指数爆炸”陷入计算瓶颈，而QAOA旨在利用量子特性突破这一限制。

典型的组合优化问题包括：

最大割问题（Max-Cut）：将图的顶点分为两组，使两组间连接的边数最多；
旅行商问题（TSP）：寻找访问所有城市并返回起点的最短路径；
其他场景：蛋白质折叠、物流调度、金融投资组合优化等NP-Hard问题。

这类问题的共性可抽象为：给定二进制解向量 z = (z₁, z₂, ..., zₙ)（zᵢ ∈ {0,1}），需最小化（或最大化）目标函数 C(z)。QAOA的目标就是通过量子电路制备编码最优解的量子态，最终通过测量输出近似最优的 z。

2. 核心思想：量子绝热定理与参数化量子电路的结合¶

QAOA的灵感来源于量子绝热计算（AQC），但通过“数字化改造”规避了AQC对“缓慢演化”的严苛要求，核心是“用参数化电路模拟绝热过程，用经典优化器优化电路参数”。

2.1 量子绝热定理的核心逻辑¶

量子绝热定理是QAOA的理论基础，其核心表述为：
若量子系统初始处于简单哈密顿量 H_B 的基态（易制备），且系统哈密顿量从 H_B 缓慢演化到复杂哈密顿量 H_C（其基态对应问题最优解），则系统始终保持在瞬时基态，最终会停留在 H_C 的基态。

其中两个关键哈密顿量的定义的作用：

问题哈密顿量 H_C：需与目标函数 C(z) 一一对应，满足 H_C |z⟩ = C(z) |z⟩（|z⟩ 是编码二进制解 z 的计算基态，如 |011⟩ 对应 z=(0,1,1)）。因此，H_C 的基态（能量最低态）就是目标函数 C(z) 最小化的解。
混合哈密顿量 H_B：通常取所有量子比特的X泡利算符之和，即 H_B = Σ_{i=1}^n X_i（X_i 是第 i 个量子比特的泡利X算符）。其基态为 |+⟩^⊗n = (|0⟩+|1⟩)/√2 ⊗ ... ⊗ (|0⟩+|1⟩)/√2，是所有计算基态的均匀叠加态，可通过对所有量子比特施加H门直接制备。

2.2 从“绝热演化”到“参数化电路”的改造¶

AQC的核心缺陷是“演化需足够缓慢”——这会导致电路深度极深，在噪声量子设备上无法实现。QAOA的关键创新是将“连续的绝热演化”转化为离散的参数化量子电路，具体思路为：

用 p 层重复的“相位分离+混合”门序列，近似模拟从 H_B 到 H_C 的绝热演化；
电路中的演化“时间”转化为可优化的参数（β₁,...,βₚ 和 γ₁,...,γₚ）；
用经典优化器迭代调整参数，最小化 H_C 的期望值，等价于寻找最优解。

这是一种典型的混合量子-经典范式：量子处理器负责制备量子态并测量能量，经典处理器负责优化参数，二者协同完成优化。

3. 算法步骤：四步实现量子近似优化¶

QAOA的完整流程可分为“问题映射”“电路构建”“经典优化”“结果输出”四个步骤，以下结合公式与实例详细说明。

步骤1：将经典问题映射到量子哈密顿量 `H_C`¶

核心目标是构造 H_C，使其能量与目标函数 C(z) 完全对应。对于任意二进制解 z，需满足：
$$H_C |z⟩ = C(z) |z⟩$$

此时，量子态 |ψ⟩ 下 H_C 的期望值为：
$$⟨ψ| H_C |ψ⟩ = Σ_{z} P(z) \cdot C(z)$$
其中 P(z) 是测量 |ψ⟩ 得到解 z 的概率。因此，最小化 ⟨ψ| H_C |ψ⟩ 等价于让高概率的解 z 对应更小的 C(z)，即逼近最优解。

实例（Max-Cut问题）：
对于含 n 个顶点、m 条边的图，边 (i,j) 的权重为 w_ij，Max-Cut的目标是最大化 $C(z) = (1/2)Σ_{(i,j)} w_{ij} (1 - z_i z_j)$（$z_i=-1/1$ 表示顶点 i 属于两组之一）。对应的问题哈密顿量为：
$$H_C = - (1/2)Σ_{(i,j)} w_{ij} (I - Z_i Z_j)$$
其中 Z_i 是第 i 个量子比特的泡利Z算符（Z|0⟩=|0⟩，Z|1⟩=-|1⟩），代入 |z⟩ 可验证 H_C |z⟩ = -C(z) |z⟩（最大化 C(z) 等价于最小化 ⟨ψ| H_C |ψ⟩）。

步骤2：构建QAOA参数化量子电路（Ansatz）¶

QAOA电路以 |+⟩^⊗n 为初始态，由 p 层相同的“相位分离算符+混合算符”组成，最终输出的量子态由参数 β = (β₁,...,βₚ) 和 γ = (γ₁,...,γₚ) 控制。

（1）两个核心算符的数学表达¶

相位分离算符 U_C(γ)：由 H_C 生成的幺正演化，作用是根据 C(z) 给不同基态添加相位：
$$U_C(γ) = e^{-iγ H_C}$$
由于 H_C 是对角化的（H_C = Σ_z C(z) |z⟩⟨z|），代入可得 U_C(γ) |z⟩ = e^{-iγ C(z)} |z⟩——即 C(z) 越小（解越优），相位变化越小，间接“保护”优质解。
混合算符 U_B(β)：由 H_B 生成的幺正演化，作用是在基态间产生跃迁，探索解空间：
$$U_B(β) = e^{-iβ H_B} = e^{-iβ Σ_{i=1}^n X_i} = ⊗_{i=1}^n e^{-iβ X_i}$$
其中 e^{-iβ X_i} 可通过“R_X(2β)”门实现（泡利X算符的旋转门），因此 U_B(β) 本质是对所有量子比特施加相同的R_X旋转，打破基态间的隔离，实现解的“混合与探索”。

（2）最终制备的量子态¶

p 层电路作用后，最终的量子态为：
$$|ψ(β, γ)⟩ = U_B(β_p) U_C(γ_p) \cdot ... \cdot U_B(β₁) U_C(γ₁) |+⟩^⊗n$$

其中 p 是QAOA的“层数”（也叫“深度”）：p 越大，电路对绝热演化的近似精度越高，但同时对量子设备的噪声容忍度要求也越高（NISQ时代通常取 p=1~5）。

步骤3：经典优化循环——迭代优化参数¶

这一步是QAOA的“反馈核心”：量子处理器负责计算 H_C 的期望值，经典处理器负责调整参数，循环直至收敛。具体流程如下：

初始化参数：随机选择初始参数 (β⁽⁰⁾, γ⁽⁰⁾)（如 β⁽⁰⁾_i = π/4，γ⁽⁰⁾_i = π/4）；
量子计算期望值：在量子计算机上运行参数为 (β⁽ᵏ⁾, γ⁽ᵏ⁾) 的电路，制备 |ψ(β⁽ᵏ⁾, γ⁽ᵏ⁾)⟩，并通过多次测量（采样 M 次）估算期望值：
$$F(β⁽ᵏ⁾, γ⁽ᵏ⁾) = ⟨ψ(β⁽ᵏ⁾, γ⁽ᵏ⁾)| H_C |ψ(β⁽ᵏ⁾, γ⁽ᵏ⁾)⟩ ≈ (1/M) Σ_{m=1}^M C(z⁽ᵐ⁾)$$
其中 z⁽ᵐ⁾ 是第 m 次测量得到的二进制解；
经典优化参数：将 F(β⁽ᵏ⁾, γ⁽ᵏ⁾) 作为优化目标，使用经典优化器（如梯度下降、Nelder-Mead、BFGS等）更新参数，得到 (β⁽ᵏ⁺¹⁾, γ⁽ᵏ⁺¹⁾)，满足 F(β⁽ᵏ⁺¹⁾, γ⁽ᵏ⁺¹⁾) ≤ F(β⁽ᵏ⁾, γ⁽ᵏ⁾)；
收敛判断：若 F(β⁽ᵏ⁾, γ⁽ᵏ⁾) 的变化量小于阈值（如 10⁻⁶），或达到最大迭代次数（如 100 次），则停止优化，得到最优参数 (β*, γ*)。

步骤4：输出结果——提取近似最优解¶

优化结束后，运行参数为 (β*, γ*) 的QAOA电路，对 |ψ(β*, γ*)⟩ 进行大量测量（如 1000 次）。由于此时 F(β*, γ*) 最小，测量结果中出现概率最高的二进制串 z*，即为问题的近似最优解。

例如，若测量结果中 z=(0101) 出现 300 次（概率 30%），z=(0110) 出现 250 次（概率 25%），则 z=(0101) 是最可能的近似最优解。

4. 为什么有效？——性能与挑战¶

QAOA的有效性源于其对量子绝热过程的“高效近似”，但实际性能受参数、层数、噪声等因素影响，需客观看待其优势与局限。

4.1 有效性的核心原因¶

理论保证（p→∞ 时）：当层数 p 趋近于无穷大时，QAOA的参数化电路可精确模拟绝热演化过程，根据量子绝热定理，最终态 |ψ(β*, γ*)⟩ 会收敛到 H_C 的基态，即找到精确最优解；
实际优势（有限 p 时）：即使 p 较小（如 p=2~3），QAOA也能通过量子干涉效应“增强优质解的概率”——优质解的相位因 U_C(γ) 变化更小，在 U_B(β) 的混合后更容易形成 constructive interference（相长干涉），从而在测量中以更高概率出现；
计算效率：相比经典算法（如模拟退火、遗传算法），QAOA可利用量子并行性同时探索多个解，在部分问题（如Max-Cut、TSP）上表现出更快的收敛速度，尤其在问题规模中等时（n=10~20）优势更明显。

4.2 关键挑战¶

参数优化的“贫瘠高原”问题：当量子比特数 n 增加时，参数空间的维度（2p）急剧扩大，优化目标函数 F(β, γ) 会陷入“平坦区域”（梯度接近0），导致经典优化器无法有效更新参数，优化效率骤降；
噪声的影响：NISQ设备的量子门操作存在误差（如门保真度 < 99%），p 越大，电路深度越深，误差累积越严重，最终导致测量结果的概率分布偏离理想情况，近似解的质量下降；
问题映射的复杂性：并非所有组合优化问题都能简单映射为 H_C——对于复杂问题（如带约束的调度问题），H_C 的构造可能需要引入辅助量子比特或复杂的泡利算符组合，增加了电路实现的难度。

总结¶

QAOA的本质是“量子模拟+经典优化”的协同框架：通过参数化量子电路近似量子绝热过程，将组合优化问题转化为“最小化哈密顿量期望值”的量子问题；再通过经典优化器迭代调整电路参数，最终以高概率输出近似最优解。

尽管目前受限于NISQ设备的噪声和“贫瘠高原”问题，但QAOA仍是量子计算在组合优化领域最具前景的算法之一——随着量子硬件的升级（如更高保真度的量子门、量子纠错技术）和优化策略的改进（如自适应参数初始化、梯度-free优化器），QAOA有望在未来解决经典计算机难以处理的大规模组合优化问题，在物流、金融、生物医药等领域发挥关键作用。

在QAOA（量子近似优化算法）中解决Max-Cut问题时，构建问题的哈密顿量（通常称为代价哈密顿量 $ H_C $）是核心步骤。其本质是将经典组合优化问题映射为量子系统的能量问题。以下是详细的构建过程：

1. Max-Cut 问题回顾¶

目标：给定无向图 $ G = (V, E) $（顶点集 $ V $，边集 $ E $），将顶点划分为两个子集 $ S $ 和 $ \bar{S} $，使得跨越 $ S $ 和 $ \bar{S} $ 的边数（即切割边数）最大化。
数学表达：最大化 $ \sum_{(i,j) \in E} \frac{1 - z_i z_j}{2} $，其中 $ z_i \in \{-1, +1\} $ 表示顶点 $ i $ 的归属（$ z_i = +1 $ 属于 $ S $，$ z_i = -1 $ 属于 $ \bar{S} $）。

2. 经典问题到量子哈密顿量的映射¶

QAOA 通过以下步骤将 Max-Cut 转化为量子问题：

(1) 变量量子化¶

每个顶点 $ i $ 对应一个量子比特 $ q_i $。
顶点归属 $ z_i $ 映射到量子比特的 计算基态：
- $ z_i = +1 $ → 量子态 $ |0\rangle $
- $ z_i = -1 $ → 量子态 $ |1\rangle $

(2) 代价函数量子化¶

Max-Cut 的目标函数 $ C = \sum_{(i,j) \in E} \frac{1 - z_i z_j}{2} $ 需转化为量子算符 $ H_C $：

将经典变量 $ z_i $ 替换为 泡利 $ Z $ 算符： $$ z_i \rightarrow Z_i = \begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix} $$
代入目标函数： $$ C \rightarrow H_C = \sum_{(i,j) \in E} \frac{1 - Z_i Z_j}{2} $$ 其中 $ Z_i Z_j $ 是作用在比特 $ i $ 和 $ j $ 上的张量积算符。

(3) 哈密顿量的物理意义¶

$ H_C $ 的本征值对应于经典切割的代价（切割边数）。
$ H_C $ 的基态（最小本征值）对应 最小切割，但 Max-Cut 需要最大化切割数，因此实际优化的是 $ -H_C $ 或等价地最小化 $ H_C $ 的负值。

3. 哈密顿量的显式形式¶

对于图 $ G $ 的每条边 $ (i,j) \in E $，定义局部哈密顿量： $$ H_C^{(i,j)} = \frac{1}{2} (I - Z_i Z_j) $$ 则全局代价哈密顿量为： $$ H_C = \sum_{(i,j) \in E} H_C^{(i,j)} = \sum_{(i,j) \in E} \frac{1}{2} (I - Z_i Z_j) $$

关键性质：¶

本征值：$ H_C^{(i,j)} $ 的本征值为 $ 0 $ 或 $ 1 $：
- 当比特 $ i $ 和 $ j $ 同态（$ |00\rangle $ 或 $ |11\rangle $）时，$ Z_i Z_j = +1 $，本征值 $ = 0 $（边未被切割）。
- 当比特 $ i $ 和 $ j $ 异态（$ |01\rangle $ 或 $ |10\rangle $）时，$ Z_i Z_j = -1 $，本征值 $ = 1 $（边被切割）。
期望值：对于量子态 $ |\psi\rangle $，$ \langle \psi | H_C | \psi \rangle $ 等于期望切割边数。

4. 示例：简单图的哈密顿量¶

考虑一个包含 3 个顶点和 2 条边的图 $ G $（边集 $ E = \{(1,2), (2,3)\} $）： $$ H_C = \frac{1}{2} (I - Z_1 Z_2) + \frac{1}{2} (I - Z_2 Z_3) $$ 展开后： $$ H_C = I - \frac{1}{2} Z_1 Z_2 - \frac{1}{2} Z_2 Z_3 $$¶

5. 在 QAOA 中的作用¶

在 QAOA 中：

初始态：均匀叠加态 $ |\psi_0\rangle = |+\rangle^{\otimes n} $（所有比特处于 $ |+\rangle = \frac{|0\rangle + |1\rangle}{\sqrt{2}} $）。
交替应用算符：
- 代价哈密顿量 $ H_C $：驱动系统向高切割数状态演化。
- 混合哈密顿量 $ H_B $：通常选 $ H_B = \sum_{i=1}^n X_i $（泡利 $ X $ 算符），引入量子隧穿效应。
参数优化：通过经典优化器调整参数 $ \vec{\gamma}, \vec{\beta} $，最大化 $ \langle \psi(\vec{\gamma}, \vec{\beta}) | H_C | \psi(\vec{\gamma}, \vec{\beta}) \rangle $。

6. 为什么选择泡利 $ Z $ 算符？¶

对角性：$ Z $ 算符在计算基下是对角的，其本征态直接对应经典解（$ |0\rangle $ 和 $ |1\rangle $）。
可观测性：$ H_C $ 是泡利 $ Z $ 的多项式，易于在量子计算机上测量（通过多次采样计算期望值）。
问题适配：Max-Cut 的目标函数天然与 $ Z_i Z_j $ 相关，能直接表达顶点间的关联。

总结¶

Max-Cut 的代价哈密顿量 $ H_C $ 构建步骤如下：

变量映射：顶点 $ i \rightarrow $ 量子比特 $ q_i $，归属 $ z_i \rightarrow Z_i $。
目标函数转化： $$ \text{Max-Cut} \rightarrow H_C = \sum_{(i,j) \in E} \frac{1}{2} (I - Z_i Z_j) $$
物理意义：$ H_C $ 的期望值等于期望切割边数，其基态对应最大割解。通过这种映射，QAOA 将经典组合优化问题转化为量子系统的能量最小化问题，利用量子叠加和干涉探索解空间，有望获得比经典算法更好的近似解。

TSP问题¶

量子近似优化算法（QAOA）解决旅行商问题（TSP）：代价哈密顿量构建详解¶

这是一个非常经典的问题，完美展示了如何将一个组合优化问题映射到量子计算框架中。

第一部分：QAOA 与 TSP 简介¶

TSP 问题：给定一系列城市和它们之间的距离，找到一条访问每个城市恰好一次并返回起点的最短路径。
QAOA 算法：一种用于解决组合优化问题的量子算法。其核心思想是：
- 将经典优化问题的代价函数映射成一个量子代价哈密顿量（$H_C$）。
- 准备一个参数化的量子态 $|\psi(\gamma, \beta)\rangle$，通过交替演化代价哈密顿量（$H_C$） 和混合哈密顿量（$H_B$） 来生成。
- 反复测量这个量子态，得到候选解（即可能的路径）。
- 使用经典优化器（如梯度下降）调整参数 $\gamma$ 和 $\beta$，以最小化期望值 $\langle\psi(\gamma, \beta)| H_C |\psi(\gamma, \beta)\rangle$，从而让量子态的概率分布集中在最优解（或近似最优解）附近。

整个流程的关键第一步，就是将 TSP 的代价和约束条件编码到哈密顿量 $H_C$ 中。

第二部分：代价哈密顿量 $H_C$ 的构建（核心部分）¶

构建 $H_C$ 的目的是：使得其基态（能量最低的状态）对应的解就是 TSP 的最短路径，并且所有满足约束的有效路径都具有明确的能量值（路径越长，能量越高），所有违反约束的无效路径都具有更高的能量作为惩罚。

我们采用最常用的 “二进制编码” 和 “惩罚项” 方法。

步骤 1：定义问题与变量编码¶

假设有 $N$ 个城市，标签为 $0$ 到 $N-1$。

我们需要多少量子比特？ 我们需要编码“哪个城市在旅行的哪个位置被访问”。因此，我们使用 $N^2$ 个量子比特。每个量子比特用一个二元变量 $z_{i, p}$ 表示： $z_{i, p} = 1$ 表示城市 $i$ 在第 $p$ 个位置被访问。 $z_{i, p} = 0$ 表示城市 $i$ 不在第 $p$ 个位置被访问。
- $i$: 城市索引（$i = 0, 1, ..., N-1$）
- $p$: 路径中的位置索引（$p = 0, 1, ..., N-1$）
有效解的条件（约束）：
1. 每个位置有且只有一个城市：对于任意位置 $p$，有且只有一个 $i$ 使得 $z_{i, p} = 1$。
2. 每个城市有且只被访问一次：对于任意城市 $i$，有且只有一个 $p$ 使得 $z_{i, p} = 1$。

步骤 2：构建代价函数（路径长度）¶

TSP 的目标是最小化总路径长度。总长度是相邻位置之间距离的总和。

设 $d_{i, j}$ 为城市 $i$ 和城市 $j$ 之间的距离。

从位置 $p$ 到位置 $p+1$ 的距离，取决于是哪两个城市在这两个位置上。具体来说，如果城市 $i$ 在位置 $p$，城市 $j$ 在位置 $p+1$，那么这段距离就是 $d_{i, j}$。

在量子比特编码下，“城市 $i$ 在位置 $p$” 即 $z_{i, p} = 1$。因此，连接位置 $p$ 和 $p+1$ 的边的成本可以表示为： $d_{i, j} \cdot z_{i, p} \cdot z_{j, p+1}$

只有当 $z_{i, p}$ 和 $z_{j, p+1}$ 同时为 1 时，这项才不为零。

对所有的城市 $i, j$ 和所有的位置 $p$（注意，路径是环，所以最后一个位置 $p = N-1$ 的下一个位置是 $p = 0$）求和，就得到了总路径长度的代价函数：

$H_{distance} = \sum_{p=0}^{N-1} \sum_{i=0}^{N-1} \sum_{j=0}^{N-1} d_{i, j} \cdot z_{i, p} \cdot z_{j, (p+1) \mod N}$

步骤 3：构建约束惩罚项¶

上面 $H_{distance}$ 只定义了目标，但没有施加约束。一个无效的解（比如一个城市被访问两次）也可能计算出路径长度，但这不是我们想要的。我们需要添加惩罚项（Penalty Terms），让违反约束的解具有非常高的能量（成本），从而被算法自然摒弃。

根据之前的两个约束，我们构造两个惩罚项：

每个位置一个城市约束（One city per position）：对于任意一个位置 $p$，所有城市对应的变量 $z_{i, p}$ 之和必须为 1。即 $\sum_i z_{i, p} = 1$。违反这个约束意味着和不为 1。我们可以用一个二次项来构造惩罚： $(\sum_i z_{i, p} - 1)^2$ 这个项只有在 $\sum_i z_{i, p} = 1$ 时为 0，否则为一个正数（惩罚）。对所有位置 $p$ 求和： $H_{position} = A \cdot \sum_{p=0}^{N-1} (\sum_{i=0}^{N-1} z_{i, p} - 1)^2$ （$A$ 是一个很大的常数，是惩罚权重）
每个城市一次访问约束（One visit per city）：对于任意一个城市 $i$，所有位置对应的变量 $z_{i, p}$ 之和必须为 1。即 $\sum_p z_{i, p} = 1$。同样，用二次项构造惩罚： $(\sum_p z_{i, p} - 1)^2$ 对所有城市 $i$ 求和： $H_{city} = A \cdot \sum_{i=0}^{N-1} (\sum_{p=0}^{N-1} z_{i, p} - 1)^2$ （使用相同的惩罚权重 $A$）

步骤 4：组合成总的代价哈密顿量 $H_C$¶

最终的代价哈密顿量 $H_C$ 由目标项（路径长度） 和惩罚项两部分组成：

$H_C = H_{distance} + H_{position} + H_{city}$

$H_C = \sum_{p} \sum_{i} \sum_{j} d_{i,j} z_{i,p} z_{j, (p+1) \mod N} + A \sum_{p} (\sum_i z_{i,p} - 1)^2 + A \sum_{i} (\sum_p z_{i,p} - 1)^2$

惩罚权重 $A$ 的选择至关重要：

$A$ 必须足够大，以确保任何违反约束的解的能量都高于所有遵守约束的解的能量。通常 $A$ 需要大于所有可能路径的最大长度（例如，$A > \max(d_{i,j}) \cdot N$）。
这样，QAOA 算法在最小化 $\langle H_C \rangle$ 时，会优先满足约束，然后再优化路径长度。

步骤 5：转换为伊辛模型形式（用于量子处理器）¶

目前的量子计算机（如超导量子比特）通常直接实现的是泡利算符的张量积。因此，我们需要将经典变量 $z_{i,p} \in \{0, 1\}$ 转换为量子比特的自旋算符 $Z_{i,p}$（本征值为 ±1）。

进行一个变量代换： $z_{i,p} = (1 - \sigma_{i,p}^z) / 2$ 其中 $\sigma_{i,p}^z$ 是作用在第 $(i, p)$ 个量子比特上的泡利-Z 算符，其本征值为 +1 (代表 $z=0$) 和 -1 (代表 $z=1$)。

将 $H_C$ 的表达式中的所有 $z_{i,p}$ 用 $(1 - \sigma^z)/2$ 替换，并展开所有平方项。经过一系列代数运算后，$H_C$ 会被完全展开成以下形式：

$H_C = \sum_{k} h_k \sigma_k^z + \sum_{k, l} J_{k,l} \sigma_k^z \sigma_l^z + constant$

这个形式就是伊辛模型（Ising Model） 的哈密顿量，它只包含泡利-Z 算符的单项式和双项式。其中的系数 $h_k$ (局部场) 和 $J_{k,l}$ (耦合强度) 都由距离 $d_{i,j}$ 和惩罚权重 $A$ 计算而来。

这个形式的 $H_C$ 就可以直接输入到 QAOA 电路中进行模拟演化（通过 $exp(-i \gamma H_C)$ 门操作），或者在某些量子退火器中直接实现。

总结与图示¶

假设有 3 个城市 (A, B, C)，我们需要 9 个量子比特。其代价哈密顿量 $H_C$ 的构建思想如下图所示：

H_C = H_distance + H_position + H_city

H_distance: 
  d_AB · (如果A在p0且B在p1) + d_AC · (如果A在p0且C在p1) + ...
  d_BA · (如果B在p0且A在p1) + ... （考虑所有相邻位置和城市对）

H_position (示例：对于位置p0):
  A · ( (Z_A0 + Z_B0 + Z_C0) - 1 )² 
  // 如果p0有且只有一个城市，此项为0，否则为正惩罚

H_city (示例：对于城市A):
  A · ( (Z_A0 + Z_A1 + Z_A2) - 1 )² 
  // 如果城市A有且只在一个位置，此项为0，否则为正惩罚

最终，这个 $H_C$ 的期望值 $\langle\psi| H_C |\psi\rangle$ 就是我们通过QAOA需要最小化的目标函数。 通过优化参数，量子态 $|\psi\rangle$ 会越来越倾向于表示那些短路径且符合约束的解，我们通过测量这个态就能高概率地得到TSP的近似最优解。

构建代价哈密顿量是将经典问题“量子化”最关键且最需要技巧的一步，本文描述的是最通用和直观的方法。

QAOA中的相位分离算符和混合算符¶

在量子近似优化算法 (QAOA) 中，我们交替地应用 问题哈密顿量 $H_C$ (Cost Hamiltonian) 和 混合哈密顿量 $H_M$ (Mixer Hamiltonian) 的旋转算符。问题哈密顿量 $H_C$ 的旋转算符 $U_C(\gamma) = \exp(-i \gamma H_C)$ 的物理意义和作用是什么呢？为什么它如此重要？

$U_C(\gamma)$ 的物理意义和作用¶

核心作用：利用问题哈密顿量的能量景观来指导优化过程，倾向于将量子态推向能量较低（对应优化问题中目标值更优）的区域。

为了更深入地理解，我们可以从以下几个方面来阐述：

能量景观的探索者：
- $H_C$ 的本质： 问题哈密顿量 $H_C$ 的定义与你正在尝试解决的组合优化问题紧密相关。它的能量本征值（eigenvalues）直接对应于优化问题的目标函数值。具体来说，$H_C$ 的本征态（eigenstates）是优化问题的一些可能解（通常是以量子态的形式表示），其对应的本征值就是这些解的目标函数值。
- 能量最低点： QAOA 的目标是找到一个量子态 $\ket{\psi}$，使得 $\bra{\psi} H_C \ket{\psi}$ 的期望值最小（或者最大，取决于问题设定）。这个期望值代表了量子态在问题哈密顿量下的平均能量。
- $U_C(\gamma)$ 的作用： $U_C(\gamma) = \exp(-i \gamma H_C)$ 是一个酉演化算符。当我们将一个量子态 $\ket{\psi}$ 通过这个算符演化时，它会根据 $H_C$ 的本征值和本征态来改变量子态的相位。具体而言，如果 $\ket{i}$ 是 $H_C$ 的一个本征态，其本征值为 $E_i$，那么 $U_C(\gamma) \ket{i} = \exp(-i \gamma E_i) \ket{i}$。
- 物理意义： 这种相位变化可以被理解为对量子态在能量景观上的“移动”或“偏转”。参数 $\gamma$ 控制着演化的“深度”或“幅度”。通过调整 $\gamma$，我们希望能够将量子态推向能量较低（对应于优化问题中“更好”的解）的区域。
相位编码和优化：
- 量子叠加态： QAOA 通常以一个均匀叠加态 $\ket{+}^{\otimes n}$（所有量子比特处于 $|+\rangle = (|0\rangle + |1\rangle)/\sqrt{2}$ 状态）开始。这个态代表了所有可能解的等概率叠加。
- 相位累积： 当量子态经历 $U_C(\gamma)$ 演化时，不同能量的本征态会获得不同的相位。对于能量较低的本征态，它们会积累一个特定的相位；而对于能量较高的本征态，它们会积累另一个相位。
- 干涉效应： QAOA 的另一个关键是 $H_M$ 及其算符 $U_M(\beta) = \exp(-i \beta H_M)$。$H_M$ 通常被选择为能够驱动量子比特在所有可能状态之间自由“行走”的哈密顿量（例如，$\sum_i X_i$）。$U_M(\beta)$ 的作用是将量子态的相位信息“混合”或“传播”到整个状态空间中。
- 关键机制： $U_C(\gamma)$ 负责根据优化问题的目标函数（即 $H_C$ 的本征值）来“标记”量子态的相位。而 $U_M(\beta)$ 则负责将这些相位标记“传播”出去，并通过干涉效应，增强（constructive interference）那些在 $H_C$ 作用下获得了特定相位（通常与最优解对应）的状态的概率振幅，同时削弱（destructive interference）其他状态的概率振幅。
- 为什么是“旋转”？ $U_C(\gamma) = \exp(-i \gamma H_C)$ 是一个酉算符。在量子力学中，酉算符描述了量子态随时间的演化，或者在抽象的希尔伯特空间中，它代表了对量子态的一种“旋转”。这里的“旋转”不是我们直观理解的几何旋转，而是指在量子态的复振幅空间中的一种相变。
参数 $\gamma$ 的作用：
- 优化目标： $\gamma$ 是 QAOA 的一个待优化的参数。它控制着问题哈密顿量 $H_C$ 作用的“强度”。
- “探索” vs. “利用”： 可以将 $\gamma$ 和 $\beta$ 理解为某种程度的“探索”和“利用”的平衡。
  - $\gamma$ (与 $H_C$ 相关): 更多地“利用”问题的结构信息，即根据目标函数来塑造态。
  - $\beta$ (与 $H_M$ 相关): 更多地“探索”可行的量子态空间，允许态在不同解之间切换。
- 改变相位： 改变 $\gamma$ 的值会改变量子态在 $H_C$ 本征态上获得的相位，从而影响后续 $U_M(\beta)$ 作用下的干涉效果。
- 寻找最优解： 通过扫描不同的 $\gamma$ 值（通常与 $\beta$ 一起进行优化），QAOA 算法试图找到一组参数 $(\gamma, \beta)$，使得最终测量的结果能以更高的概率给出优化问题的最优解或接近最优解。

总结：

$U_C(\gamma)$ 是 QAOA 中至关重要的组成部分，它通过 对量子态进行酉演化，使其在根据问题目标函数（$H_C$ 的本征值）划分的能量景观上获得相位标记，为后续通过 $H_M$ 的演化所产生的相干干涉效应奠定基础。参数 $\gamma$ 就像一个“旋钮”，控制着问题哈密顿量对量子态的影响程度，从而引导算法逐步逼近优化问题的最优解。

没有 $U_C(\gamma)$ 的作用，QAOA 就无法将经典优化问题的目标函数信息编码到量子态的相位中，也就无法利用量子干涉来增强目标解的出现概率。

$U_M(\beta)$ 的物理意义和作用¶

$H_M$ 的主要作用是作为一个 “混合器” (Mixer) 或 “行走算符” (Walker Operator)。它负责在量子态的所有可能状态（或问题的可行解）之间提供一个“连接”或“通道”。

我们可以从以下几个方面来理解 $U_M(\beta)$ 的物理意义和作用：

探索解空间，促进状态混合：
- $H_M$ 的选择： $H_M$ 的选择非常重要，它通常被选择为能够驱动量子比特在所有基本状态（或所有可能解）之间进行“行走”的哈密顿量。最常见的选择是 $H_M = \sum_i X_i$，其中 $X_i$ 是作用在第 $i$ 个量子比特上的泡利-$X$ 门。
- $U_M(\beta)$ 的作用： $U_M(\beta) = \exp(-i \beta \sum_i X_i)$ 作用在一个量子态上时，会通过泡利-$X$ 门（相当于量子比特的翻转）在不同的量子比特组合之间产生叠加。
- 物理意义： 这个算符的作用就像是在量子态空间中“行走”或“探索”。它允许量子态从一个可能的解“跳跃”到另一个可能的解。如果从 $p=0$ 层开始（此时态为均匀叠加态），$H_M$ 的作用确保了态具有在所有可能解之间进行搜索的能力。
为干涉机制提供平台：
- 相位传播与叠加： QAOA 的核心机制是通过交替作用 $U_C(\gamma)$ 和 $U_M(\beta)$ 来实现对量子态的塑造。$U_C(\gamma)$ 负责根据问题的目标函数（$H_C$ 的本征值）为量子态的不同成分“标记”相位。而 $U_M(\beta)$ 的作用就是将 $U_C(\gamma)$ 标记的相位信息“传播”到整个状态空间中。
- 相干干涉： 通过多次交替作用，对应于最优解（$H_C$ 的基态）的那些量子态分量，在恰当的 $\gamma$ 和 $\beta$ 值下，会获得一个能够导致相长干涉的相位模式。而其他非最优解的分量，则会因相干效应被抑制（发生相消干涉）。
- 为什么是“混合”？ $H_M$ 作为混合器，确保了 $H_C$ 施加的相位标记不会“固定”在某个局部区域，而是有机会与其他区域的相位进行干涉。如果 $H_M$ 不起作用，那么 $H_C$ 施加的相位变化可能只会影响态的相位，而不会改变不同本征态分量的概率振幅比例，也就无法实现干涉来增强特定解的出现概率。
参数 $\beta$ 的作用：
- “探索”的强度： $\beta$ 是 QAOA 的另一个待优化的参数，它控制着混合哈密顿量 $H_M$ 作用的“强度”或“深度”。
- 平衡“利用”与“探索”：
  - $\gamma$（与 $H_C$ 相关）侧重于“利用”问题的目标函数信息，将相位标记到有潜力的解上。
  - $\beta$（与 $H_M$ 相关）侧重于“探索”整个解空间，将这些标记了的相位进行混合与干涉。
- 找到最佳干涉： 通过调整 $\beta$，我们可以控制相位在整个量子态空间中是如何传播和“混合”的，从而找到最有利于最优解（基态）相长干涉的参数值。

为什么是“旋转”？

就像 $U_C(\gamma)$ 一样，$U_M(\beta) = \exp(-i \beta H_M)$ 也是一个酉算符。

在量子力学中，酉算符描述了量子态随时间的演化，或者在抽象的希尔伯特空间中，它代表了对量子态的一种“旋转”。
这里的“旋转”不是几何意义上的旋转，而是指在量子态的复振幅空间中的一种相变，它会改变量子态的各个基态分量的复振幅。
对于 $H_M = \sum_i X_i$，其本征态是与量子比特配置相关的。$U_M(\beta)$ 通过作用于这些本征态，改变它们的相位，从而实现状态的“混合”或“转换”。