当前位置：首页 > news >正文

量子退火与经典优化算法性能对比研究

news 2026/5/23 1:28:32

1. 量子退火与经典优化算法的性能对比研究

在计算科学领域，量子计算一直被视为可能带来革命性突破的技术。其中，量子退火（Quantum Annealing）作为一种专门用于解决组合优化问题的方法，近年来备受关注。然而，关于量子退火是否真正具备相对于经典算法的优势，学术界一直存在争议。

最近发表在arXiv上的研究（arXiv:2505.22514v1）对这一争议提供了新的见解。该研究团队来自波兰多个研究机构，包括弗罗茨瓦夫理工大学和波兰科学院等。他们通过系统性的对比实验，重新评估了量子退火在解决二次无约束二进制优化（QUBO）问题时的性能表现。

1.1 研究背景与核心问题

量子优势（Quantum Advantage）是指量子计算机在特定问题上能够超越经典计算机的性能。这种优势可能体现在计算复杂度、运行时间或能耗等方面。在近似优化领域，特别是QUBO问题的求解上，量子退火曾被报道具有缩放优势（Scaling Advantage）。

然而，这一结论高度依赖于所选择的经典参考算法。早期研究中，量子退火被拿来与并行回火结合等能团簇移动（PT-ICM）算法进行比较，并显示出优势。但问题在于：这种优势是否真实存在？还是仅仅因为选择了不够优化的经典算法作为基准？

1.2 研究方法与创新点

研究团队采用了模拟分岔机（Simulated Bifurcation Machine，SBM）作为新的经典参考算法。SBM是一种基于非线性哈密顿动力学（Nonlinear Hamiltonian Dynamics）的启发式方法，通过利用混沌行为（Chaotic Behavior）而非传统的热涨落来实现优化。

SBM具有三个核心优势：

运行时效率高
天生具备并行性
特别适合现代GPU计算平台

研究团队将SBM与量子退火（使用D-Wave设备）在相同的QUBO问题实例上进行了对比。这些实例来自哈佛Dataverse，是基于D-Wave Advantage 4.1量子处理单元（QPU）的逻辑量子纠错（QAC）图拓扑结构生成的随机问题。

1.3 关键发现与结论

研究得出了几个重要结论：

缩放性能相当或更优：SBM展现出与量子退火相当甚至更优的缩放性能，有效地缩小了先前报道的量子-经典性能差距。
小规模问题的局限性：研究发现，早期研究中分析的小规模问题（N≈1.3×10³）对于推断渐近缩放行为是不够的，因为它们对运行时间和硬件特定因素过于敏感。
大规模实验验证：通过将基准测试扩展到更大的实例（N≈4×10⁴），远超出当前量子退火器的能力范围，研究建立了更强的经典缩放行为。
测量方法的影响：研究强调了测量方法对结果的影响。量子退火的"退火时间"是一个预设参数，而SBM的GPU计算时间是可以实际测量的，这使得比较更加透明和可靠。

最终，研究得出结论：在当前这一代量子退火器上，不太可能在操作上有意义的条件下展示出在离散近似优化中的真正优势。

2. 技术细节解析

2.1 模拟分岔机（SBM）算法原理

SBM算法受到量子绝热计算的启发，属于基于非线性动力系统的算法家族。它通过以下微分方程描述：

˙q_i = a₀p_i ˙p_i = -[a₀ - a(t)] q_i + c₀(∑J_{ij}f(q_j) + h_i)

其中f(x)采用了三元离散化方案：

f(x) = { 0 (|x| ≤ Δ(t)), sign(x) (|x| > Δ(t)) }

Δ(t) = 0.7 t/T是一个时间依赖的阈值，T是演化的总时间。

该系统的非线性主要来源于位于|q_i|=1处的完全非弹性壁。当|q_i|>1时，q_i被替换为sign(q_i)，并且p_i被设为0。

2.2 实验设计与评估指标

研究采用了"时间到ε"（Time-to-epsilon，TTε）作为主要评估指标，定义为：

TTε = t_f · log(1 - 0.99)/log(1 - p_{E≤E0+ε|E0|})

其中：

t_f是生成样本所花费的时间
p_{E≤E0+ε|E0|}是找到能量在真实基态能量E0的ε范围内的解的概率

对于每个实例，研究人员计算了100次独立运行的平均运行时间t_f和概率p_{E≤E0+ε|E0|}，然后对所有固定大小N的实例取TTε的中值[TTε]_{Med}。

2.3 参数优化与调整

在SBM实现中，有三个关键超参数需要优化：

时间步长Δt
步数N_s（T = N_sΔt）
副本数N_r

研究发现：

对于小规模实例，能量级间距相对较大，因此可以使用较小的N_s，同时增加N_r以提高找到ε范围内解的概率。
随着实例规模的增大，需要增加N_s以确保哈密顿量缓慢变化，相应地减少N_r以平衡运行时间和解的质量。

3. 结果分析与讨论

3.1 性能对比结果

图1展示了不同ε值下[TTε]_{Med}随问题规模N的缩放情况。结果显示：

对于所有ε值，基于GPU的SBM要么优于，要么匹配基于CPU的PT-ICM和基于D-Wave的U3及QAC方法的性能。
当仅考虑纯GPU计算时间t_{GPU}^f（类似于退火时间τ）时，SBM的性能进一步改善，完全消除了量子解法相对于经典解法的优势。

3.2 缩放指数分析

图2总结了不同解法和ε值下的缩放指数α。关键发现包括：

对于Ng=1和t_{tot}^f（包括所有开销），SBM的缩放指数α小于或等于（在两倍标准偏差内）其他方法的表现，特别是性能最好的QAC方法。
使用Ng=4个GPU时，尽管多GPU实现带来了额外的开销，但缩放性能有所改善，这突显了SBM算法的一个优势——可以通过增加GPU数量来提高性能，而无需进行硬件升级。