XQuad 旅行商问题（TSP）端到端实战：从 xqcp 建模到 QUBO 采样、验证与解码

导读：本文以 xquad 仓库中 examples/tsp/README.md 为核心，完整讲解如何用 XQuad 工具链求解经典 TSP：先用 xqcp 约束规划 DSL 把"最短哈密顿回路"编码为一个带 one-hot 约束的 QUBO 模型，再经三程序（Encoder/Verifier/Decoder）管线在 Python 参考 VM 或 Rust VM 上运行，交由 xqsa 求解器采样，最终输出能量、合法性标记与解码后的城市序列。读完本文，你将掌握 XQuad 从问题建模到结果验证的完整调用链，并理解 XQMX 模型中约束常数"消失"导致的能量偏移这一关键细节。

问题定义：最短哈密顿回路

TSP 示例的目标是：给定 N 个城市以及一个随机对称的距离矩阵，找出一条访问每个城市恰好一次并返回起点的最短回路（哈密顿回路）。仓库内对应实现位于 runner.py 与 README.md。

该示例被收录在 examples/manifest.yaml 的 graph-problems 分组中，标注为 hardware: true——意味着它同时属于 CI 中会被回放到真实硬件求解器（cuda-gpu、dwave-qpu、metal-gpu）上的三个代表性示例之一（二进制问题的 maxcut、排列问题的 tsp、带约束问题的 knapsack）。

QUBO 形式化

要素	定义
输入	num_cities（整数）、distance_matrix（Vec，扁平上三角，共 n*(n-1)/2 项）
模型	一个 n x n 的二进制网格，x[i, p] = 1 表示城市 i 位于回路位置 p
目标	回路中相邻位置的成对距离之和
约束	行 one-hot（每个城市恰好占据一个位置）与列 one-hot（每个位置恰好容纳一个城市），罚值均取 100

在 runner.py 的 build_problem() 中，距离矩阵由固定种子的 random.Random(seed) 生成，每个城市对的距离落在 [1, 100]；上三角扁平索引由 xq_triu(i, j) 计算。模型通过 problem.define_model(size=num_cities * num_cities, domain=Domain.BINARY, rows=num_cities, cols=num_cities) 声明为二进制二维网格——rows/cols 是后面 apply_onehot_row/apply_onehot_col 合法性的前提，省略它们会在运行期抛出 InvalidGridDimensions。

哈密顿量：三项之和

TSP 的哈密顿量是三项之和：

$$H = H_{\text{dist}} + H_{\text{row}} + H_{\text{col}}$$

回路长度项 (H_{\text{dist}})：对每对城市 (i < j) 和每个位置 (p)，无论回路以哪个方向访问它们（城市 i 在 p、城市 j 在下一位置，或反过来），都触发一项：

$$H_{\text{dist}} = \sum_{i<j} \sum_{p=0}^{n-1} d_{ij} \left( x_{i,p}\, x_{j,(p+1) \bmod n} + x_{j,p}\, x_{i,(p+1) \bmod n} \right)$$

one-hot 约束项 (H_{\text{row}}) 与 (H_{\text{col}})：由 DSL 的 apply_onehot_row / apply_onehot_col 以罚值 (P = 100) 加入：

$$H_{\text{row}} = P \sum_{i=0}^{n-1} \left( \sum_{p=0}^{n-1} x_{i,p} - 1 \right)^2, \qquad H_{\text{col}} = P \sum_{p=0}^{n-1} \left( \sum_{i=0}^{n-1} x_{i,p} - 1 \right)^2$$

在 runner.py 中，这两组约束分别通过两个 range 循环逐行、逐列施加，罚值硬编码为 100。

关键细节：XQMX 没有常数项，"满足"的约束贡献的是 -P 而非 0

XQMX 模型没有承载常数项的字段。每个被满足的 one-hot 约束会把公式中的 +P 丢掉，在存储的模型中留下 -P 的线性项，而不是 0——详细推导见 约束建模文档。

因此，虽然 (H_{\text{row}})、(H_{\text{col}}) 在合法回路上按公式书写为零、不会改变合法回路之间的最短者排序，但实际存储模型中被满足的约束贡献的是 -P 而非 0。这就是下文工作示例中 -2 * P * n = -800 项的来源：4 行 + 4 列共 8 个约束，每个贡献 -100。违规情形（一个城市占据两个位置，或一个位置容纳两个城市）仍然比满足约束更"贵"。

runner.py 的 run() 函数正是这种结构的直接反映：encoder 输出模型，solver 采样，verifier 重放约束并计算 (energy, valid)，decoder 提取回路。可参考 三程序架构文档 理解为什么这套拆分是 XQuad 的规范形态。

罚值 P 的选择：不是所有实例都安全

"每个非法网格的能量是否都高于每个合法回路"取决于 (P) 与违规所能"买回"的回路长度差之间的相对关系。通用判据见 约束建模文档的罚值选择章节：罚值必须超过任何违规赋值相对于最优可行解所能获得的最大目标改进。

以本示例的两个具体实例为证：

• --n 4 --seed 42：在 (P = 100) 下判据成立。最优非法网格得分为 -581，比最差合法回路的 -587 高 6，因此任何违规解都不会被误选。
• --n 5 --seed 7：判据不成立。一个非法网格得分 -770，低于 120 个合法回路中的 40 个——这意味着仅靠默认罚值并不能在所有实例上保证可行性。

这提示了一个实操原则：罚值应当针对具体实例校验，而不是"抄一个固定值"。XQuad 的 约束文档 还给出了一个更紧的阈值思路：对 equality 形状的违规（one-hot、equality、atleast、atleastw），整数超量 d 实际付出 penalty * d^2，因此决定阈值的是 value gap / excess^2 最大的违规者，而不是价值缺口最大的那个；当问题大到无法枚举时，退而求其次的安全上限是"所有线性系数绝对值之和（二次目标再加所有二次系数绝对值之和）"。

用到的 DSL 方法与底层实现

该示例覆盖了 xqcp DSL 的大部分建模原语：

DSL 调用	作用
problem.input()	声明带类型的 calldata 输入（num_cities、distance_matrix）
problem.define_model()	分配二进制二维网格 XQMX 模型
problem.stow()	把中间计算结果绑定到命名寄存器（如 dist）
problem.range()	发射 RANGE 循环
model.quadratic[(i, p), (j, p)].add()	用二维网格坐标累加二次耦合
model.apply_onehot_row()	每个城市一条 ONEHOTR 约束
model.apply_onehot_col()	每个位置一条 ONEHOTC 约束
problem.output()	声明带类型的输出槽（tour）
problem.sample.colfind()	在指定列中查找值为 1 的行索引

这些方法在 xqcp/problem.py 中有对应实现（Problem.input、define_model、range、stow、output 等），编译产物是三个独立的 .xqasm 源码字符串，由 problem.compile() 在内存中生成，无需手写任何汇编文件。

runner.py 中的建模核心循环（第 72-78 行）值得细读：外层 range 遍历城市对 (city_i, city_j)，取出上三角距离 dist 后，内层 range 遍历位置 position，用 next_position = (position + 1) % num_cities 构造相邻位置，然后向模型同时累加两个方向的二次项——这与 (H_{\text{dist}}) 公式中的两个被加项一一对应。

解码端（第 86-87 行）用 problem.sample.colfind(col=position, value=1) 对每个位置查找"该位置上是哪个城市"，逐列收集成 tour 向量。

六步管线：三程序 + 一次求解

整体流程如下：

1. CP（xqcp）——生成随机对称距离矩阵，声明 n x n 二进制网格，添加二次距离项与 one-hot 行/列约束；
2. 汇编——通过 xquad.asm 把 .xqasm 文本编译为字节码；
3. 编码——在所选 XQVM 上运行 encoder，产出 XQMX 模型；
4. 采样——求解器在模型上运行 SA/QPU/GPU；
5. 验证——verifier 检查样本为二进制且满足行/列 one-hot 约束，然后计算能量；
6. 解码——decoder 把样本提取为城市索引序列。

第 3-6 步是三个相互独立的 XQVM 程序、中间夹一次求解器调用，彼此只通过 calldata 与输出槽共享数据：

flowchart LR
    ENC[Encoder] -->|model| SLV[xqsa solver]
    ENC -->|model| VER[Verifier]
    SLV -->|sample| VER
    SLV -->|sample| DEC[Decoder]
    VER -->|energy, valid| OUT[Host program]
    DEC -->|tour| OUT

各程序的 calldata 分工为：encoder 接收 num_cities, distance_matrix；verifier 接收 model, sample, num_cities；decoder 接收 sample, num_cities。为什么必须拆成三个程序而非一个？因为 XQVM 没有任何指令能调用外部求解器——求解发生在宿主代码里、两次 VM 运行之间，模型在 encoder 结束时还不存在样本，程序自然无法"边构建模型边检查答案"。完整论证见 三程序架构。

宿主侧的调用顺序（runner.py）

run() 函数（runner.py 第 136-171 行）精确复刻了上述数据流：

1. vm.run(programs.encoder)，calldata [n, distances]，1 个输出槽，得到 XQMX 模型；
2. solver.solve(model)（完全在 VM 之外），得到 sample；
3. vm.run(programs.verifier)，calldata [n, distances, model, sample]，2 个输出槽，得到 (energy, valid)；
4. vm.run(programs.decoder)，calldata [sample, n]，1 个输出槽，得到 tour。

--interpreter 参数决定这三段程序跑在哪个后端：python 对应纯 Python 参考 VM（xqvm_py），rust 对应经由 xqffi 的 Rust 解释器；二者对同一字节码产生确定性一致的输出。注意 --interpreter 与 --solver 是两条完全独立的轴——前者选 VM，后者选采样后端。

Rust 侧的同构实现

不想用 Python 的读者可以直接看 Rust 版本：xqvm/examples/tsp/main.rs 用 xqasm::assemble_source 内联汇编了三个程序（encoder.xqasm、verifier.xqasm、decoder.xqasm），以 4 城环状距离矩阵驱动同一三程序管线。其中 verifier 对"同一份样本"同时维护两种形状：XqmxModel 形状供 ROWSUM/COLSUM/COLFIND 等网格指令使用，XqmxSample 形状供 ENERGY 使用（QUI-410 之后 ENERGY 只接受 Sample，不接受 Model），两者由同一份 dense 向量派生、不会漂移。手写汇编的 encoder 中可以看到 ADDQUAD、ONEHOTR、ADDLINE 等指令与 DSL 高层调用的一一对应。

运行与工作示例

命令行用法

uv run python examples/tsp/runner.py --seed 42
uv run python examples/tsp/runner.py --n 5 --seed 7 -o /tmp/tsp.json

Flag	默认值	说明
--n	4	城市数量
--solver	dwave-cpu	求解器后端（见下节）
--interpreter	python	XQVM 后端：python 或 rust
--seed	42	随机种子
-o	stdout	把 JSON 结果写入文件

4 城实例的完整推演

uv run python examples/tsp/runner.py --n 4 --seed 42 构造的实例（边标签为 distance_matrix 值，按城市对的上三角位置索引）：

graph LR
    0 ---|82| 1
    0 ---|15| 2
    0 ---|95| 3
    1 ---|4| 2
    1 ---|36| 3
    2 ---|32| 3

两个解释器返回同样的结果：

{
  "_note": "canonical CI golden",
  "_seed": 42,
  "energy": -650,
  "n": 4,
  "tour": [0, 2, 1, 3],
  "tour_distance": 150,
  "valid": 1
}

tour_distance 验证：d(0,2) + d(2,1) + d(1,3) + d(3,0) = 15 + 4 + 36 + 95 = 150，与合法回路的 (H_{\text{dist}}) 一致。

energy 验证：energy = H_dist + H_row + H_col。在合法回路上，4 行与 4 列各自只贡献其唯一激活变量的 -P 线性项、二次项贡献为 0（同一行/列内没有两个同时为 1 的变量），于是每个约束族贡献 -P * n，得到：

$$energy = tour\_distance - 2 \times P \times n = 150 - 2 \times 100 \times 4 = -650$$

与运行输出完全吻合。若读者想复现 Rust 侧的能量推演，main.rs 中的 identity 回路（[0,1,2,3]，环状距离）对应 6 - 800 = -794，同样被 ensure! 断言锁定。

解码结果的规范化

一个哈密顿回路在语义上等价于其任意旋转与任意反向（2n 种表示），朴素采样器可能返回其中任何一种。runner.py 的 canonicalize_tour()（第 103-133 行）先把回路旋转到以城市 0 开头，再在正向与反向之间取字典序较小者，从而让 make example-smoke 可以对 golden.json 逐字节 diff。这是必要的：Rust 与 Python 解释器在不同宿主平台上曾因 decoder 的 XQMX 扫描迭代顺序差异而在"方向"上不一致（QUI-465），但能量、回路距离、合法性这些不变量始终相同。

选择求解器

求解器由 xqsa 适配层提供，--solver 接受下列后端名称：

名称	硬件	安装
dwave-cpu	CPU（默认）	pip install xquad
dwave-qpu	D-Wave Leap 账号	pip install xquad[dwave]
cuda-gpu	NVIDIA CUDA GPU	pip install xquad[cuda]
metal-gpu	Apple Silicon（macOS）	pip install xquad[metal]
quip	Quip 网络（远程 miner，环境变量配置）	pip install xqsa[quip]

GPU/QPU 的驱动先决条件见 README 的 GPU/QPU support 一节，各求解器参数调优的快速入门见 xqsa 求解器文档。extra 可组合安装，例如 pip install xquad[cuda,dwave]。

两个需要记住的约束：

• 非默认求解器不会复现规范输出——不同后端 RNG/硬件行为不同；
• example-smoke 总是使用 dwave-cpu（scripts/example-smoke.py 中对每个示例以 --seed 42 --solver dwave-cpu 在两种解释器上各跑一遍）。

规范性验证：不变量优先于逐字节一致

example-smoke 对 --seed 42 --solver dwave-cpu 校验两个解释器都产出 valid == 1，并按不变量而非精确输出断言——因为模拟退火对 BQM 构造顺序敏感，两个路径可能找到不同但同样合法的极优值。该脚本同时会检查 xqffi.verifier.verify_source 可导入：编译产物在运行前必须真正经过字节码验证器，而不是因 ImportError 被静默跳过。

结合 使用示例文档 可知，tsp（与 maxcut、knapsack）在默认种子下恰好没有同能量并列最优，因此两种解释器返回完全相同的解码结果；而 graph_coloring、bin_packing、set_cover、max3sat 等存在并列最优的示例，解码结果可以不同但同样合法。

延伸阅读

• 约束建模：罚值选择与能量偏移原理 —— 本文 -800 偏移与罚值阈值的完整推导来源；
• 三程序架构：为什么 XQuad 拆成 Encoder/Verifier/Decoder；
• xqsa 求解器适配层 与 根 README 的安装与包映射；
• Rust 三程序实现：xqvm/examples/tsp/main.rs 及其 encoder.xqasm、verifier.xqasm、decoder.xqasm；
• 示例清单与硬件标记：examples/manifest.yaml、CI 冒烟脚本 scripts/example-smoke.py。