【免费下载链接】xquadA rust implementation of the Quip Networks quantum virtual machine.项目地址https://gitcode.com/gh_mirrors/xq/xquad点击查看免费下载本指南以 XQuad 仓库中 docs/book/src/cookbook/ 一章为骨架系统讲解如何把一个新问题识别为五种可复用编码形态Permutations、Assignment、Selection Under Budget、Mutual Exclusion、Soft vs. Hard Constraints之一以及如何在选定形态后用 XQCP DSL 的apply_*约束调用落地为 XQVM 汇编程序。读完本文你将掌握从问题描述出发、借助仓库内examples/的成熟范例快速搭建 QUBO 模型、估算变量成本、定位典型失败模式并正确处理实数数据整数缩放的能力。为什么需要一本菜谱从示例到形态仓库examples/目录下的十四个示例清单每一个都解决一个具体问题——Knapsack、TSP、Graph Coloring——并且每个都包含一份可运行的编码。但仓库本身并没有把这些编码命名为可在非 Knapsack、非 TSP 问题上复用的模式。cookbook章节做的事情正是补上这一步命名五种反复出现的形态每一种都以一个或多个示例为依托并以真正运行过的代码呈现。这五种形态不是凭空归纳的它们之间存在内在联系Permutations 与 Assignment 是同一个网格去掉一族约束Permutations 的列 one-hot 被移除后就是 Assignment。常见的错误方向见 Assignment 的失败模式。Selection Under Budget 与 Mutual Exclusion 在一条边界上重叠容量恰为1的一对变量正是EXCLUDE指令族直接给出的能力参见 Mutual Exclusion 中不用 EXCLUDE 编码同一规则。组合问题可以按形态拆分examples/bin_packing/组合了两种形态Assignment 加一个容量约束examples/graph_coloring/也组合了两种Assignment 加互斥。把问题读成每一部分像哪种形态对组合问题的处理方式与单形态问题相同。本章假定读者已经熟悉 Modelling 章节用相同的xqcp调用构建问题不再重复解释以及 Quadratic Models 概念罚项是什么、为什么存在。五种形态总览形态页面何时选用典型示例Permutations排列N 个事物需要完整排序每个事物恰好一个位置每个位置恰好一个事物examples/tsp/Assignment分配N 个事物各选 B 个槽位之一不要求每个槽位都被使用也不要求 N 等于 Bexamples/bin_packing/Selection Under Budget预算下选择在不超过固定容量的前提下选择加权事物子集examples/knapsack/Mutual Exclusion互斥两个选择冲突或一个选择要求另一个examples/graph_coloring/、examples/max_independent_set/Soft vs. Hard Constraints软硬约束一条必须成立的规则与一条应该成立的偏好并存examples/portfolio_opt/、examples/max3sat/所有约束方法都挂在problem.model由define_model()提供的ModelRef上且都接受一个penalty参数——这一调用面在 xqcp/symbols.py 的源码中可以直接验证apply_onehot_row、apply_onehot_col、apply_exclude、apply_implies、apply_equality、apply_atleast、apply_atleastw、apply_inequality全部经由_record_*系列方法记录为 XQVM 指令。形态一Permutations——每样东西一个位置每个位置一样东西识别与编码当问题语句里出现排序每个访问一次时就该想到排列形态一条游览路线或 N 位客人坐进 N 把椅子。编码是一个 (N \times N) 的二进制网格x[thing, position] 1表示thing 坐在 position对每一行、每一列施加 one-hot 约束ONEHOTR对应这个东西恰好占一个位置ONEHOTC对应这个位置恰好放一个东西。可行的赋值就是一个排列矩阵——每行每列恰好一个1。examples/tsp/是仓库中体现此形态的唯一示例x[city, position] 1表示城市位于路线位置目标在同样的行列 one-hot 对之上叠加相邻位置城市间的距离TSP 文档、examples/tsp/runner.py。剥离距离目标后模式本身独立成立——分配网格、施加两种 one-hot、用colfind解码from xquad.cp import Domain, Problem, Types def build_problem(n: int) - Problem: problem Problem(PurePermutation) num_items problem.input(num_items, typeTypes.Int) problem.define_model(sizenum_items * num_items, domainDomain.BINARY, rowsnum_items, colsnum_items) with problem.range(0, num_items) as row: problem.model.apply_onehot_row(row, penalty10) with problem.range(0, num_items) as col: problem.model.apply_onehot_col(col, penalty10) perm problem.output(perm, typeTypes.Vec) with problem.range(0, num_items) as position: perm.append(problem.sample.colfind(colposition, value1)) return problem以n 3编译、在 Rust VM 上运行编码器再用SolverDWaveCPU在seed42下求解三个事物的全部六种排列在-60处并列所以不同的 seed 解码出不同的排列但下面两行始终成立decoded permutation (thing at each position): [0, 1, 2] is a permutation of range(N): True energy: -60xquad verify --text接受编译好的编码器ok: permutation_encoder.xqasm (29 instructions)xquad run --text ... --calldata 3从汇编字节码确定性地复现同一模型独立于上面的 Python 求解outputs: [0] Model(XqmxModel { domain: Binary, size: 9, linear: {0: -20, ..., 8: -20}, quadratic: {(0, 1): 20, (0, 2): 20, ..., (7, 8): 20}, rows: 3, cols: 3 })九个-20线性项每个单元格属于一行一列所以各吸收-penalty两次和十八个20二次项每个同行对与每同列对——正是ONEHOTR与ONEHOTC在 High-Level Constraints 文档 中给出的展开式叠加在同一网格上。ONEHOTR的展开式为 (H \mathrel{} \text{penalty} \cdot (\sum_c x_{\text{row},c} - 1)^2)即对每列加-penalty线性项、对每对同列变量加2·penalty二次项ONEHOTC完全对称。examples/tsp/构建相同的行列结构并叠加距离系数目标加入后排列半部分没有任何改变。变量成本网格是 (N^2) 个变量——没有 slack、没有辅助变量因为ONEHOTR和ONEHOTC都只是重写已存在单元格上的系数。这种二次增长才是该形态的真正成本待排序事物数量翻倍变量数变为四倍而这还发生在加入任何目标项之前。失败模式只施加一个轴——只有ONEHOTR而无ONEHOTC或反之——不会报错它产生的是一个每个事物仍恰好选一个位置但没有任何东西阻止两个事物选同一位置的模型。这个更宽松的规则就是 Assignment。另一个失败是结构性的而非语义性的ONEHOTR/ONEHOTC从RESIZE读取网格维度因此没有设置网格的模型就没有行或列可供约束。两种情况都会在需要网格的那条指令上抛出InvalidGridDimensions两个解释器行为一致见 High-Level Constraints。xquad verify无法捕获它因为网格维度是运行时值失败发生在编码器运行时而非编译时。测试 xqcp/tests/test_xqcp.py 明确覆盖了非 2D 模型调用apply_onehot_row/apply_onehot_col被拒绝这一约束。形态二Assignment——每样东西一个槽位槽位可以不空置识别与编码把 N 个事物各匹配到 B 个槽位之一不要求每个槽位都收到事物也不要求 B 等于 N。当问题涉及一个集合匹配进另一个集合、不要求双向匹配时识别它物品进箱子、节点取颜色。这是 Permutations 去掉列半部分的形态。编码为一个 (N \times B) 网格x[thing, slot] 1表示该事物占据该槽位只在每一行施加 one-hot每个事物恰好选一个槽位但一个槽位可以容纳零个、一个或多个事物。注意去掉列约束得到的是一个不同的规则而不是同一规则的更弱形式Permutations 的失败模式 指出的是相反方向的错误——在两个轴都需要时只施加了一个。examples/bin_packing/把每个物品分配到恰好一个箱子——网格的每个物品行一个ONEHOTRBin Packing 文档、examples/bin_packing/runner.py# Assignment constraint: each item i must go in exactly one bin with problem.range(0, num_items) as i: problem.model.apply_onehot_row(i, 200)ONEHOTR是EQUALITY在 (a_k 1)、(b 1) 时的特例High-Level Constraints 直接陈述了这一点。手工编写它——每行一个vec()对、每列推入一个索引和一个1、然后apply_equality(indices, coeffs, 1, 200)——表达同样的约束却要每行花费一个循环和两个向量。这里的模型同时设置了rows和cols所以apply_onehot_row直接可用手写形式毫无收益。装箱网格的行数比物品数多一行第0..N-1行是分配单元格额外的第N行每箱持有一个指示变量apply_implies((i, b), (num_items, b), 200)使任意物品落入箱子 b 的瞬间打开该箱子。这个指示行正是目标得以统计箱数的关键若把偏差散布在分配单元格上每个可行装箱都会求和为 N因为每个物品恰好落在一个箱中无法区分一箱装箱与三箱装箱。运行examples/bin_packing/runner.py --seed 424 个物品、3 个箱子、容量5、尺寸[1, 2, 1, 1]解码为assignment: [2, 2, 2, 2]——四个物品全在 2 号箱总尺寸5对容量5。而rust解释器返回[0, 0, 0, 0]使用哪个单箱是平局两个解释器以不同方式打破。每个物品恰好出现在一个箱子中这正是行约束保证的没有任何东西要求箱子被使用而统计箱数的目标朝反方向推动。装箱还把这种行分配模式与第二种无关的模式组合起来——每箱内容不得超过容量用SLACK加EQUALITY编码与 Selection Under Budget 中的容量约束完全一样。该容量半部分不是本页关注点。变量成本网格花费 (N \times B) 个变量对比 Permutations 的 (N^2)节省全部来自网格当槽位少于事物(B N)时更便宜。去掉列约束在变量上既不花钱也不省钱因为两个 one-hot 族都不分配变量——索引在范围内的EQUALITY自身不会增长model.sizeHigh-Level Constraints。失败模式本页警示的方向与 Permutations 的失败模式 相反给不需要列约束的分配问题加一列 one-hot会静默地把N 个事物进 B 个槽位变成事物与槽位之间的双射后者只有在 (N B) 时才有可行解。如果RESIZE了网格尺寸的 Permutations 形态模型持续返回不可行请检查问题究竟需要两个轴都被约束还是只需要一个。形态三Selection Under Budget——总量不超过容量识别与编码从 N 个各带成本的事物中选择子集使总成本不超过固定容量同时最大化或最小化该子集的某些其他属性。当问题用最多不超过装得下描述逐项权重之和时识别它背包、资产预算、重量限制下的运输。不等式加上不恒为1的逐项权重正是本形态区别于 Mutual Exclusion 的成对、以及普通 one-hot 的 1之处——这里边界是通用容量物品携带任意整数权重。ONEHOTR、ONEHOTC、EXCLUDE、IMPLIES都不能表达不等式ATLEAST与ATLEASTW覆盖镜像的方向Vertex Cover、Weighted Set Cover但 XQVM 没有针对任意加权和的对应物。SLACK弥合了这一缺口把不等式转成EQUALITY可以强制执行的等式——为什么这种替换是精确的见 Constraints 文档指令本身见 SLACK 文档。model.apply_inequality(indices, coeffs, target, capacity, penalty)把两次调用合成一次——见 The Constraint Forms注意其中target参数不是目标值它是 slack 变量开始的位置通常等于真实变量数capacity才是真正的边界必须按位置传参。典型实例examples/knapsack/是此形态的纯净版——Knapsack 文档、examples/knapsack/runner.py。调用它自己的build_problem六个物品、容量12而不是 Modelling 章节已演练过的 seed-42 实例from examples.knapsack.runner import build_problem from xquad.vm import VM, VMBackend n 6 weights [2, 3, 4, 5, 6, 7] values [3, 4, 5, 8, 9, 10] capacity 12 problem build_problem(n, weights, values, capacity) programs problem.compile() vm VM(backendVMBackend.RUST) vm.set_calldata([n, weights, values, capacity]) vm.set_output_slots(1) vm.run(programs.encoder) model vm.outputs()[0]model.size为10六个物品变量加四个 slack 位(S \lfloor \log_2(12) \rfloor 1 4)。用SolverDWaveCPU求解并解码selection [0, 0, 0, 1, 0, 1] weight 12 capacity 12 feasible True value 18 energy -14418 verifier energy -14418 valid 1选中物品 3 和 5重量5和7价值8和10重量恰好等于容量价值18。穷举全部 64 个子集确认18是真正的最优值其中 28 个在容量内没有其他子集达到价值18。xquad verify对编译好的编码器43 条指令通过。底层机制值得展开SLACK向indices/coeffs两个并行向量追加 (S) 个条目——indices追加[start, start1, ..., startS-1]coeffs追加[1, 2, 4, ..., 2^(S-1)]vector-ops.md。随后EQUALITY对组合向量施加 (P \cdot (\sum_k a_k \cdot x_k - b)^2)。若物品之和小于容量某种 slack 组合精确填补缺口若超出任何 slack 组合都无法补救因为 slack 只能加不能减。examples/knapsack/runner.py的build_problem就是先problem.slack(indices, coeffs, num_items, capacity_in)再problem.model.apply_equality(indices, coeffs, capacity_in, 100)编译出的汇编中两条指令紧挨着出现。测试 test_equality_over_slack_checks_a_bound 和 test_inequality_bounds_by_capacity_not_target 分别验证了SLACK 扩展后的等式等价于原不等式和apply_inequality的边界是 capacity 而非 target。变量成本(N) 个物品变量加 (S \lfloor \log_2(\text{capacity}) \rfloor 1) 个 slack 位——对容量取对数而非容量本身这正是最多一百万个单位只需二十个额外变量而非一百万个的原因。Integer Scaling 覆盖了这个公式在选择缩放粒度前值得知道的一个后果slack 数随缩放后的容量增长因此过大的缩放因子花费的是真实变量而不仅仅是更大的系数。examples/bin_packing/对每个箱子重复一次这个SLACKEQUALITY形态处理的是逐箱容量而非单个全局容量——见 Assignment。它的SLACK的start_index参数逐箱推进——model_vars b * xq_bitlen(capacity)——使每箱容量约束指向自己的 slack 块。把这个块复制为逐箱模板时的陷阱是每次都传同一个固定起始索引箱子们会共享 slack 变量一箱溢出可以被另一箱的 slack 吸收。失败模式看起来正确的SLACK/EQUALITY对仍可能不可行原因与罚权重无关如果每个物品的重量都已超过容量或最便宜的单个物品也超过任何 slack 组合都救不了——slack 只朝目标方向加从不从真实物品的贡献中减去SLACK。在伸手去拿 penalty-weight 指南 解释求解器为何一直返回看起来不对的东西之前先检查原始数字——最小物品重量对容量。形态四Mutual Exclusion——两者不可兼得识别与编码两个选择冲突一个解至多取其一。在不能同时至多一个或禁止相连事物共享某属性的邻接规则中识别它相邻节点上的两种颜色、两个重叠的预订。EXCLUDE是直接指令弹出penalty然后两个变量索引加quad[i, j] penalty——纯耦合项、无线性部分当两个变量都为1时恰好花费penalty否则分文不花High-Level Constraints 的 EXCLUDE 小节。本页还覆盖方向性的IMPLIES选i就要求j而非两者都选被禁止。examples/graph_coloring/对每条边的每个颜色施加一次EXCLUDE两个相邻节点不得同时持有同一颜色Graph Coloring 文档、examples/graph_coloring/runner.pywith 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)运行examples/graph_coloring/runner.py --seed 1 --interpreter rust5 个节点、4 种颜色、6 条边返回colors: [0, 1, 0, 0, 2]、is_valid: true、energy: -1000——六条边逐条手工核对都连接着不同颜色的节点。把默认--seed 42实例强压到--colors 3展示了EXCLUDE能做什么、不能做什么。该 seed 的随机边在节点{0, 2, 3, 4}间构成一个 4-团每对节点都是边而 4-团根本没有 3-着色。运行报告is_valid: false、energy: -800、valid: 0对EXCLUDE罚权重的任何调整都改变不了这一点。EXCLUDE强制一条规则它只能强制存在的着色。颜色数默认4正是为此。注意此处生成的验证器的valid与运行器自己的is_valid一致它直接对照样本检查每条EXCLUDE。不用EXCLUDE编码同一规则examples/max_independent_set/需要同样的逐边x_i x_j 1规则——两个相邻节点不能同时在集合中——却用SLACK加EQUALITY而非EXCLUDE构建Max Independent Set 文档edge_indices problem.vec() edge_coeffs problem.vec() edge_indices.push(ni) edge_indices.push(nj) edge_coeffs.push(1) edge_coeffs.push(1) problem.slack(edge_indices, edge_coeffs, num_nodes e, 1) problem.model.apply_equality(edge_indices, edge_coeffs, 1, 200)两者编码同一个不等式EXCLUDE是恰好在成对情形下的一指令便捷形式而SLACKEQUALITY为达成同一规则每对多花一个 slack 变量Selection Under Budget 的模式在此应用于容量1。只要冲突是成对的几乎总是如此就用EXCLUDE仅当互斥需要与已经骑在同一个索引/系数向量上的其他项组合时才用手写形式。运行examples/max_independent_set/runner.py --seed 42与上面图着色默认相同的 5 节点 6 边图节点集{0, 2, 3, 4}构成团返回in_set: [0, 1, 0, 0, 1]——节点{1, 4}、is_independent: true。对同一图运行examples/vertex_cover/runner.py --seed 42返回cover: [1, 0, 1, 1, 0]——节点{0, 2, 3}恰是{1, 4}在{0, 1, 2, 3, 4}中的补集。这不是单一实例的巧合一组节点覆盖所有边当且仅当被排除的节点之间没有边共享所以同一图上的最小顶点覆盖与最大独立集总是互为补集。但vertex_cover自己的约束x_i x_j 1经ATLEAST不是本页的模式——它要求至少一个端点与禁止两者的方向相反。当问题说至少其一时即使图形态在其他地方激发互斥也不要伸手拿EXCLUDE。IMPLIES的系数语义仓库中没有示例调用apply_implies。一个极简演示直接检验符号from xquad.cp import Domain, Problem, Types from xquad.vm import VM, VMBackend problem Problem(ImpliesDemo) n problem.input(n, typeTypes.Int) problem.define_model(sizen, domainDomain.BINARY) problem.model.apply_implies(0, 1, 50) # picking 0 requires picking 1 problem.model.linear[0].add(-30) # a reason to pick 0 at all programs problem.compile() vm VM(backendVMBackend.RUST) vm.set_calldata([2]) vm.set_output_slots(1) vm.run(programs.encoder) model vm.outputs()[0]读回所得系数并手工求值全部四种赋值linear: {0: 20}, quadratic[0,1]: -50 x00 x10 - H0 x00 x11 - H0 x01 x10 - H20 x01 x11 - H-30x01, x10——选0不选1即被禁止的组合——比两者都不选贵20且比合法的x01, x11贵正好50与传入的penalty50一致。x0上的-30奖励正是给求解器一个先选它的理由没有它x00将平凡地支配蕴含关系永远不会被检验。IMPLIES自身的展开linear[i] penalty、quad[i, j] -penaltyHigh-Level Constraints 的 IMPLIES 小节正好产生了这里的20与-50linear[0] -30 50 20linear[1]不变quadratic[0,1] 0 - 50 -50。变量成本EXCLUDE与IMPLIES不增加任何变量——两者都重写一对既有系数。同一规则的SLACK式编码每对多花一个 slack 位因为容量1需要 (S \lfloor \log_2(1) \rfloor 1 1) 位SLACK。失败模式如上文图着色 seed-42 默认所示需要的颜色多于给定颜色数的图不是罚权重调参问题任何penalty值都不能把不可行实例变成可行因为罚项只控制违例有多贵而非违例是否可避免。如果EXCLUDE/IMPLIES约束使最佳返回样本在多个罚权重下都卡在非零违例先检查底层组合结构是否允许解存在再去找 penalty-weight 指南。形态五Soft vs. Hard Constraints——必须成立与最好成立两者的本质区别二次模型中的每条规则都是罚项但并非每个罚项对所属问题含义相同。硬约束是解必须遵守的规则满足或违例没有中间态罚权重唯一回答的问题是违例变得多贵。软约束——更精确的名字是偏好——是解连续支付的代价越多的被厌恶之物花费越多但没有任何数量被标记为禁止。apply_equality、apply_onehot_row、apply_exclude以及 Constraints 文档 中的其余约束族是书写硬规则的方式。偏好则直接写进目标正如 Objectives 文档 所覆盖的完全不需要约束调用。同一问题中的两种examples/portfolio_opt/各携带一种。预算是硬的——sum(x_i) B经apply_equality无条件罚权重200——风险项是软的——对问题认为有风险的每个资产三元组一个三次罚项直接加进目标没有任何伴随的约束调用Portfolio Optimization 文档、examples/portfolio_opt/runner.py# Cubic risk cross-terms via REDUCE with problem.range(0, num_risk) as t: ... w problem.model.reduce(ti, tj, _P_AUX) problem.model.quadratic[w, tk].add(sigma) # Budget constraint: sum(x_i) B (EQUALITY with unit coefficients) ... problem.model.apply_equality(indices, coeffs, budget_in, 200)reduce与ADDQUAD用与任何其他目标项相同的方式构建风险成本——见 Objectives 与 REDUCE 的 High-Level Constraints 小节——REDUCE自身的 Rosenberg 项quad[var_a, var_b] P_aux、quad[var_a, w] -2·P_aux、quad[var_b, w] -2·P_aux、linear[w] 3·P_aux见 xqcp/tests/test_xqcp.py 对辅助变量代数同一性的验证强制的是辅助变量的代数恒等式而非风险规则本身。sigma没有任何阈值含义它像任何其他系数一样在同一和中直接权衡收益与风险。判别性差异阈值 vs. 连续权衡固定四个资产收益[10, 9, 8, 7]、预算3、一个风险三元组(0, 1, 2, sigma)然后扫描sigma。下面的run_case覆盖编码器半部分——编译问题、运行编码器构建模型、求解——与本页早期片段相同。把返回样本解码回投资组合运行programs.decoder作用于[sample, n]与examples/portfolio_opt/runner.py完全相同此处省略因为比较的两侧一致from examples.portfolio_opt.runner import build_problem from xquad.vm import VM, VMBackend from xqsa import build_solver def run_case(sigma): risk_terms [(0, 1, 2, sigma)] problem build_problem(4, [10, 9, 8, 7], 3, risk_terms) programs problem.compile() flat_risk [v for term in risk_terms for v in term] vm VM(backendVMBackend.RUST) vm.set_calldata([4, [10, 9, 8, 7], 3, 1, flat_risk]) vm.set_output_slots(1) vm.run(programs.encoder) model vm.outputs()[0] result build_solver(dwave-cpu, seed42).solve(model, num_reads200) ... # decode via programs.decoder and print, as below解码并打印sigma1与sigma2给出sigma1: portfolio[1, 1, 1, 0] total_return27 energy-1826 sigma2: portfolio[1, 1, 0, 1] total_return26 energy-1826在sigma各自的 20 个求解器 seedseed in range(1, 21)上sigma2每次都切换到{0, 1, 3}收益26每个 seed 都稳定。sigma1行为不同它恰好坐在平局上采样器返回任一组合跨 seed 接近对半——12/20 是{0, 1, 2}8/20 是{0, 1, 3}两者能量相同-1826。平局是精确的而非近似的资产2的风险成本仅当0、1、2三者同时被选时才生效REDUCE的乘积项所以选风险三元组花费-27 sigma对比更安全三元组的固定-26两者在sigma 1时相等一旦sigma 1风险选择就不再划算稳定切换到{0, 1, 3}恰在此处发生。恰好落在平局上的权重不是任一组合都被偏好的证据——它是权重处于边界的证据而那里的单个样本不会告诉你你站在哪一侧。该扫描中的每个选择仍然恰好三个资产——硬预算约束在每个sigma都成立不受影响——而软风险成本偏爱哪三个资产在盈亏平衡点发生变化恰在该点出现平局而非干净切换。这个对比正是两类约束买到的硬规则的罚权重只决定规则能否被打破Quadratic Models、Constraints而软项的权重决定解实际买下多少偏好。完全没有硬约束的软约束examples/max3sat/站在另一极端每条子句都是偏好没有一条是解必须满足的规则问题任何地方都没有apply_*调用Max-3-SAT 文档。子句(i, j, k)恰在其三个文字全为假时花费P_CLAUSE直接加进目标满足零个子句的解合法只是贵。运行examples/max3sat/runner.py --seed 426 个变量、8 个子句对该随机实例满足全部八个satisfied: 8、energy: -80但模型中没有东西会拒绝满足更少的样本——没有与子句满足绑定的valid检查因为没有可检查的约束。valid标志恰好画出这条线。硬约束是apply_*调用生成的验证器对每次调用发射一个检查portfolio_opt的预算是apply_equality所以针对预算3选择全部四个资产的样本返回valid: 0。Max-3-SAT 的子句是目标项所以其验证器中的任何东西都不看它们满足两个子句的样本与满足八个的一样valid。如果一条规则必须成立把它声明为约束Verification 文档 说明valid随后覆盖什么。变量成本两种模式都不直接征税于模型——软项是普通的linear/quadratic系数写入硬约束的成本是它自己的指令所添加的ATLEAST/ATLEASTW/REDUCE增长model.sizeEXCLUDE/IMPLIES/索引在范围内的EQUALITY不增长。portfolio_opt的风险项每项花费一个REDUCE辅助变量所以模型从n增长到n num_risk与共享同一模型的硬预算约束无关。失败模式把偏好写成大罚权重的硬约束会强制一个全有或全无的规则而原本想要的是分级成本——模型永远不会选择付出少量被厌恶之物即使目标其余部分会从中获得更多因为约束的成本在触碰它的瞬间从0跳到penalty * d^2Constraints。反向错误——把必须始终成立的规则写成软目标项——更糟当目标其余部分给出足够回报时没有任何东西阻止求解器打破它而且事后无法检查它是否被打破正如上面max3sat缺失valid检查所直接演示的。形态组合把问题拆成形态的并集五种形态不是孤立的。examples/bin_packing/组合了 Assignment 加容量约束每箱一个SLACKEQUALITY块examples/graph_coloring/组合了 Assignment 加互斥每节点一个ONEHOTR加每条边每个颜色一个EXCLUDE。阅读组合问题的正确方式是每一部分看起来像哪种形态这扩展到组合问题的处理方式与单形态问题相同。一个有用的内部关联Permutations 与 Assignment 是同一网格去掉一族约束Assignment 失败模式 指出错误最常跑的方向Selection Under Budget 与 Mutual Exclusion 在一条边界重叠——一对上的容量恰为1就是EXCLUDE直接给出的指令族Mutual Exclusion。算术页面Integer ScalingInteger Scaling 不是形态——上面每种形态迟早都需要它因为要把实值问题数据转成每种形态所书写的整数系数。罚权重本身的定标、以及读取求解器输出判断廉价的约束违例是否买到了好看的能量属于 Constraints 文档 的领地不是菜谱页。选择缩放因子每个 XQMX 系数都是i64其上每个算术运算都是精确的——Quadratic Models 与 Energy and Precision 都建立在这个事实上。现实问题数据很少以整数到达价格、千克重量、分数收益。把每个分数值乘以足够大的因子使结果恰为整数用该整数作系数。因子必须对问题中的每个值都足够大而不只是看起来整齐的那些。一个四物品背包重量精确到四分之一千克、价值精确到分weights_f [2.50, 3.75, 1.25, 4.00] values_f [10.20, 15.75, 8.40, 20.00] capacity_f 7.50 def scale(values, factor): scaled [round(v * factor) for v in values] for v, s in zip(values, scaled): assert abs(v * factor - s) 1e-9, (v, factor, s) # catch silent rounding return scaled用4缩放——对重量足够全是四分之一——在到达价值时立刻失败断言10.2 * 4 40.8不是整数舍入为41所以scale()在该因子构建模型之前就抛出AssertionError: (10.2, 4, 41)价值是分精度但不全是四分之一10.20、8.40不是0.25的倍数所以4不够。这里对每个值都精确的最小因子是每个值小数分母的最小公倍数——20这些数都是0.05的倍数而不是两位小数直觉会伸手去拿的天真100from fractions import Fraction from math import lcm denoms [Fraction(v).limit_denominator(10000).denominator for v in weights_f values_f [capacity_f]] lcm(*denoms) # 20在factor 20下weights [50, 75, 25, 80]、values [204, 315, 168, 400]、capacity 150。通过xqcp构建Selection Under Budget 覆盖的同一SLACKEQUALITY形态罚权重4的推导见下文系数幅度小节编译、在 Rust VM 上运行编码器、用SolverDWaveCPU求解、把解码后的总量除以缩放因子selection[1, 1, 1, 0] total_weight7.5 total_value34.35 capacity_okTrue energy-906877.5和34.35是精确的——不是舍回来的而是整数和除以20无余数因为20是对每个输入都精确的选定值。xquad verify接受编译好的编码器43 条指令且同样的选择{0, 1, 2}在五个不同求解器 seed 上返回一致。缩放的成本slack 位与系数幅度SLACK的位数是 (S \lfloor \log_2(\text{capacity}) \rfloor 1)——对容量取对数但重要的是缩放后的容量。同一实例的天真factor 100缩放需要10个 slack 位capacity 750最小精确的factor 20需要8个capacity 150。缩放比数据所需的精细五倍在这里多花两个变量且差距随容量增长而扩大——不必要的过大缩放因子并不免费即使在其对系数幅度的影响之前。罚权重会乘以每个约束系数所以缩放因子与罚项会复合。用 Constraints 作为兜底给出的宽松安全罚项——线性系数绝对值之和加一对上述数值为1088因为规则是罚项大于该和——作用于factor 20模型loose_penalty1088: max |coefficient| 23,953,408 fits MAX_NATURAL_COEFFICIENT (2,147,483): FalseQuip Network 直接从xqsa.quip.codec确认精确边界from xqsa.quip.codec import MILLI_SCALE, MAX_NATURAL_COEFFICIENT print(MILLI_SCALE, MAX_NATURAL_COEFFICIENT) # 1000 2147483宽松边界自身是安全的在此缩放因子下却使SolverQuip的毫尺度i32编码溢出十倍以上。按 Constraints 文档 枚举这个特定实例——十六个子集最紧违例者{0, 2, 3}重量155、价值差距85对超额5——给出紧阈值85 / 5^2 3.4所以最小的安全整数罚项是4而非1088tight penalty4: max |coefficient| 88,064 fits MAX_NATURAL_COEFFICIENT: True4越过紧阈值求解器仍返回正确的最优值{0, 1, 2}五个 seed 一致——宽松与紧罚项之间 272 倍的差距正是区分溢出SolverQuip编码与从容适配的分水岭。这是 Constraints 关于宽松边界之宽松的警告被一个足够大的缩放因子具体化一个在自然尺度上仅仅安全的边界一旦缩放因子乘过它触碰的每个系数就可能成为决定因素。同样的系数增长对metal-gpu的 float32 搜索与cuda-gpu的 float64 搜索影响不同正如 Energy and Precision 对未缩放模型所覆盖的。在上述宽松罚项下所得求解能量-24,480,687量级 (10^7)对1的差值超出 float32 大约七位十进制数字的分辨率但对100的差值不超出import numpy as np e -24480687 # this models actual solved energy at the loose penalty np.float32(e) ! np.float32(e - 1) # False -- the 1-unit difference is lost np.float32(e) ! np.float32(e - 100) # True -- a 100-unit difference still resolves按自然尺度推理看似安全的缩放选择可能让metal-gpu损失cuda-gpu在完全相同的模型上保有的分辨率——请对照目标后端检查你的因子实际产生的系数幅度而不仅仅是对照输入数据的精度。变量成本与失败模式变量成本公式与 Selection Under Budget 相同——(S \lfloor \log_2(\text{scaled capacity}) \rfloor 1) 个 slack 位叠在物品数上——但输入是缩放后容量而非原始容量。失败模式是按这个看起来有几位小数而非每个值分母的真实最小公倍数选择缩放因子要么静默丢失精度因子太小本演示只因断言舍入精确才捕获要么毫无理由地花费变量和系数余量因子大于任何值所需即上面100对20的情形。从问题使用的每个值一次性计算最小精确因子而不是猜一个整齐的数字。本章的边界以上页面都不重新推导 one-hot、EXCLUDE或EQUALITY约束展开成线性与二次系数的表格——那张表在 High-Level Constraints 中已经写就本章链接过去而不重复。本章关心的是识别新问题需要哪个指令族、以及选定后要付出什么代价而不是指令本身。选形态、看成本、查失败模式然后回到 Modelling 章节 的约束与罚权重页面对齐具体系数——这就是 XQuad Cookbook 给出一份新问题的完整工作流。赞分享【免费下载链接】xquadA rust implementation of the Quip Networks quantum virtual machine.项目地址https://gitcode.com/gh_mirrors/xq/xquad点击查看免费下载相关推荐Wand-Enhancer完整指南免费解锁Wand专业版体验三步搞定Wand Enhancer完整指南免费解锁Wand专业版体验三步搞定 Wand原WeMod免费版每天只有2小时额度超时弹窗、配置清零、AI功能锁在订阅桌面应用前端Product-Manager-Skills 的 roadmap-planning 实战指南从五阶段工作流到可复用的路线图示例解析Product Manager Skills 的 roadmap planning 实战指南从五阶段工作流到可复用的路线图示例解析 导读 本文围绕开源仓库 PAI 技能AI 插件Sails Helpers 实战指南从 getRecentUsers() 示例掌握可复用代码封装Sails Helpers 实战指南从 getRecentUsers 示例掌握可复用代码封装 导读 本篇以 Sails 官方示例 getRecentUsers后端上一篇Hextra主题常见问题解答新手必知的15个技巧下一篇YaneuraOu开源项目教程创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考