4. MaxCut的哈密顿量建模

要理解量子算法如何求解 MaxCut，核心一步是把“图上怎么切”这个组合优化问题，翻译成量子硬件能够操作的能量函数。这一步的产物就是伊辛哈密顿量（Ising Hamiltonian）。本节围绕三个问题展开：割目标如何写成求和式、自旋变量如何与图的顶点一一对应、以及最终得到的哈密顿量中每一项到底代表什么。

一、先固定约定：自旋与割的对应关系

给定无向图 G=(V,E)，每个顶点 i 分配一个自旋变量。我们采用计算中最常用的约定：自旋取值为 s_i ∈ {+1, −1}，其中 s_i=+1 表示顶点 i 被划入集合 A，s_i=−1 表示划入集合 B。一条边 (i,j) 被“割断”，当且仅当两个端点落在不同集合，即 s_i ≠ s_j，等价于乘积 s_is_j = −1。反之，若两端同侧，则 s_is_j = +1。

这个约定非常关键：它把“是否被割”这一离散判断，变成了一个只取 ±1 的乘积量。于是“割断的边数”就可以用乘积的求和来表达。需要强调的是，正负号约定必须在全文和图示中保持一致；若改用 s_i ∈ {0,1}，则表达式形式会变化，容易在实现时引入符号错误。

二、割目标函数的构造

对每条边 (i,j)，定义指示量 (1 − s_is_j)/2：当两端异侧时它等于 1，同侧时等于 0。把所有边加起来，就得到割大小的表达式：

C(s) = Σ_(i,j)∈E (1 − s_i·s_j) / 2
     = |E|/2 − (1/2)·Σ_(i,j)∈E s_i·s_j

MaxCut 的目标是最大化 C(s)。由于 |E|/2 是常数，最大化 C(s) 等价于最小化 Σ s_is_j。这正是伊辛模型的标准形式：能量越低，割越大。因此我们定义哈密顿量

H_C = Σ_(i,j)∈E s_i·s_j   （等价地写作 Σ J_ij·Z_i·Z_j，J_ij = 1）

其中 Z_i 是作用在第 i 个量子比特上的泡利 Z 算符，其本征值为 +1 和 −1，恰好对应两个自旋方向。这样，一个图割问题就被完整地编码进了一个对角哈密顿量：它的每一个本征态对应一种割方案，本征值对应这种方案的“负割大小”（差一个常数）。

三、用一个具体小图走一遍

取一个 4 顶点、4 条边的环图 C₄，顶点 0–1–2–3–0 依次相连。边集为 {(0,1),(1,2),(2,3),(3,0)}，|E|=4。哈密顿量为：

H_C = Z0Z1 + Z1Z2 + Z2Z3 + Z3Z0

考虑割方案 s=(+1,−1,+1,−1)，即顶点 0、2 在 A，1、3 在 B。逐边计算乘积：Z0Z1=−1，Z1Z2=−1，Z2Z3=−1，Z3Z0=−1，求和得 H_C=−4。代入割公式 C = 4/2 − (−4)/2 = 2 + 2 = 4，四条边全部被割断，这是 C₄ 的最优解。

再考虑 s=(+1,+1,−1,−1)：Z0Z1=+1，Z1Z2=−1，Z2Z3=+1，Z3Z0=−1，求和得 H_C=0，对应 C = 2 − 0 = 2，只割断两条边。可见能量从 0 降到 −4，割从 2 升到 4，能量与割大小呈严格的负相关。这个例子也说明：哈密顿量的每一项只涉及一条边的两个端点，图的结构直接决定了算符之间的耦合关系。

四、从伊辛模型到量子哈密顿量

上面的 H_C 是经典伊辛能量，写成算符形式后它就是一个对角量子哈密顿量。但量子算法（如 QAOA）并不直接对 H_C 做演化，而是引入一个混合哈密顿量 H_B = Σ X_i，其中 X_i 是泡利 X 算符。H_B 负责在解空间中进行翻转（单比特翻转），H_C 负责施加问题结构的相位。两者交替演化，就构成了 QAOA 的核心线路。

这里有一个容易混淆的点：H_C 中的 Z_iZ_j 项是对角的，它只改变相位、不改变计算基下的比特值；而 H_B 中的 X_i 是非对角的，它才会真正翻转比特。理解这一分工，是理解后续 QAOA 线路设计的前提。

五、建模时的几个实操要点

• 边权处理：若图带权 w_ij，则 H_C = Σ w_ijZ_iZ_j，割目标相应变为 Σ w_ij(1−s_is_j)/2。权重直接进入耦合系数 J_ij。
• 常数项：|E|/2 或 Σw_ij/2 是能量平移，不影响最优解，但在比较不同规模图的能量值时必须保留，否则读数会系统性偏移。
• 比特编号：顶点编号必须与量子比特索引严格一致，边表 (i,j) 决定了两两耦合的连线，编号错位会导致哈密顿量对应错误的图。
• 符号自检：用全 +1 态（所有顶点同侧）验证，此时 H_C 应等于 +|E|（无权情形），割为 0；若符号相反，说明约定写反了。