【免费下载链接】xquadA rust implementation of the Quip Networks quantum virtual machine.项目地址https://gitcode.com/gh_mirrors/xq/xquad点击查看免费下载本文以开源仓库 xquad 中的 bin_packing 示例 为主线完整讲解如何把一个经典组合优化问题——「将 N 件整数尺寸物品装入容量为 C 的最小数量箱子」——建模为二次无约束二值优化QUBO问题并通过 XQuad 工具链xqcp约束编程 DSL →.xqasm→ XQVM 虚拟机 →xqsa求解器端到端跑通。读完本文你将掌握二元网格模型的声明方式、用 ONEHOTR / IMPLIES / SLACK EQUALITY 三类约束表达装箱语义的建模技巧、指示变量行indicator row对目标函数区分度的作用以及如何用 Python / Rust 两种解释器与五种求解器后端运行并校验结果。问题定义与 QUBO 建模思路问题描述装箱问题Bin Packing的目标是把 N 件给定整数尺寸的物品装入尽量少的箱子每个箱子有固定容量 C。示例 README 给出的输入为N物品数量Vec类型输入B箱子数量C箱子容量输出是最小化实际启用的箱子数量同时满足三项约束每件物品恰好装入一个箱子、物品只能进入已启用的箱子、每个箱子的装载量不超过容量。模型结构(N 1) × B二元网格示例使用xqcpDSL 的define_model()声明一个二元变量网格runner.pyproblem.define_model( size(num_items 1) * num_bins_in, domainDomain.BINARY, rowsnum_items 1, colsnum_bins_in, )行0..N-1是分配单元x[i, b] 1表示物品 i 装入箱子 b第 N 行是指示行y[b] 1表示箱子 b 被启用至少装了一件物品。网格总变量数为(N 1) * B一维编号为x[i*B b]其中x[N*B b] y[b]。目标函数为什么必须用指示变量行在 runner.py 中目标以线性项形式加到每个指示变量上with problem.range(0, num_bins_in) as b: problem.model.linear[num_items, b].add(BIN_COST)其中BIN_COST 10见 runner.py 顶部常量远小于各约束惩罚项200 / 100因此它只在可行装箱之间打破平局永远不会压倒约束。README 特别解释了一个建模陷阱如果把同样的偏置bias平均撒到所有分配单元上那么每个可行装箱的能量都恒等于 N——因为每件物品恰好落入一个箱子总和不变一个 1 箱方案和一个 3 箱方案将无法区分。指示行把「箱子是否被使用」变成显式的二元变量目标才能真实计数被打开的箱子数量。DSL 方法清单与约束编码原理示例用到的全部 DSL 方法README 中列出的六项及其底层实现如下DSL 方法语义源码位置model.apply_onehot_row(row, penalty)对行施加 one-hot 约束该行恰好一个变量为 1xqcp/symbols.pymodel.apply_implies(coord_a, coord_b, penalty)蕴含约束x[i,b] - y[b]xqcp/symbols.pyproblem.vec()分配未类型化的向量寄存器用于索引与系数xqcp/problem.pyproblem.slack(indices, coeffs, start_index, capacity)生成松弛变量条目并追加到索引/系数向量xqcp/problem.pymodel.apply_equality(indices, coeffs, target, penalty)加权等式P*(sum(a_k*x_k) - b)^2xqcp/symbols.pyxq_bitlen(value)BITLENfloor(log2(v)) 1用于确定每个箱子的松弛块宽度xqcp/init.py约束一每件物品恰好一个箱子ONEHOTR对每件物品 i要求其所在行的 B 个分配变量中恰好一个为 1惩罚 200with problem.range(0, num_items) as i: problem.model.apply_onehot_row(i, 200)apply_onehot_row要求模型必须是二维的内部调用_require_2d检查对应 XQVM 的 ONEHOTR 约束原语。约束二使用箱子即启用箱子IMPLIES对每个(i, b)单元施加蕴含约束x[i,b] - y[b]惩罚 200物品放进箱子 b 就必须启用箱子 b。实现上把指示变量定位在(num_items, b)即网格最后一行with problem.range(0, num_items) as i: with problem.range(0, num_bins_in) as b: problem.model.apply_implies((i, b), (num_items, b), 200)约束三容量不等式SLACK EQUALITY容量约束sum_i s_i * x[i,b] C是不等式QUBO 只有等式。标准处理方式是引入二元松弛变量把不等式补成加权等式sum_i s_i * x[i,b] slack C。slack_width problem.stow(slack_width, xq_bitlen(capacity_in)) model_vars problem.stow(model_vars, (num_items 1) * num_bins_in) with problem.range(0, num_bins_in) as b: col_indices problem.vec() col_coeffs problem.vec() with problem.range(0, num_items) as i: col_indices.push(i * num_bins_in b) col_coeffs.push(sizes_in.get(i)) # Each bin gets its own slack block, past every model variable. problem.slack(col_indices, col_coeffs, model_vars b * slack_width, capacity_in) problem.model.apply_equality(col_indices, col_coeffs, capacity_in, 100)三个要点值得深入xq_bitlen(capacity)决定松弛块宽度容量 C 的二进制表示需要bitlen(C)个二元松弛变量每个松弛块从(N1)*B b*bitlen(C)开始——既在所有模型变量之后也在前面所有箱子的松弛块之后。每个箱子拥有独立的松弛块README 明确指出如果所有箱子共享同一个起始索引一个箱子的松弛变量可以吸收另一个箱子的超额装载容量约束会被欠约束under-constrained无法正确判定装箱是否超容。slack()方法正是为这个场景设计的——它在编译期把松弛条目追加进索引/系数向量problem.py 的_record_slack。惩罚取 100低于 ONEHOTR / IMPLIES 的 200高于BIN_COST 10保证约束满足优先于目标优化同时目标在可行域内仍然有效区分不同箱子数。输出解码器读取分配矩阵Problem.output()声明一个Types.Vec类型的输出槽源码强制所有输出必须是向量见 problem.py解码器把扁平的分配矩阵写入该向量total_vars problem.stow(total_vars, num_items * num_bins_in) assignment problem.output(assignment, typeTypes.Vec) with problem.range(0, total_vars) as k: assignment.append(problem.sample.getline(k))total_vars N * B只覆盖分配单元不含指示行这样解码器只需引用一个 N 引用即可取回全部分配结果。compile()把记录的动作列表一次性生成三段.xqasm程序problem.py并在编译期通过 XQVM 字节码验证器Phase 1 Phase 2做代码生成检查。六步流水线全景README 的 Pipeline overview 把端到端流程分为六步runner.py 的run()函数是它的直接实现CPxqcp——生成随机物品尺寸声明(N1) × B二元网格按物品加 ONEHOTR 分配约束、按单元加 IMPLIES 链接约束、按箱子加 SLACK EQUALITY 容量约束编译出 encoder / verifier / decoder 三段程序Assemble——.xqasm文本经xquad.asmxqffi的assemble_source汇编为字节码Rust 后端或直接由 Python 参考 VM 解析Encode——在选定的 XQVM 上运行 encoder产出 XQMX 模型Sample——求解器SA / QPU / GPU在模型上采样Verify——verifier 检查样本是否二元、逐物品分配、箱子使用链接与逐箱容量是否满足并计算能量Decode——decoder 从样本中提取箱子分配。三个 VM 会话串联run()用统一的xquad.vm.VM类依次跑三个程序每个程序独立构造一个 VM 实例vm VM(backendbackend) vm.set_calldata([n, num_bins, sizes, capacity]) vm.set_output_slots(1) vm.run(programs.encoder) model vm.outputs()[0]encoder 会话calldata 为[n, num_bins, sizes, capacity]输出 1 个槽位得到XQMX模型采样build_solver(solver_name, seedseed)构造求解器solver.solve(model).sample得到样本若依赖缺失或运行错误ImportError/RuntimeError打印error: ...并以退出码 1 终止verifier 会话calldata 为[n, num_bins, sizes, capacity, model, sample]输出 2 个槽位即energy与validdecoder 会话calldata 为[sample, n * num_bins]把扁平分配向量取出供decode_assignment()转成「每件物品的箱子编号」-1表示未分配。VM类在 xquad/vm.py 中统一封装了 Rust FFI VMxqffi.vm.Vm与纯 Python 参考 VMxqvm_py.ExecutorVMBackend.RUST / PYTHON枚举切换calldata 中的XQMX、Vec、int都在边界完成类型转换_prepare_calldata_rust/_prepare_calldata_python并对模型尺寸、网格形状、系数索引、样本域做了与 bytecode 构造能力一致的预校验。数据生成与结果 JSONmain() 中用random.Random(args.seed)生成确定性随机数据capacity rng.randint(args.n, args.n * 3) sizes [rng.randint(1, capacity // 2) for _ in range(args.n)]物品尺寸在[1, capacity//2]内保证单件物品总能放进至少一个箱子。最终输出 JSON 包含_seed、n、num_bins、sizes、capacity、assignment、energy、valid字段不指定-o时写入 stdout否则写入指定路径。运行方式与全部命令行参数安装后pip install xquad或仓库内uv run直接执行uv run python examples/bin_packing/runner.py --seed 42 uv run python examples/bin_packing/runner.py --n 5 --bins 4 --interpreter rust命令行参数表默认值与说明来自 runner.pyFlag默认值说明--n4物品数量--bins3箱子数量--solverdwave-cpu求解器后端见下文求解器表--interpreterpythonXQVM 解释器python或rust--seed42随机种子-o/--outputstdout把解码结果以 JSON 写入文件solver的可选值由xqsa.registry的SOLVERS字典约束registry.py--interpreter由 argparse 的choices(python, rust)约束。求解器选择名称硬件安装方式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 Network远程 miner环境变量配置pip install xqsa[quip]要点dwave-cpu是唯一无需额外依赖与硬件、可完全复现的基线registry.py也是默认求解器cuda-gpu/metal-gpu构造时会以num_reads200, num_sweeps2000的参数化求解且只有经典 SA 家族dwave-cpu、cuda-gpu、metal-gpu接受 seedD-Wave QPU 是物理硬件、quip由环境配置驱动二者都忽略 seedregistry.py非默认求解器不会复现 canonical 输出RNG / 硬件不同GPU / QPU 的驱动前置条件见仓库根 README 的 GPU/QPU support 章节CUDA 12.x 驱动、Metal 设备、D-Wave Leap 账户与 API token、QUIP_RPC_URL与签名者配置各求解器的参数调优快速上手见 xqsa/README.md额外依赖可组合安装例如pip install xquad[cuda,dwave]。Canonical 输出与一致性验证示例在 examples/manifest.yaml 中登记为「Selection and packing」组的bin_packing条目。CI 冒烟脚本 scripts/example-smoke.py 对每个示例分别用python与rust两种解释器以--seed 42 --solver dwave-cpu运行example-smoke.py并断言valid 1example-smoke.py。冒烟测试是不变量驱动的它只校验两个解释器都产出合法解valid 1并打印各自能量不校验精确输出——因为不同 RNG / 求解器配置下最优装箱可能不唯一。这是 README「Canonical output」一节的核心结论确定性验证看合法性与能量而非逐位比对结果。小结Bin Packing 示例展示了 XQuad 建模的组合约束能力二元网格 指示行表达「最小化被使用对象数量」这一类经典目标ONEHOTR 表达排他分配IMPLIES 表达依赖关系SLACK EQUALITY 组合把容量不等式补成 QUBO 等式且每个箱子的松弛块独立布局以避免约束被稀释。整个流程由xqcpDSL 一段代码编译出 encoder / verifier / decoder 三程序经统一VM接口在 Python 与 Rust 解释器间无缝切换最终由xqsa求解器完成采样与校验。同样的建模骨架可以直接迁移到仓库中的 knapsack、set_cover、vertex_cover 等同类选择 / 装箱 / 覆盖问题。赞分享【免费下载链接】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 预算内选择Selection Under Budget建模用 SLACK EQUALITY 把总量不超过容量编译成 QUBOXQuad 预算内选择Selection Under Budget建模用 SLACK EQUALITY 把总量不超过容量编译成 QUBO 预算内选创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考