XQuad Max-Cut 端到端示例深度解析：从 QUBO 建模到求解验证的完整流水线
XQuad Max-Cut 端到端示例深度解析：从 QUBO 建模到求解验证的完整流水线
本文以 XQuad 仓库中的 examples/maxcut 示例为线索，完整讲解如何用 xqcp 约束编程 DSL 将加权图最大割问题建模为 QUBO（二次无约束二值优化）模型，经 XQVM 编码器生成模型、xqsa 求解器采样、验证器独立校验、解码器还原二染色划分的六段式流水线。读完本文，你将掌握 Max-Cut 的 QUBO 数学形式、runner.py 中每个 DSL 调用对应的底层指令行为、命令行参数的完整含义，以及如何把该示例改造成带固定终点的最小 s-t 割变体。
问题定义与 QUBO 建模
Max-Cut 的目标是：给定一个带权图，把所有节点染成两种颜色（即二划分，2-colour partition），使得横跨两个染色集合的边的总权重最大。每个节点只能选择一侧（0 或 1），这是一个典型的二值组合优化问题。
在 XQuad 中，求解器只能最小化一个数字（模型的能量），因此必须把"最大化割权重"改写为"最小化某个二次函数"。示例采用如下形式：
- 输入：
num_nodes（int），edges（Vec，扁平化的(i, j, w)三元组，共3*|E|个条目，即每一条边依次存放起点、终点、权重三个整数）； - 模型：
n个二值变量，每个节点一个，x[v] ∈ {0, 1}表示节点v被分到哪一侧； - 目标：对每条边
(i, j, w)，累加线性项-w*(x_i + x_j)与二次项+2w*x_i*x_j。
为什么这样写？对单条边而言，其贡献为：
H_edge = -w·x_i - w·x_j + 2w·x_i·x_j = -w·(x_i + x_j - 2·x_i·x_j)
其中 x_i + x_j - 2·x_i·x_j 正是二值变量的 XOR：当 x_i ≠ x_j（边跨越划分）时等于 1，当两者相等时等于 0。于是该边在跨越划分时贡献 -w，否则贡献 0。对所有边求和后，整个哈密顿量 H 恰好是割权重的相反数——最小化 H 即最大化割权重。这正是仓库中二次模型工作示例的推导结论，examples/maxcut/runner.py 构建的正是这个模型。
注意：最大化问题改写为最小化时，所有系数符号取反，因此文档和输出中
energy通常为负值，其绝对值即为割权重。在--n 5 --seed 42的默认示例中，输出energy: -354与cut_weight: 354严格互为相反数。
DSL 方法：runner.py 的核心建模代码
examples/maxcut/runner.py 的 build_problem() 是建模的核心，它只用八个 DSL 方法就完成了整个问题定义。以下是其逐段拆解（对应源码）：
problem = Problem("MaxCut")
num_nodes = problem.input("num_nodes", type=Types.Int)
edges_in = problem.input("edges", type=Types.Vec)
problem.define_model(size=num_nodes, domain=Domain.BINARY)
edge_count = problem.stow("edge_count", edges_in.veclen() // 3)
with problem.range(0, edge_count) as e:
offset = e * 3
i = problem.stow("i", edges_in.get(offset))
j = problem.stow("j", edges_in.get(offset + 1))
w = problem.stow("w", edges_in.get(offset + 2))
problem.model.linear[i].add(-w)
problem.model.linear[j].add(-w)
problem.model.quadratic[i, j].add(w * 2)
partition = problem.output("partition", type=Types.Vec)
with problem.range(0, num_nodes) as node:
partition.append(problem.sample.getline(node))
各 DSL 方法的作用如下（与文档中 [DSL methods used] 一节逐条对应）：
| DSL 调用 | 作用 | 底层对应 |
|---|---|---|
problem.input(name, type) |
声明类型化的 calldata 输入，返回符号化的 InputRef |
编码器输出 INPUT rN 指令，按调用顺序分配寄存器（r0、r1…），且必须在 define_model() 之前调用 |
problem.define_model(size, domain) |
分配二值 XQMX 模型（size 个变量） |
编码器输出 BQMX 指令；Domain.BINARY 对应 {0,1} 域（此外还有 SPIN 的 SQMX 与 Integer 的 XQMX，见三域说明） |
problem.stow(name, expr) |
把中间计算结果绑定到命名寄存器 | 编译为 STOW rN，供后续指令复用 |
problem.range(start, end) |
发出 RANGE 循环，e 是循环变量 LoopVar |
编译为 RANGE ... NEXT 块；edge_count 循环遍历每一条边，node 循环遍历每个节点 |
model.linear[i].add(w) |
在变量 i 上累加线性偏置 |
编译为 ADDLINE 指令 |
model.quadratic[i, j].add(w) |
累加变量 i、j 之间的二次耦合 |
编译为 ADDQUAD 指令（对角元 quadratic[i,i] 在二值域等价于线性项，因为 x² = x） |
problem.output(name, type) |
声明类型化输出槽 | 解码器为每个输出分配一个槽位，编译为 PUSH {slot} / OUTPUT rN |
problem.sample.getline(node) |
从样本位串中读取一行（即节点 node 的取值） |
编译为 GETLINE 指令；在解码器中把样本位串还原为划分向量 |
值得注意的细节：
- 扁平化输入：
edges不是嵌套结构，而是3*|E|个整数的扁平 Vec；edge_count = edges_in.veclen() // 3用veclen()计算边数，每条边的三个字段通过edges_in.get(offset + k)读取。 - 寄存器分配是全局递增的：从 xqcp 的寄存器分配器实现 可以看到，
_RegisterAllocator是一个简单的递增计数器（起始 0，超过r255会在编译期抛出RuntimeError）。输入的num_nodes、edges先占用r0、r1，之后每个stow()、循环变量、vec()与输出寄存器按调用顺序依次认领。这也解释了为什么编码器输出中的寄存器编号与runner.py的调用顺序一一对应。 problem.model与problem.sample是隐式引用：define_model()调用后可通过属性访问模型（源码），未定义模型就访问会抛出RuntimeError("No model defined — call define_model() first")。
六段式流水线：三程序架构与求解器
Max-Cut 的端到端流程分为六步，其中编码器、验证器、解码器是三个相互独立的 XQVM 程序，仅通过 calldata 输入与输出槽通信（三程序架构的完整说明见文档）：
1. CP (xqcp) —— 构建随机加权完全图，声明每个节点一个二值变量，按边累加 QUBO 线性/二次项
2. Assemble —— problem.compile() 在内存中生成三段 .xqasm 文本（encoder/verifier/decoder），
经 xquad.asm 汇编为字节码
3. Encode —— 在所选 XQVM（python 或 rust）上运行编码器，产出 XQMX 模型
4. Sample —— 求解器（SA/QPU/GPU）对模型采样
5. Verify —— 验证器检查样本均为二值，并独立重算能量；本问题未声明约束，故只做域检查
6. Decode —— 解码器从样本位串还原二染色划分
注意：problem.compile() 返回的 CompiledPrograms(encoder, verifier, decoder) 是三段独立的 .xqasm 字符串，编译过程不产生共享的中间表示（编译文档）。三个程序的 calldata 与输出槽契约是固定的：
| 程序 | Calldata（按序） | 输出 |
|---|---|---|
| 编码器 | 每个 problem.input() 一项，按调用顺序 |
槽 0：模型 |
| 验证器 | 每个 problem.input() 一项，再加模型、样本 |
槽 0：energy；槽 1：valid |
| 解码器 | 样本、N |
每个 problem.output() 一个槽，按声明顺序 |
runner.py 的 run() 函数（源码）正是按此契约驱动：
vm = VM(backend=backend)
vm.set_calldata([n, flat]) # 编码器输入
vm.set_output_slots(1)
vm.run(programs.encoder)
model = vm.outputs()[0] # XQMX 模型
solver = build_solver(solver_name, seed=seed)
sample = solver.solve(model).sample # 求解发生在 VM 之外
vm = VM(backend=backend)
vm.set_calldata([n, flat, model, sample]) # 验证器输入
vm.set_output_slots(2)
vm.run(programs.verifier)
energy, valid = vm.outputs()
vm = VM(backend=backend)
vm.set_calldata([sample, n]) # 解码器输入
vm.set_output_slots(1)
vm.run(programs.decoder)
这里体现了三程序架构的核心设计：XQVM 的指令集（93 条）没有任何"调用求解器"的指令——求解发生在宿主代码中、两次 VM 运行之间（三程序文档）。xquad.vm.VM 是统一的解释器接口（源码），通过 VMBackend.RUST / VMBackend.PYTHON 在 Rust FFI 运行时与纯 Python 参考实现之间切换，set_calldata()、set_output_slots()、run()、outputs() 是四个关键方法。--interpreter 参数选择的正是这个执行轴，与 --solver 选择的求解轴完全正交：一个正确的模型在两种解释器上总是产生相同的 valid 与 energy。
由于 Max-Cut 不声明任何约束，验证器中的域检查循环（; === Validity checks ===）只确认每个样本值属于 {0, 1}，而 ENERGY 重算是真实发生的：验证器从模型与样本出发、用与求解器无关的精确整数算术重新计算能量，而非直接采信求解器上报的数值（三程序文档中的具体运行）。
运行示例：命令行参数速查
在仓库根目录下执行（uv 是项目采用的 Python 包管理工具，仓库的 uv.lock 已锁定依赖）：
uv run python examples/maxcut/runner.py --seed 42
uv run python examples/maxcut/runner.py --n 6 --seed 7 -o /tmp/mc.json
第一条命令以默认参数运行并把 JSON 结果打印到 stdout；第二条改为 6 个节点、随机种子 7，并把结果写入 /tmp/mc.json。完整参数如下（对应文档 [Usage] 表格）：
| Flag | 默认值 | 说明 |
|---|---|---|
--n |
5 |
完全图的节点数 |
--solver |
dwave-cpu |
求解后端（见下节"选择求解器"） |
--interpreter |
python |
XQVM 后端：python 或 rust |
--seed |
42 |
随机种子（同时决定边权重生成与求解器随机性） |
-o / --output |
stdout | 把 JSON 结果写入文件，缺省打印到标准输出 |
--n 只改变问题规模，不改变编译产物：编码器的寄存器编号与指令数量取决于 Python 代码中 input()、stow()、define_model() 等调用的次数，而非 --n 的值（编译文档）。边权重在 <a href="https://link.gitcode.com/i/243908fb1189703bf16edb432e269e16" target="_blank">1, 100] 区间内均匀随机生成（[runner.py 第 58 行）。
一个典型输出（--n 5 --seed 42）：
{
"_seed": 42,
"_note": "canonical CI golden",
"n": 5,
"partition": [0, 1, 0, 0, 1],
"cut_weight": 354,
"energy": -354,
"valid": 1
}
字段说明：_seed 与 _note 是 runner 自己的簿记信息（_note 的值描述该次调用，而非测试固化的承诺）；partition 是解码出的 0/1 划分；cut_weight 由宿主代码用 partition<a href="https://link.gitcode.com/i/376e5a7c023583895d1c54bfe1416773" target="_blank">i] != partition[j] 重新累加计算（[runner.py 第 84-86 行）；energy 是验证器独立重算的哈密顿量，本问题中恒为 -cut_weight；valid: 1 仅表示所有样本值都在 {0, 1} 内——这是本问题验证器的全部检查内容。
选择求解器：五种后端与安装方式
求解器选择与安装 extras 对所有示例完全一致，完整说明见示例使用指南与求解总览。--solver 的合法取值由 xqsa.SOLVERS 注册表决定（registry 源码），共五种：
| 名称 | 硬件 | 安装方式 |
|---|---|---|
dwave-cpu |
CPU（默认，本地模拟退火） | pip install xqsa（基础包即含） |
dwave-qpu |
D-Wave Leap 云账户（真实量子退火硬件） | pip install xqsa[dwave] |
cuda-gpu |
NVIDIA CUDA GPU（自定义模拟退火内核） | pip install xqsa[cuda]，需 CUDA 12.x 驱动 |
metal-gpu |
Apple Silicon（macOS）Metal GPU | pip install xqsa[metal] |
quip |
Quip 网络（远程矿工，环境变量配置） | pip install xqsa[quip] |
其中 dwave-cpu 是 xqsa.DEFAULT_SOLVER（registry 源码第 55 行），也是 CI 冒烟测试使用的唯一求解器。它封装 dwave-samplers 的 SimulatedAnnealingSampler，无需任何凭据即可在任何机器上运行。build_solver(name, seed=...) 是后端无关的构造入口，seed 只对三个经典模拟退火后端（dwave-cpu、cuda-gpu、metal-gpu）生效；dwave-qpu（物理硬件无种子）与 quip（矿工自身随机性不受调用方控制）会忽略它（求解总览）。
dwave-cpu 的关键构造参数（均可在 solve(**kwargs) 时按次覆盖）：num_reads=100（独立退火次数，取最优）、num_sweeps=1000（每次退火的扫描数）、num_sweeps_per_beta=1（每个温度层级停留的扫描数）、beta_range=None（逆温区间，None 交给 dwave-samplers 自动选择）、seed=None（None 表示非确定性）。GPU 后端在此基础上还有 strategy（metal-gpu 支持 "sa" 或 "gibbs"）与 beta_schedule_type 等参数，详见本地求解器文档。
重要：非默认求解器无法复现规范输出（不同求解器使用不同 RNG/硬件，模型可能有多个能量相同的等价最优解）。
example-smoke始终使用dwave-cpu进行校验。另外注意当前所有xqsa求解器都只接受 binary 与 spin 域，integer 域模型会被拒绝（ValueError: Unsupported domain for solving: INTEGER），因此示例统一使用Domain.BINARY。
规范输出与冒烟测试：不变式校验而非逐字节比对
example-smoke 是示例的 CI 守护者，其目标不是逐字节对比两个解释器的输出，而是验证不变式：两个解释器都以 --seed 42 --solver dwave-cpu 跑出 valid == 1（脚本源码）。
为什么不做精确输出比对？模拟退火对 BQM 的构建顺序敏感，Python 与 Rust 两条路径可能找到不同但同样有效的最优解。文档明确说明（三程序文档）：编码器、验证器、解码器在每个解释器内部是确定性的（相同字节码进、相同输出出），但夹在中间的求解器只锚定种子与 dwave-samplers 版本——同一库的不同版本可能对同一种子返回不同的有效样本。
在仓库中执行冒烟测试：
uv run --no-sync python scripts/example-smoke.py
脚本会遍历 examples/*/runner.py，对每个示例在 python 与 rust 两种解释器下各跑一遍，检查 valid == 1，随后对 manifest 中标记 hardware: true 的示例子集（Max-Cut、TSP、Knapsack 三个，用于控制 GPU 时间与 D-Wave QPU 月度配额，见 examples/manifest.yaml）在可用硬件求解器上复跑。值得注意的是，脚本会先强制要求 xqffi.verifier.verify_source 可导入（脚本第 46-71 行）：xqcp 在库模式下对验证器缺失会静默跳过，但冒烟测试必须保证每个编译出的示例程序都真正经过了字节码验证器的检查。
动手改造：把 Max-Cut 变成带固定终端的最小 s-t 割
把现有 runner.py 复制一份并修改，是建模新问题最快的方式。文档以最小 s-t 割为例：假设两个指定节点（如节点 0 与节点 n-1）必须位于划分的两侧。这是两个小改动（完整过程见示例使用指南）：
with problem.range(0, edge_count) as e:
offset = e * 3
i = problem.stow("i", edges_in.get(offset))
j = problem.stow("j", edges_in.get(offset + 1))
w = problem.stow("w", edges_in.get(offset + 2))
problem.model.linear[i].add(w) # 符号翻转：最小化而非最大化
problem.model.linear[j].add(w)
problem.model.quadratic[i, j].add(w * -2)
# 把节点 0 钉在 0 侧、节点 n-1 钉在 1 侧。10_000 远大于所有边权重之和
#（该图最多 C(n,2) * 100），因此任何一侧都不会为了省权重而翻转固定节点。
problem.model.linear[0].add(10_000)
problem.model.linear[num_nodes - 1].add(-10_000)
其余全部保留：随机加权图、define_model、partition 输出循环与 run()。注意 main() 必须删掉 canonicalize_partition(partition) 调用——该函数把节点 0 规范化为 0 侧，是因为 Max-Cut 中一个割与其补割（所有节点翻转）是同一个割；而 s-t 割变体的两个端点使两侧不再等价，规范化会抹掉钉住端点这一新增事实。
同一图（--n 5 --seed 42）上原版与变体的结果对比（来自示例使用指南）：
// 原版 maxcut：最大化割权重
{"cut_weight": 354, "energy": -354, "partition": [0, 1, 0, 0, 1], "valid": 1}
// s-t 割变体：最小化跨越权重且端点固定
{"cut_weight": 196, "energy": -9804, "partition": [0, 1, 1, 1, 1], "valid": 1}
这个对比同时是调试方法论的一课：对于无约束问题，仅凭 valid 无法发现建模错误（它只确认样本是二值）；energy 也不是安全指标——把两个端点的偏置符号写反（linear[0] += -10_000、linear[n-1] += +10_000），跑出来的 cut_weight（196）与 energy（-9804）与正确版本完全相同，因为一个割与其补割永远代价相同，反转钉住端点只是选中了这对补割的另一半。此时唯一的暴露点是 partition[0] 与 partition[-1]：正确版本为 0 和 1，写反版本为 1 和 0。这给出了一条可迁移的验证习惯：用编辑本应保证的具体属性去检查未经任何下游步骤规范化的输出，而不是只盯 valid 与看起来合理的 energy。
小结
examples/maxcut 是 XQuad 工具链的浓缩展示：一个 runner.py 文件贯穿了 xqcp（建模编译）、xqasm（汇编）、XQVM（编码/验证/解码三段程序）、xqsa（求解）与宿主编排的全部层级，没有预写好的 .xqasm 文件、没有 JSON 输入——CP 进，解码后的划分出。其 QUBO 形式（线性 -w、二次 +2w）是一个可以原样迁移到任意带权二划分问题的模板，而"验证器独立重算能量、冒烟测试校验不变式而非精确输出、通过补割对称性识别建模错误"这三条实践，对仓库中其余十三个示例（图着色、背包、TSP、最大独立集等，见示例画廊）同样适用。