【免费下载链接】xquadA rust implementation of the Quip Networks quantum virtual machine.项目地址https://gitcode.com/gh_mirrors/xq/xquad点击查看免费下载图着色Graph Coloring是把 C 种颜色分配给无向图的每个节点、并保证任意相邻节点颜色不同的组合优化问题。本文以仓库中的 examples/graph_coloring/ 为例讲解如何用 XQuad 的xqcp约束编程 DSL 以Domain.CATEGORICAL声明类别变量、自动生成 one-hot 网格并通过 EXCLUDE 约束逐边逐色地禁止同色相邻最终在 encoder → solver → verifier → decoder 的三程序流水线上完成建模、求解、验证与解码。读完本文你将掌握一个可直接运行的图着色端到端示例、所有命令行参数与求解器选型方式以及背后 ONEHOTR / EXCLUDE / IDXGRID / ROWFIND 等指令级实现原理。问题定义proper C-coloring 及其 QUBO 形式化示例 README 将问题明确为为无向图的每个节点分配 C 种颜色之一使得不存在两个相邻节点共享同一种颜色proper C-coloring。在 QUBO 形式化中输入节点数 N、颜色数 C、边列表 edges模型N 个类别变量每个取值于 C 个 case。Domain.CATEGORICAL将其记录为一个 N × C 的二元网格x[v,c] 1表示节点 v 取颜色 c并且每行一个 one-hot每节点恰好一色目标函数无。这是一个纯约束满足问题着色方案的优劣完全由约束违反程度衡量约束每节点 one-hotsum_c x[v,c] 1ONEHOTRpenalty 200由域声明隐含、无需手写每边颜色互斥x[u,c] x[v,c] 1EXCLUDEpenalty 200。一个反直觉的能量数值为什么合法着色不是 0README 特别强调一个合法的 C-着色得分是-penalty * N而不是0。原因是 XQMX 模型没有常数项字段每个被满足的 ONEHOTR 在模型中存储的是-penalty而非0。因此在默认参数--n 5、penalty200下合法解的能量为-1000。这一点与 docs/book/src/modelling/constraints.md 中报告的 energy 不只是-total_value的讨论一脉相承EQUALITY展开会丢弃常数项penalty * b^2但ENERGY指令重新计算时被满足的约束项恰好求值为该常数因此合法样本仍然携带这一固定偏移。为什么默认是 4 种颜色颜色数默认取4是经过推敲的一个 G(5, 0.5) 随机图每条边以 0.5 概率独立出现通常包含 4-团4-clique而默认种子--seed 42生成的图正是如此。4-团不存在 3-着色因此若用--colors 3规范实例将不可满足验证器会正确报告valid 0。runner 的注释里也记录了同样的判断依据见 runner.py。编码策略CATEGORICAL 域如何变成 N × C 网格每节点 one-hot 行正是类别变量之所以是类别变量的关键define_model(domainDomain.CATEGORICAL, kC, penalty200)负责把它发射出来网格本身加每行一个 ONEHOTR走的是手写循环会使用的同一条记录路径——编译出的程序与域功能出现之前的写法完全一致。从源码看Domain.CATEGORICAL在 DSL 层只是语法糖xqcp/problem.py 中define_model遇到Domain.CATEGORICAL时会递归委托为define_model(size * k, Domain.BINARY, rowssize, colsk)随后对每一行调用model.apply_onehot_row(variable, penalty)。与此同时_check_domain_argsxqcp/problem.py强制k与penalty必须同时给出且k至少为 2——只有一个取值的域没有可求解的东西。对应的指令发射逻辑在 xqcp/compiler.py 的_emit_model_allocation中先算size * k用BQMX分配二元模型再经RESIZE把模型重塑为rows × cols网格_emit_onehot_rowxqcp/compiler.py则发射PUSH penalty与ONEHOTR r{model}。指令语义见 conformance/opcodes.mdONEHOTR0x70弹出 penalty 与 row为网格行添加 one-hot 约束EXCLUDE0x72弹出 penalty、j、i在变量 i 与 j 之间添加互斥约束越界[0, size)时抛IndexOutOfBounds。逐边逐色的 EXCLUDE嵌套 range 循环与 IDXGRID 扁平化EXCLUDE 通过嵌套 range 循环按边 (u,v)颜色 c逐对施加。2D 坐标 (u,c) 与 (v,c) 需要用IDXGRID解析为扁平索引u * num_colors c与v * num_colors c。IDXGRID0x5A的语义是弹出 cols、col、row压入扁平网格索引row * cols col见 conformance/opcodes.md。runner.py 中的实现正是这个结构# Exclusion constraint per edge per color: adjacent nodes cannot share a color with problem.range(0, num_edges) as e: offset problem.stow(offset, e * 2) u problem.stow(u, edges_in.get(offset)) v problem.stow(v, edges_in.get(offset 1)) with problem.range(0, num_colors_in) as c: problem.model.apply_exclude((u, c), (v, c), 200)边列表以扁平向量传入每条边 (u, v) 展平成两个连续整数offset e * 2定位起点。编译器侧的_emit_excludexqcp/compiler.py会对 2D 模型逐坐标调用emit_flat_index(row, col, cols_reg, ...)生成 IDXGRID 序列随后PUSH penalty与EXCLUDE r{model}。读回答案sample.case(v) 与 ROWFIND 的未着色哨兵解码阶段把求解器返回的二元样本读回为每个节点取哪种颜色。sample.case(v)是对节点 v 所在行执行一次 ROWFIND寻找值为 1 的那一列ROWFIND0x67弹出 value 与 row压入第一个匹配该值的列号找不到则返回-1见 conformance/opcodes.md。因此一行没有任何 1未着色时返回-1这正是示例在宿主代码中使用的未着色哨兵。从源码看case在 xqcp/symbols.py 中定义为rowfind(row, 1)的别名它适用于任何 2D 二元网格无论该网格是否由Domain.CATEGORICAL构建。rowfind同时要求模型为 2D_require_2d否则在编译期直接抛错。runner 的输出循环runner.py将每个节点的 case 追加进colors输出向量colors problem.output(colors, typeTypes.Vec) with problem.range(0, num_nodes) as node: colors.append(problem.sample.case(node))DSL 方法速查DSL 调用作用problem.define_model(sizeN, domainDomain.CATEGORICAL, kC, penalty200)声明 N × C 二元网格及其逐行 one-hotmodel.apply_exclude((u, c), (v, c), penalty)对每边颜色施加 EXCLUDE 互斥约束sample.case(node)读取节点所取的颜色 case或-1完整流水线CP → 汇编 → 编码 → 采样 → 验证 → 解码示例 README 给出了六步流水线与 XQuad 的三程序架构一一对应参见 docs/book/src/concepts/three-programs.mdCPxqcp生成随机图声明 N 个取值于 C 个 case 的类别变量并为每个边颜色对添加 EXCLUDE 约束Assemble通过xquad.asm把.xqasm文本汇编为字节码Encode在选定的 XQVM 上运行 encoder产出 XQMX 模型Sample求解器SA / QPU / GPU在模型上采样Verifyverifier 检查样本是否二元、one-hot 行和、逐边互斥并重算能量Decodedecoder 用 ROWFIND 读取每个节点的 case输出每个节点的颜色索引。在runner.py的run()函数examples/graph_coloring/runner.py中三程序各自通过统一的 xquad/vm.pyVM包装器执行calldata 与输出槽遵循固定契约encodercalldata[n, num_colors, m, flat_edges]1 个输出槽 → 模型断言为XQMXverifiercalldata[n, num_colors, m, flat_edges, model, sample]2 个输出槽 →(energy, valid)decodercalldata[sample, n]1 个输出槽 → 颜色向量colors。求解发生在 VM 之外build_solver(solver_name, seedseed)构造求解器solver.solve(model).sample返回样本随后再回到 VM 运行 verifier 与 decoder。这正是 docs/book/src/modelling/compiling.md 描述的通用契约encoder 输出槽 0 为模型verifier 输出(energy, valid)decoder 按problem.output()声明顺序每槽一个输出。运行与命令行参数从仓库根目录运行uv run python examples/graph_coloring/runner.py --seed 42 uv run python examples/graph_coloring/runner.py --n 6 --colors 4 --interpreter rustFlag默认值说明--n5节点数--colors4颜色数--solverdwave-cpu求解器后端见下文选型--interpreterpythonXQVM 后端python或rust--seed42随机种子-ostdout将 JSON 结果写入文件随机图生成在 runner.py 中edges [(i, j) for i in range(n) for j in range(i 1, n) if rng.random() 0.5]即 G(n, 0.5) 模型。结果 JSON 包含_seed、_note固定为canonical CI golden、n、num_colors、edges、colors、is_valid、energy、valid等字段其中is_valid由宿主端is_valid_coloring独立核对无相邻同色且每节点都已着色runner.py。选择求解器--solver接受下表名称xqsa.SOLVERS中可枚举参见 xqsa/README.md名称硬件安装dwave-cpuCPU默认pip install xquaddwave-qpuD-Wave Leap 账户pip install xquad[dwave]cuda-gpuNVIDIA CUDA GPUpip install xquad[cuda]metal-gpuApple SiliconmacOSpip install xquad[metal]quipQuip 网络远程矿工环境变量配置pip install xqsa[quip]GPU/QPU 的驱动前提见 README.md各求解器参数调优快速上手见 xqsa/README.md。需要注意非默认求解器不会复现规范输出不同的 RNG/硬件example-smoke始终使用dwave-cpu。另外所有求解器目前只接受二元或自旋模型参见 docs/book/src/concepts/backends.md本示例经 CATEGORICAL 域展开后的模型恰为二元模型因此五种后端均可直接采样。规范输出与 example-smoke 验证make example-smoke会同时运行两种解释器python与rust并校验它们以--seed 42 --solver dwave-cpu运行时均产出valid 1。该冒烟测试是基于不变量的它检查有效性而不是字节级输出一致性——求解器可能从多个等能量最优解中返回不同的一员解码结果因而可能不同但两种解释器下的energy与valid必然一致参见 docs/book/src/examples/using-examples.md 对graph_coloring平局最优解的解释--seed 1时 python 与 rust 会给出不同的colors数组但能量相同且均有效。完整可复制的 build_problem以下是示例完整的建模函数examples/graph_coloring/runner.py可直接作为自己问题的起点def build_problem(n: int, num_colors: int, edges: list[tuple[int, int]]) - Problem: Construct a Graph Coloring QUBO from one categorical variable per node. Domain.CATEGORICAL records the N x C binary grid and the one-hot row per node that says each node takes exactly one color. What is left to write is the part the domain does not imply: EXCLUDE per (edge, color): x[u,c] and x[v,c] cannot both be 1 (adjacent nodes may not share a color). problem Problem(GraphColoring) num_nodes problem.input(num_nodes, typeTypes.Int) num_colors_in problem.input(num_colors, typeTypes.Int) num_edges problem.input(num_edges, typeTypes.Int) edges_in problem.input(edges, typeTypes.Vec) problem.define_model( sizenum_nodes, domainDomain.CATEGORICAL, knum_colors_in, penalty200, ) # Exclusion constraint per edge per color: adjacent nodes cannot share a color with problem.range(0, num_edges) as e: offset problem.stow(offset, e * 2) u problem.stow(u, edges_in.get(offset)) v problem.stow(v, edges_in.get(offset 1)) with problem.range(0, num_colors_in) as c: problem.model.apply_exclude((u, c), (v, c), 200) # Output: the color each node took, or -1 where its row stayed empty colors problem.output(colors, typeTypes.Vec) with problem.range(0, num_nodes) as node: colors.append(problem.sample.case(node)) return problem扩展方向调整实例规模与图模型修改--n/--colors即可但请留意 README 的告诫——当随机图含 4-团而颜色数不足时实例不可满足valid会如实报告为 0调优惩罚权重示例固定 penalty 为 200关于 penalty 的选择枚举最紧违反者、纯线性目标的安全上界等可参考 docs/book/src/modelling/constraints.md更换求解器后端保持--interpreter与--solver解耦build_solver按名称选择后端宿主代码无需改动查看编译产物problem.compile()返回的programs.encoder/programs.verifier/programs.decoder是三个独立.xqasm字符串打印即可观察 ONEHOTR、IDXGRID、EXCLUDE 与 ROWFIND 的实际发射序列参见 docs/book/src/modelling/compiling.md。赞分享【免费下载链接】xquadA rust implementation of the Quip Networks quantum virtual machine.项目地址https://gitcode.com/gh_mirrors/xq/xquad点击查看免费下载相关推荐XQuad Bin Packing 端到端实战QUBO 建模、SLACK 松弛编码与三程序流水线详解XQuad Bin Packing 端到端实战QUBO 建模、SLACK 松弛编码与三程序流水线详解 Bin Packing装箱问题是组合优化中的经典 N用 XQuad 求解最大独立集MISQUBO 建模、SLACKEQUALITY 约束编码与端到端流水线实战用 XQuad 求解最大独立集MISQUBO 建模、SLACKEQUALITY 约束编码与端到端流水线实战 最大独立集Maximum IndependXQuad 旅行商问题TSP端到端示例深度解析从 QUBO 建模、XQVM 三程序流水线到求解与验证XQuad 旅行商问题TSP端到端示例深度解析从 QUBO 建模、XQVM 三程序流水线到求解与验证 本文以 docs/book/src/examples创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考