3. 量子计算基础速览

要理解量子算法为什么可能比经典算法更快地求解 MaxCut，必须先弄清量子计算的基本“零件”和“规则”。本节不追求量子力学的完整形式体系，而是围绕组合优化真正会用到的几个概念展开：量子比特如何表示状态、叠加如何让多个候选解同时参与运算、纠缠如何建立变量之间的关联、测量如何把量子态变成可读的经典结果，以及量子门如何一步步塑造量子态。理解这五件事，就足以读懂后续 QAOA 等算法的结构。

量子比特：从确定位到概率幅

经典比特只能取 0 或 1。量子比特（qubit）的状态则写成两个基态的线性组合：

|ψ⟩ = α|0⟩ + β|1⟩，其中 α、β 为复数，且 |α|² + |β|² = 1

这里 α、β 称为概率幅，不是概率本身。|α|² 和 |β|² 分别是测量得到 0 和 1 的概率。概率幅可以带相位，而相位在后续门操作和干涉中会起作用——这正是量子算法能放大“好解”、抑制“坏解”的关键资源。对 MaxCut 而言，一个 n 个顶点的图需要 n 个量子比特，每个比特对应一条边的一个端点是否被划入某个割集合，例如约定 |0⟩ 表示顶点在集合 S 中、|1⟩ 表示在补集中。

叠加：让多个候选割同时存在

叠加是把单个比特的“0 或 1”扩展为“0 和 1 的加权共存”。对 n 个比特全部施加 Hadamard 门，可得到均匀叠加态：

H⊗n |0…0⟩ = (1/√2ⁿ) Σₓ |x⟩，x 遍历所有 2ⁿ 个比特串

对 MaxCut 来说，这意味着 2ⁿ 种顶点划分方式被同时编码进一个量子态。需要强调的是，叠加不等于“并行算出所有答案并直接读出”。测量一次只能得到一个比特串，量子算法的优势来自后续的门操作让不同候选解的振幅发生干涉：好割对应的振幅被增强，差割对应的振幅被削弱。因此叠加是起点，不是终点。

纠缠：变量之间的量子关联

纠缠描述的是多比特之间无法分解为各自独立状态的关联。以两比特的 Bell 态为例：

|Φ⁺⟩ = (|00⟩ + |11⟩)/√2

测量第一个比特若得 0，第二个必为 0；若得 1，第二个必为 1。这种关联超越经典相关性。在 MaxCut 中，纠缠让不同顶点的划分决策不再彼此独立，从而能够表达“相邻顶点倾向于分属不同集合”这类整体约束。QAOA 中的纠缠层正是通过受控旋转门把边两端的比特耦合起来，使割的代价信息进入量子态的相位与振幅结构。

测量：量子态到经典结果的桥梁

测量是量子计算中不可回避的一步。在计算基下测量一个比特，状态会以 |α|²、|β|² 的概率坍缩到 |0⟩ 或 |1⟩，且测量后原叠加态被破坏。对 MaxCut 的求解流程，通常需要多次运行“制备态—测量”并统计比特串分布，用采样频率估计各割出现的概率。由于单次测量只给出一个候选割，实际中要设置足够的采样次数（shots），例如数百到数千次，才能较稳定地估计期望割值。测量结果是一串经典比特，需要再按约定映射回顶点划分，并计算该割的边数。

量子门：塑造量子态的基本操作

量子门是对量子比特的酉变换，可理解为可逆的、保概率的“逻辑操作”。与组合优化关系最密切的几类门如下：

• 单比特旋转门 Rx(θ)、Ry(θ)、Rz(θ)：绕相应轴旋转，θ 是连续参数。QAOA 的代价层与混合层就由带参数的旋转构成，参数优化是算法外层的经典任务。
• Hadamard 门 H：把 |0⟩ 变为 (|0⟩+|1⟩)/√2，是制备均匀叠加的核心。
• 受控旋转门（如受控 Rz）：以一个比特为控制、另一个为目标，用于把边两端比特关联起来，是构造纠缠和编码割代价的常用手段。
• CNOT 门：控制比特为 1 时翻转目标比特，常与 H 门组合制备 Bell 态。

需要注意，量子门必须可逆（除测量外），因此经典计算中常见的“与、或、赋值”不能直接照搬，需要转成可逆形式或借助辅助比特。这也是把 MaxCut 的目标函数编码成量子线路时的主要设计工作之一。

把五个概念串成一条可执行链路

上图把本节概念组织成一条与 MaxCut 直接对应的处理链。以一个小例子说明：设图有 4 个顶点、边集为 {(1,2),(2,3),(3,4),(4,1)}，即一个四环。用 4 个量子比特表示 4 个顶点的划分，约定 |0⟩ 表示顶点在集合 S、|1⟩ 表示在补集。初始态 |0000⟩ 经 H⊗4 变为 16 个比特串的均匀叠加，每个候选割概率相同。随后按边逐条施加受控旋转门，把“两端同侧则割值小、异侧则割值大”的代价信息写入相位；再施加混合层让振幅重新分配。重复若干层后测量，得到形如 0101 或 1010 的比特串频率升高——这两个串恰好对应把四环交替划分、4 条边全部跨割的最优解，割值为 4。而 0000、1111 这类全同侧划分割值为 0，其出现频率会被压低。

这个例子揭示了几个实践要点。第一，比特到顶点的映射和 0/1 到集合的约定必须在全流程中保持一致，否则后处理会把最优解误判为最差解。第二，测量得到的只是样本，需要统计而非单次判定；若采样次数太少，可能一次都没抽到最优串。第三，量子门中的旋转角度 θ 不是凭感觉设定，而是由外层经典优化器根据多次采样估计的期望割值反复调整，形成“量子采样—经典评估—参数更新”的闭环。第四，纠缠层的作用是让边约束真正影响联合分布，若省略纠缠、只做单比特旋转，各比特近似独立，很难表达割的结构。

还需澄清一个常见误解：量子比特的叠加并不等于“同时尝试所有解并自动挑出最好的”。真正起作用的是振幅与相位在门操作下的干涉，以及测量采样对分布的估计。对 MaxCut 这类问题，量子部分负责生成带有问题结构的概率分布，经典部分负责评估样本和调参，二者缺一不可。把这条分工记清楚，后续学习 QAOA 的层结构、参数初始化与采样策略时就不会迷失方向。