1. 项目概述：当量子退火遇上大整数分解
在密码学和计算数论领域，大整数的质因数分解一直是一个令人着迷又头疼的难题。它的计算复杂性是RSA等公钥密码体系安全性的基石——只要经典计算机无法在多项式时间内破解它，我们的数字世界就相对安全。通用数域筛法是目前最快的经典算法，但对于超过一定位数（比如2048位）的整数，其计算时间将变得天文数字般漫长。
量子计算的出现，尤其是Shor算法，理论上能在多项式时间内解决这个问题，给密码学界带来了不小的震动。然而，现实很骨感：当前的含噪声中等规模量子设备受限于量子比特数量、相干时间和错误率，距离分解有实际密码学意义的大整数还有很长的路要走。
在这种背景下，量子退火作为一种替代性的量子计算范式，进入了我们的视野。它不像通用量子计算那样追求精确的量子门操作，而是专注于解决一类特定的问题：组合优化。其核心思想是将一个优化问题映射成一个物理系统的能量最低态（基态），然后让系统通过量子隧穿等效应自然“退火”到这个状态，从而找到问题的（近似）最优解。而二次无约束二进制优化模型，则是描述这类问题的通用数学语言。
我最近深入研究了如何将大整数分解这个具体问题，巧妙地“翻译”成QUBO模型，并利用量子退火硬件来求解。这听起来像是一个纯粹的学术游戏，但背后有很强的工程动机：在NISQ时代，我们能否利用现有的、不完美的量子硬件，去解决一些有实际意义的、经典计算机处理起来非常吃力的问题？我的实践表明，通过一系列精妙的建模和优化技巧，答案是肯定的。我们不仅成功分解了高达47位的通用半素数，对于一些具有特殊结构的超大整数（如2049位且高位有大量连续零），甚至也能在短时间内找到其质因子。
这篇文章，我将以一个实践者的角度，为你拆解这整个过程。我不会过多纠结于深奥的量子力学原理，而是聚焦于如何将一个数学问题工程化为一个可执行的QUBO模型，以及在实操中会遇到哪些坑，又该如何绕过它们。无论你是对量子计算感兴趣的程序员，还是寻找优化问题新解法的算法工程师，亦或是好奇量子计算实际进展的爱好者，相信都能从中获得启发。
2. 核心思路：从乘法表到QUBO模型的工程化拆解
要把质因数分解变成一个量子退火器能“听懂”的问题，关键一步是建立正确的数学模型。我们的目标很明确：给定一个半素数 N（即两个质数 p 和 q 的乘积，N = p × q），找到 p 和 q。
2.1 基石：改进的二进制乘法表
经典思路是将分解问题转化为一个满足约束条件的乘法等式。我们假设 p 和 q 的二进制位数相同（这是RSA密钥的典型情况），例如 p = (1 p_{n-2} ... p_1 1)2，q = (1 q{n-2} ... q_1 1)_2。注意最低有效位和最高有效位都是1，因为N是奇数，其质因子也必然是奇数。
传统的“教科书式”乘法会逐位相乘然后累加，但这会产生大量的进位变量，直接建模会导致QUBO问题规模爆炸。前人（如Jiang等人）提出了一种“分块”的改进乘法表方法。其核心思想是：将多个二进制列（bit column）组合成一个“块”，在块内部进行加法和进位运算，只将块的最终进位输出到下一个块。这样，我们无需为每一个单独的加法位都引入进位变量，从而大幅减少了变量总数。
举个例子，分解 N=143 (二进制10001111)。我们可以将其乘法表按列分组，比如每两列一组。约束条件就变成了：每个块内所有部分积与输入进位的和，必须等于N在该块对应二进制位的值加上输出进位的加权和。通过将每个块的等式约束（等式左边-右边=0）转化为平方项并求和，我们就得到了一个需要最小化的目标函数。当且仅当所有等式同时满足时，目标函数值为0，此时对应的p和q的二进制位赋值就是我们要的解。
注意：这里有一个至关重要的细节——如何将等式约束转化为QUBO目标函数。QUBO的标准形式是最小化一个二次型：
f(x) = Σ_i Q_ii * x_i + Σ_{i<j} Q_ij * x_i * x_j，其中x_i是二进制变量。等式约束A = B需要被转化为(A - B)^2的形式。展开后，(A - B)^2会产生常数项、线性项和二次项，它们都能完美地嵌入QUBO矩阵Q中。如果A或B的表达式包含高于二次的项（例如两个变量的乘积再乘以第三个变量），则需要引入额外的辅助变量和惩罚项将其“降次”为二次型，这个过程会增加问题的复杂度。
2.2 我们的核心创新：五大优化策略
直接套用上述分块方法，早期工作最多只能分解21位的整数。要突破这个限制，必须进行更深度的优化。我们的研究提出了五个环环相扣的策略，它们共同作用，将可分解整数的位数提升了一个数量级。
策略A：基于部分约束的多轮退火这是最根本的思路转变。与其试图用一个庞大的QUBO问题同时解决所有约束，不如“分而治之”。我们将整个乘法表分成三个块：最低有效位块、中间块和最高有效位块。然后，果断舍弃信息最复杂、变量最多的中间块，只对首尾两个块分别构建独立的QUBO问题进行退火求解。
为什么可以这样做？因为首尾块包含了p和q的关键边界信息。LSB块直接约束了p和q的低位，MSB块约束了它们的高位。分别求解这两个块，我们可以得到两组候选解集合：一组是满足低位约束的(p_low, q_low)组合，另一组是满足高位约束的(p_high, q_high)组合。最后，我们通过经典的后处理（比如遍历组合并验证乘积是否等于N）来找出最终的质因子。这本质上是一种混合计算范式：用量子退火进行高效的、并行的候选解空间筛选，用经典计算机进行精确但搜索范围已大幅缩小的验证。
策略B & C：基于位模式分析的变量约减在分别处理首尾块时，我们发现了进一步简化问题的机会。
LSB端变量约减：在最低有效位部分，由于没有来自更低位的进位输入，部分积之和与N对应位的模式存在直接、确定的关系。通过分析N在最低几位的二进制模式（如00, 01, 10, 11），我们可以直接推导出p和q对应位之间的关系，例如
p1 = q1，或者p1 + q1 = 1。这些关系式可以直接代入QUBO模型，消除一半的变量，并且能将一些高阶项（如p1 * p2 * q1）降为简单的二次项，避免了引入辅助变量。MSB端变量约减：在最高有效位部分，我们可以利用数值范围进行推理。既然
p ≤ sqrt(N) ≤ q，我们可以通过比较极值来固定某些高位的值。例如，对于较大的因子q，我们假设其某个高位qi为0，其他未知位全为1，计算出一个最小值。如果这个最小值仍然小于sqrt(N)，那么qi必须为1，否则q就无法大于等于sqrt(N)。同理，对于较小的因子p，可以假设某位pi为1，其他未知位全为0，计算出一个最大值，如果大于sqrt(N)，则pi必须为0。通过这种方式，我们可以提前确定一批高位的二进制值，将它们从变量变为常量，极大地缩减了搜索空间。
策略D：特殊位模式的利用我们观察到，对于位宽为奇数的半素数N，如果其最高位（MSB）的下方有连续多个0，那么可以确定更多的变量。因为MSB的1只能来自p和q最高位的1相乘（1*1=1），且���有进位。如果紧接着的高位是0，那么意味着对应的部分积和进位也必须全是0，否则就会产生进位破坏这个0。这个模式可以让我们将一大片高位变量直接设为0。这对于具有特定结构的超大整数分解尤为有效。
策略E：最优块平衡在应用了B、C、D策略后，首尾两个块的变量数量可能变得非常不均衡。通常，LSB块剩余的变量远多于MSB块。这会导致退火器在两个块上的搜索难度差异巨大，影响整体效率。因此，我们设计了一个动态调整块边界的算法。它尝试将LSB块的一些列“转移”到MSB块，目标是使两个块化简后的项数（近似于变量数）尽可能平衡。平衡的问题更容易被退火器均匀地探索，从而提高找到全局解的概率。
这五大策略不是孤立的，它们构成了一个完整的优化流水线。首先通过分块（A）将问题拆解，然后分别对两个子问题应用位模式分析（B，C）和特殊模式识别（D）进行预处理和约减，最后通过平衡调整（E）来优化子问题结构，使其更适合量子退火硬件求解。
3. 实操要点：构建与求解QUBO模型的全流程
理解了核心思路，我们来看看如何一步步将其实现。整个过程可以概括为：问题建模 -> 模型简化 -> 参数调优 -> 求解验证。
3.1 从数学约束到QUBO矩阵
假设我们要分解一个n位的半素数N。首先，确定p和q的位宽（通常假设相等）。然后，根据策略A确定LSB块和MSB块的划分边界。接着，为每个块写出其算术约束等式。
以LSB块为例，其等式形如：(p1 + q1 + 2*p2 + 2*p1*q1 + ... + incoming_carry) - (value_of_N_in_this_block + 2*out_carry1 + 4*out_carry2) = 0这里，p1*q1这样的项是二次项，而2*out_carry1中的2是系数。我们将这个等式移项，得到Left - Right = 0，然后构造平方项(Left - Right)^2。
展开平方项是关键一步。你会得到三种类型的项：
- 常数项：直接加到目标函数的常数偏移中（虽然不影响优化，但记录它有助于计算最终能量值）。
- 线性项：对应QUBO矩阵Q对角线上的元素
Q_ii。 - 二次项：对应Q矩阵非对角线上的元素
Q_ij。
如果展开后出现了三次或更高次的项，比如p1 * p2 * q1，我们必须将其“降次”。常用的方法是引入一个辅助变量y = p1 * p2，并用一个惩罚项P * (p1*p2 - 2*p1*y - 2*p2*y + 3*y)来强制这个等式关系。当y = p1*p2时，惩罚项为0；否则为一个正数，增大目标函数值。惩罚系数P的选择至关重要，我们后面会详细讨论。
使用Python库（如PyQUBO）可以自动化这个过程。你只需要定义二进制变量和约束等式，库函数会帮你生成对应的QUBO矩阵（一个稀疏的二维数组或字典）。
3.2 变量约减的具体实现
在调用PyQUBO之前，我们手动实施策略B、C、D，这是提升效率的关键。
- 实施VarLSB：检查N的最低2-3位。根据其二进制模式，建立变量间的等式关系（如
p1 = q1）。在构建约束等式时，直接将q1替换为p1。这样，不仅减少了一个变量，所有包含q1的项（如p2*q1）都变成了p2*p1，这本身就是一个合法的二次项，无需引入辅助变量。 - 实施VarMSB：计算
sqrt(N)的整数部分。从最高位开始，对q的每一位，假设其为0，其他位为1，计算最小值，与sqrt(N)比较。对p的每一位，假设其为1，其他位为0，计算最大值，与sqrt(N)比较。将确定的位（qi=1或pi=0）作为已知常量代入模型。 - 实施SpePattern：检查N的位宽是否为奇数，以及MSB下方是否有连续m个0。如果是，则可以直接将p和q的最高m位变量（除了MSB本身）设为0。这些操作在预处理阶段完成，能极大简化后续生成的QUBO模型。
3.3 量子退火求解与后处理
生成QUBO矩阵后，就可以提交给量子退火求解器了。我们使用的是Fixstars Amplify AE，这是一个基于GPU的模拟量子退火引擎，支持全连接且变量规模大（>10万）。你也可以使用D-Wave的真实量子退火机，但需要注意其量子比特的连通性限制可能需要额外的“嵌入”步骤。
提交任务时，需要指定退火时间。退火时间越长，系统探索解空间越充分，找到基态的概率越高，但计算成本也越大。通常需要权衡。
退火器返回的结果不是一个单一解，而是一组低能量解（及其对应的能量值）。因为我们的QUBO模型只编码了部分约束，所以这些解只是“候选解”。对于LSB块，返回的是满足低位约束的(p_low_candidate, q_low_candidate)集合；对于MSB块，返回的是满足高位约束的(p_high_candidate, q_high_candidate)集合。
后处理是混合算法的经典部分。我们需要将两个集合的候选解组合起来。最直接的方法是穷举组合：对于LSB块的每一个候选解，与MSB块的每一个候选解拼接，形成完整的p和q的二进制表示，然后计算乘积是否等于N。由于两个集合的规模经过量子退火筛选后已经大大缩小（从2^n指数级缩小到几百或几千），这个经典验证步骤是非常快速的。在实际代码中，可以用简单的循环或向量化运算来实现。
4. 参数调优与避坑指南：让退火真正生效
理论很美好，但把模型丢给退火器常常得不到想要的结果。下面这些实操中的经验和坑，是论文里不会细说，但却决定成败的关键。
4.1 惩罚系数P：一把双刃剑
在降次过程中引入的惩罚项系数P，是调参的第一个重头戏。它的选择没有黄金法则，但有几个核心原则：
- 不能太小：如果P太小，惩罚项无力约束
y = x_i * x_j这个关系。退火器可能会大量选择y=1但x_i=0或x_j=0的无效配置，因为这样可能使目标函数的其他部分更优。结果就是，你得到的“解”根本不满足原始的乘法逻辑。 - 不能太大：如果P太大，惩罚项会在整个能量景观中占据绝对主导地位。退火器会不惜一切代价去满足
y = x_i * x_j，以至于忽略了问题本身的主要目标（即满足乘法等式）。这可能导致退火器被困在某个满足辅助约束但远离真实解的局部极小值。
如何调？我们的经验是进行扫描测试。对于一个给定的问题实例，在几个数量级的范围内（例如从10到10^6）以对数间隔尝试不同的P值。观察哪个P值能让退火器返回最多数量的低能量候选解（注意，不是能量最低的一个解，而是能量低于某个阈值的一批解）。这个“候选解数量”是一个很好的代理指标，它意味着能量景观的漏斗形状较好，退火器能相对容易地找到满足部分约束的优质区域。
在我们的实验中，曾有一个47位半素数的例子，当P值从6160调整到6170时，MSB块找到的候选解数量从87个暴增到11851个，成功率也随之大幅提升。这充分说明了P值的敏感性。
4.2 退火时间：给探索留足时间
退火时间控制了量子系统从初始状态演化到最终哈密顿量的速度。时间太短，系统可能来不及找到基态，就被“冻”在了一个亚稳态（局部最优解）。时间越长，找到全局最优解的概率理论上越高。
在我们的测试中，对于一个51位的困难实例，将退火时间从10秒逐步增加到100秒，成功率从不到20%稳步提升至接近80%，同时找到的候选解数量也显著增加。这里的启示是：如果你的退火任务很快但结果不理想，不妨尝试增加退火时间，这可能是成本最低��优化手段。当然，这增加了单次实验的成本，需要在时间预算和求解质量之间做权衡。
4.3 分块与系数权衡：信息保留的艺术
策略A中我们把中间块丢掉了，但LSB和MSB块内部还可以再分“子块”吗？我们尝试过将每个大块再切成更小的“片”，分别为每个片构建约束然后加权求和。直觉上，这应该能进一步简化每个QUBO问题。
但实验结果打了脸。对于多个大整数测试，将块切成3片相比切成2片，成功率普遍下降。原因在于信息的丢失。当两个相邻的列被分到两个不同的“片”时，它们之间的交叉项（例如xy）在分别平方求和时会丢失。原本的约束(2x + y)^2包含了4x^2 + 4xy + y^2，其中4xy是关键。如果分成x^2和y^2两个片，xy项就彻底消失了。模型丢失了变量间的重要关联信息，导致产生了大量虽然满足每个片内约束、但整体组合起来无效的伪解。
同样，为不同“片”的约束赋予不同的权重系数（σ1, σ2），理论上可以调节它们在总目标函数中的重要性。但我们发现，只要系数在一个合理的范围内（不使某一项完全主导），对最终成功率的影响并不显著。而一旦某个系数过大，导致其对应的约束完全主导了能量景观，成功率就会骤降至零。因此，一个简单稳妥的策略是：除非有明确理由，否则将所有片的权重设为1，并谨慎评估进一步细分块是否真的必要。
4.4 平台差异与实现细节
不同的量子退火平台有不同特性。D-Wave是真实的量子硬件，但其量子比特之间存在特定的连接拓扑（如Chimera, Pegasus），解决全连接的QUBO问题需要先将逻辑变量“嵌入”到物理量子比特链上，这会消耗额外的资源并可能引入误差。Amplify AE是GPU模拟器，支持全连接，易于快速原型验证，但其性能依赖于经典优化算法。
在将高阶项降次为二次项时，PyQUBO等自动化工具可能不会做出最简化的选择。例如，对于表达式p1*p2*q3*q4，如果辅助变量y1 = p1*q3和y2 = p2*q4已经存在，理论上p1*p2*q3*q4 = y1 * y2可以直接化为二次项。但工具可能会笨拙地引入新的辅助变量来处理这个四次项。检查并手动简化这些项，是提升模型效率的一个手工优化点。
5. 结果分析与性能解读
我们构建了三个逐步增强的模型进行测试：
- MulBlocks：仅使用多轮退火（策略A）。
- MulVar：在MulBlocks基础上，增加LSB和MSB变量约减（策略B和C）。
- MulVarSpeObb：整合全部五种策略。
测试从8位的简单数（如143）一直到57位甚至更大的半素数。对比基线是文献中最好的方法（SOTA）。
5.1 变量数与成功率
结果非常显著。对于19位的半素数376289，SOTA方法需要约90个变量，而我们的MulBlocks仅需19个，MulVar仅需12个，MulVarSpeObb仅需11个。变量数量的直接减少，直接映射到搜索空间的指数级缩小。
在成功率上，SOTA方法在20位以后急剧下降，到26位时已几乎无法分解。而我们的MulBlocks模型可以稳定分解40位以内的所有测试用例（成功率100%），MulVar将这一界限提升到了47位。对于具有特殊奇位宽和连续零模式的超大整数，MulVarSpeObb模型甚至成功分解了2049位的半素数（尽管这个数有特殊结构）。
5.2 候选解空间与验证时间
一个有趣的现象是，量子退火后得到的候选解数量，并不是穷尽整个块的所有可能性。例如，一个包含10个变量的LSB块，全空间是2^10=1024种组合，但退火后可能只返回几十或几百个低能量候选解。这说明退火过程有效地聚焦到了有希望的搜索区域。
验证时间与候选解数量的乘积成正比。由于两个块的候选解数量通常都被压缩到几百到几千的量级，总的验证组合数在百万级别以下，在现代CPU上只需毫秒到秒级即可完成。整个流程的耗时主要取决于退火时间（固定，如10秒/块），而不是经典验证部分。
5.3 对极端案例的洞察
MulVarSpeObb在分解2049位半素数时表现出了强大威力，但前提是该数满足“奇位宽”且“MSB下方有大量连续0”。这揭示了该方法的一个本质：它非常善于利用问题的结构性先验知识。当这种结构存在时，MSB端的大量变量被直接确定，问题复杂度断崖式下降。
这也指出了当前方法的局限性：对于不具备这种特殊结构的、随机生成的、位宽为偶数的大整数，其性能会大打折扣。这更像是一种“特化武器”，而非“通用武器”。然而，从工程角度看，这依然极具价值。它证明了通过精心设计的预处理和建模，可以将一个看似不可能的大问题，化简到现有量子退火硬件能够处理的范围。
6. 总结与展望：一种务实的混合量子计算范式
回顾整个工作，我们并没有发明一种能破解RSA的“银弹”。但我们展示了一条切实可行的路径：在NISQ时代，通过混合经典-量子算法，利用量子退火处理高度结构化组合优化问题的子模块，从而扩展经典算法的能力边界。
这项工作的价值不在于分解了47位或2049位的整数——这些用经典计算机也能做到。其价值在于方法论上的验证：
- 模型简化的重要性：通过数学洞察（变量约减、模式识别）对问题进行预处理，其效果可能比单纯等待硬件升级更显著。
- 混合架构的威力：让量子处理器做它擅长的事（快速搜索离散空间），让经典处理器做它擅长的事（精确计算和验证），这种分工协作是现阶段最务实的量子计算应用模式。
- 参数调优的工程性：量子算法的性能极度依赖于参数（如惩罚系数、退火时间）。建立一个系统的参数调优流程，与算法设计本身同等重要。
对于未来，我认为有几个方向值得探索：
- 自动化参数调优：基于贝叶斯优化或机器学习，为不同规模、不同结构的QUBO问题自动寻找近优的惩罚系数和退火参数。
- 更通用的结构挖掘：除了MSB连续零，是否还有其他常见的整数位模式可以利用？能否将这种基于模式的分析扩展到更一般的偶数位宽整数？
- 与经典算法的更深融合：能否将量子退火产生的候选解，作为经典启发式算法（如Pollard's Rho）的优质初始点，进一步加速求解？
最后，我想分享一点最深的体会：在量子计算应用的早期，放弃“用量子算法完整解决一个经典难题”的执念，转而追求“用量子组件优化一个经典流程中的瓶颈步骤”，往往是更易产出成果的思路。量子退火与QUBO模型为我们提供了一个强大的组合优化工具箱，而如何将一个实际问题精巧地装进这个工具箱，才是真正的挑战与乐趣所在。这项工作是一个具体的例子，希望它能启发你在自己的领域找到那个合适的“问题”和“装法”。
