XQuad 第一个问题实战：从 Max-Cut 定义到真实求解答案的完整流水线

本篇技术指南以 XQuad 入门教程的「First Problem」为核心，完整讲解如何用一条命令把 Max-Cut（最大割）问题从问题定义一路跑通到真实求解答案：编码（encode）→ 采样（solve）→ 校验（verify）→ 解码（decode）。读者完成后将掌握 XQuad 示例运行器的全部命令行参数、输出 JSON 的每个字段含义、Python 与 Rust 两套 XQVM 解释器的选择与结果一致性边界，并能在源码层面理解 examples/maxcut/runner.py 背后的三程序流水线。

准备：安装 XQuad 并准备好可运行的示例

运行本文所有命令前，需要先完成两件事：安装 XQuad 工具链，以及拿到包含示例代码的仓库 checkout。因为示例运行器并不随已发布包分发，只存在于源码仓库中。

安装 XQuad

按 Install XQuad 的说明，两个生态各装一次：

cargo install xqcli      # 提供 `xquad` 命令行二进制
pip install xquad        # Python 伞包：完整流水线

装完后验证两半都可用：

$ xquad --version        # 确认 xqcli 二进制在 PATH 上
$ python -c "import xquad; print('ok')"
ok

其中 import xquad 会真正加载编译好的 xqffi 扩展（xquad/init.py 顶层即导入 asm、program、verifier、vm 四个子模块），因此打印 ok 本身就说明 FFI 层就绪。

获取示例仓库并初始化 Python 工作区

书籍中所有 uv run python examples/... 命令都运行在本仓库的 checkout 上：

git clone https://gitlab.com/quip.network/xquad.git
cd xquad
make deps-py

make deps-py 依赖 uv 和 Rust 工具链。它通过 uv sync 同步 Python 工作区（xqvm_py、xqcp、xqsa、xqffi），再用 maturin develop 重新编译 xqffi 的 cdylib，并利用各包 pyproject.toml 的 dev-mode-dirs = [".."] 把仓库根目录放进 sys.path，使仓库根下的 uv run python examples/<name>/runner.py 能直接 import xqcp 等包。这一步只需要做一次，之后所有示例命令即可从仓库根目录运行。

Max-Cut 问题：一个自带 QUBO 推导的入门样例

Max-Cut 的目标是把一张图的节点分成两组，使跨越两组之间的边权总和最大化。Quadratic Models 在三个节点的图上手推了它的二次模型公式；examples/maxcut/ 则是同一个问题、可运行、图规模由你指定的版本。

设 x_i ∈ {0, 1} 表示节点 i 落在割的哪一侧，对每条有权边 (i, j, w)：

linear[i] += -w,   linear[j] += -w,   quadratic[i,j] += 2w

该边对能量函数 H 的贡献是 -w(x_i + x_j - 2x_i·x_j)，而 x_i + x_j - 2x_i·x_j 正是 x_i 与 x_j 的二进制 XOR：当且仅当两个节点分居两侧时为 1。于是每条边恰好在跨越割时贡献 -w，求和后 H 就是割权的相反数——最小化 H 即最大化割，这正是 examples/maxcut/README.md 中 QUBO formulation 一节的结论。

从源码看，runner.py 的 build_problem 用 xqcp DSL 把这段公式逐边累加进模型（examples/maxcut/runner.py）：

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)

这里输入是一张随机加权完全图：num_nodes（int）与 edges（Vec，展平的 (i, j, w) 三元组，共 3*|E| 个整数）；模型为 n 个二进制变量（Domain.BINARY，x[v] ∈ {0, 1}），每个变量对应一个节点。

第一次运行：一条命令跑通从问题到答案的全程

假设 XQuad 已安装、示例已就绪，运行：

$ uv run python examples/maxcut/runner.py --seed 42
{
  "_note": "canonical CI golden",
  "_seed": 42,
  "cut_weight": 354,
  "energy": -354,
  "n": 5,
  "partition": [
    0,
    1,
    0,
    0,
    1
  ],
  "valid": 1
}

除 --seed 外不需要任何 flag：--n 默认为 5，--solver 默认为 dwave-cpu——这是无需任何硬件或凭据的基线求解器。

全部命令行参数

runner.py 的 argparse CLI（examples/maxcut/runner.py）完整定义了以下参数：

Flag	默认值	说明
--n	5	完全图的节点数
--seed	42	随机种子，决定图结构与求解随机性
--solver	dwave-cpu	求解后端，可选值见下文求解器表
--interpreter	python	XQVM 解释器：python（纯 Python 参考 VM）或 rust（Rust 解释器）
-o / --output	stdout	把解码结果以 JSON 写入指定路径，否则输出到标准输出

其中 --interpreter 与 --solver 是两条相互独立的轴：前者选择执行编译后程序的虚拟机，后者选择采样模型的求解器（Using the Examples）。

输出 JSON 的结构

输出是一个 sort_keys=True 的缩进 JSON，各字段含义如下：

字段	示例值	含义
_note	"canonical CI golden"	运行器自带的簿记标记，描述本次调用的用途，并非测试断言
_seed	42	本次运行使用的种子
n	5	节点数
partition	[0, 1, 0, 0, 1]	答案本体：每个节点一个 0 或 1，指明该节点落在割的哪一侧
cut_weight	354	连接 0 侧节点与 1 侧节点的边权总和，即 Max-Cut 最大化的量
energy	-354	模型能量，等于 cut_weight 的相反数
valid	1	校验标志：1 表示通过校验

读懂结果：四个字段背后的机制

partition 与 cut_weight

partition 就是问题的答案：5 个节点，每个位置的值 0 或 1 代表该节点所属的割侧。cut_weight 则由 runner.py 中的 cut_weight() 函数独立重算（examples/maxcut/runner.py）：

def cut_weight(partition: list[int], edges: list[tuple[int, int, int]]) -> int:
    return sum(w for i, j, w in edges if partition[i] != partition[j])

即只累加跨越割的边权。注意输出前 partition 还经过 canonicalize_partition() 归一化：Max-Cut 对全局翻转不变（把每个节点的侧别取反得到同一个割），因此统一把节点 0 归一化到侧 0，使输出在不同解释器之间稳定（examples/maxcut/runner.py）。

energy 为什么是负的

energy = -354 是 cut_weight 的相反数，原因是模型最小化的是「-1 倍割权」：为把最大化问题转成 XQuad 每个模型都在做的最小化，编码器对每条跨越割的边计入 -w 的贡献。这个符号翻转是精确的、非近似的，其推导见 Quadratic Models。更重要的一点：energy 不是从求解器那里转述过来的。校验器程序在收到模型与样本后，用 XQVM 的 ENERGY 指令按同一公式独立重算能量，因此你永远不必相信后端自报的能耗（Backends）。

valid: 1 的边界

valid: 1 确认 partition 中每个值都是 0 或 1——这是该问题校验器检查的唯一内容，因为 Max-Cut 除了「取值合法」之外没有声明任何约束。它的 verifier 中 ; === Validity checks === 之下的循环只逐值确认样本落在 {0, 1} 内（Three Programs）。这一点在把示例改造成新问题时尤其重要：valid 只覆盖校验器实际检查的属性，并不自动覆盖你新增的业务约束（Using the Examples）。

同一个答案，换一台「机器」：--interpreter rust

$ uv run python examples/maxcut/runner.py --seed 42 --interpreter rust

--interpreter 选择由哪套 XQVM 运行编译后的程序：默认的纯 Python 参考 VM（xqvm_py），或经 xqffi FFI 调用的 Rust 解释器（xqvm）。xquad/vm.py 中的 VM 类以 VMBackend 枚举在这两者之间分发：RUST 路径先把 .xqasm 源码汇编成字节码再交给 Rust VM，PYTHON 路径直接以源码运行 Python 执行器（xquad/vm.py）；边界处的模型、样本统一转换成 xquad/types.py 中的规范 XQMX 类型。

确定性边界：什么保证一致，什么不保证

关键在于：encoder、verifier、decoder 三个程序在每个解释器内部都是确定性的——相同的字节码进、相同的输出出，两套解释器都成立。夹在它们中间的求解过程只被 seed 和 dwave-samplers 的版本锁定：solver.solve(model) 运行的是模拟退火，因此换了该库的版本，同一 seed 可能返回不同的合法样本。

对本 seed（42）而言，求解恰好落在两边一致的样本上，所以上面 cut_weight、energy、partition 在两种解释器下也完全一致。但这不是保证：如果模型存在多个能量相等的并列最优解，求解器返回其中某一个，不同解释器路径可能各取其一，解码出不同的合法答案（Using the Examples 中 graph_coloring 在默认 seed 下就出现了 python 与 rust 结果不同的情形）。Three Programs 对同一 seed、同一规模在两种解释器上并排运行，详细说明哪些匹配是保证的、哪些不是。

仓库的 CI 冒烟测试同样遵守这条边界：make example-smoke（Makefile 中 example-smoke 目标）调用 scripts/example-smoke.py，对每个示例在两种解释器上以 --seed 42 --solver dwave-cpu 各跑一遍，只断言 valid == 1，不做 cut_weight/energy/partition 的逐字节比对——模拟退火对 BQM 构造顺序敏感，两条路径可能落在不同但同样合法的优化解上（examples/maxcut/README.md）。

深入流水线：runner.py 内部的四步调用

理解了输出，再看这条命令到底执行了什么。runner.py 的 run() 函数按 Three Programs 的形态做了四次顺序调用，其中三次穿过 VM（examples/maxcut/runner.py）：

1. vm.run(programs.encoder)，calldata 为 [n, flat_edges]，开 1 个输出槽，产出一个 XQMX 模型；
2. solver.solve(model)，完全在 VM 之外运行，产出一个样本（默认走 xqsa 的 dwave-cpu 模拟退火，xquad/sa.py 重导出 build_solver、SolverDWaveCPU 等全部后端）；
3. vm.run(programs.verifier)，calldata 为 [n, flat_edges, model, sample]，开 2 个输出槽，产出 (energy, valid)；
4. vm.run(programs.decoder)，calldata 为 [sample, n]，开 1 个输出槽，产出解码后的 partition。

每个 vm.run() 之间都通过 vm.set_calldata()、vm.set_output_slots() 注入新的 calldata 并重设输出槽（xquad/vm.py）。三个程序互不共享状态，通信只经过 calldata 输入与输出槽；verifier 之所以需要 encoder 的原始输入，是因为它要重放 encoder 以重建约束数据（存在 VM 寄存器里而非模型里），从而独立于任何求解器检查样本的可行性（Three Programs）。

problem.compile() 在内存中把一次 Problem 定义编译成 encoder、verifier、decoder 三个彼此独立的 .xqasm 源文本，不落任何 .xqasm 文件（Using the Examples）。

换求解器：同一个模型，五种后端

--solver 决定模型在哪里被求解，模型与 encoder 完全不变。Backends 列出了五种后端（examples/maxcut/README.md 给出安装方式）：

名称	求解位置	安装方式
dwave-cpu（默认）	本地 CPU，模拟退火，无需硬件与凭据	pip install xquad
dwave-qpu	D-Wave Leap 云端物理量子退火硬件	pip install xquad[dwave]
cuda-gpu	本地 NVIDIA GPU，模拟退火	pip install xquad[cuda]
metal-gpu	本地 Apple Silicon（macOS），模拟退火或 block Gibbs 采样	pip install xquad[metal]
quip	Quip 网络：提交给去中心化计算市场，由矿机求解	pip install xqsa[quip]

每个 runner 都通过 xqsa.build_solver(name, seed=...) 按名称构造后端，调用方保持后端无关（Solving Overview）。seed 只到达三个经典模拟退火后端；dwave-qpu（物理硬件无种子）与 quip（环境配置、矿机自有随机性）会忽略它。

注意：非默认求解器不会复现上述标准输出——不同的 RNG/硬件会产生不同样本。make example-smoke 始终只跑 dwave-cpu，且以不变式（valid == 1）而非精确输出作为校验标准。另外，quip 等后端需要各自的硬件或凭据，缺省时不破坏基础安装，只有真正构造对应求解器类时才会因 ImportError 失败并提示应补装的 extra（Install XQuad）。

下一步：把这次运行拆成五步

如果想知道这次运行每一步到底发生了什么，What Happened 把这条命令拆成五个动作，并逐一指向完整讲解的章节：问题变成三个程序、encoder 构建模型、求解器最小化它、verifier 独立校验并计算能量、decoder 把样本转成 partition。若想用 xqcp 定义自己的问题，Modelling 从 Knapsack 的输入声明讲起；想把某个示例改造成自己的问题，Using the Examples 以 Max-Cut 改造成带固定端点的最小 s-t 割为例，完整演示了仅需两处小改动的过程。