概率计算机突破量子优势边界：三维自旋玻璃优化问题的经典解决方案

《Nature Communications》：Pushing the boundary of quantum advantage in hard combinatorial optimization with probabilistic computers

本研究针对量子计算机在硬组合优化问题中的实际优势尚不明确的问题，开展了基于概率计算机（p-computer）的蒙特卡洛算法研究。通过离散时间模拟量子退火（DT-SQA）和自适应并行回火（APT）算法，在三维伊辛自旋玻璃问题上实现了优于量子退火器的缩放性能。研究证实，概率计算机通过硬件协同设计可实现大规模并行计算，为优化问题提供了可扩展的经典解决方案，为评估量子优势建立了严谨的基线。

　　

近年来，专用基准测试上的演示重新点燃了人们对量子计算机的热情，但量子计算机在现实问题中的优势仍然是一个悬而未决的问题。量子退火器等专用量子设备虽然在理论上具有潜力，但其性能往往受到硬件限制（如有限的量子比特连通性和退相干时间）的制约。与此同时，经典算法如模拟量子退火（SQA）和并行回火（PT）一直在不断改进，挑战着量子设备的所谓“量子优势”。在这一背景下，概率计算机（p-computer）作为一种新兴的经典计算范式，通过硬件与算法的协同设计，为解决硬组合优化问题提供了一条可扩展的路径。

本研究聚焦于三维爱德华-安德森自旋玻璃这一经典难题，比较了两种先进的概率算法——离散时间模拟量子退火（DT-SQA）和自适应并行回火（APT）——与领先的量子退火器的性能。研究人员设计了一个混合计算平台，将通用计算机与专门用于快速蒙特卡洛采样的概率计算机相结合。概率计算机已在中央处理器（CPU）、图形处理器（GPU）、现场可编程门阵列（FPGA）以及互连的FPGA等多种硬件上实现。其中，结合了随机磁性隧道结（sMTJ）技术的专用芯片在能效和性能方面最具潜力。

为了评估算法性能，研究团队以残差能量（ρ_E^f）作为解决方案质量的主要度量标准，其定义为退火时间（t_a）的函数：ρ_E^f = (E(t_a) - E₀)/n，其中E₀是哈密顿量H的基态能量，E(t_a)是退火结束时测得的能量，n是系统中的自旋数。残差能量随退火时间呈幂律衰减：ρ_E^f ∝ t_a^-κ_f，其中κ_f是拟合的缩放指数。

关键技术方法

研究主要采用了离散时间模拟量子退火（DT-SQA）和自适应并行回火（APT）两种算法，并在CPU和FPGA平台上实现。DT-SQA通过铃木-特罗特变换将d维量子系统映射到(d+1)维经典系统，使用R个相互关联的特罗特副本。APT则利用多个副本在不同温度下并行运行，并通过周期性状态交换和等能团簇移动（ICM）来逃离局部极小值。通过极端值理论（EVT）分析DT-SQA的缩放行为，并利用有限尺寸缩放分析验证APT结果的普适性。硬件方面，利用FPGA的 massive parallelism（大规模并行性）实现自旋的恒定时间更新，并基于7纳米工艺进行了专用集成电路（ASIC）的物理设计可行性分析。

DT-SQA的残差能量缩放分析

研究人员首先评估了DT-SQA的缩放性能，通过改变特罗特副本数R来观察残差能量随退火时间的变化。

结果表明，斜率κ_f的绝对值随着R的增加而增加。当R=2850时，DT-SQA的缩放指数（κ_f=0.805）与量子退火器相当甚至更优。这种缩放行为的改善可以通过修正的极端值理论（EVT）来解释，该理论考虑了副本之间的相关性。研究人员将R个特罗特副本划分为P_eff个有效块，其中块内的副本是相关的，但与其他块基本无关，从而将块视为独立的运行。提取的有效块大小与测量的副本间相关性很好地吻合，支持了修正的EVT分析。

与自适应并行回火（APT）的比较

接下来，研究将DT-SQA与强大的自适应并行回火（APT）算法进行了比较。APT同样利用问题的副本，但这些副本在不同温度下并行运行，相邻副本根据Metropolis准则定期交换状态，使高温副本能够广泛探索能量景观，而低温副本则保留最优状态。自适应变体进一步通过预处理问题图来均衡副本间的交换概率，避免瓶颈。此外，研究还引入了等能团簇移动（ICM）来增强APT，这是一种在标准APT算法之上添加的非局部蒙特卡洛交换。

结果显示，虽然DT-SQA在早期表现出更好的斜率，但在较长的退火时间后会进入一个平台期，残差能量停滞不前。相比之下，带有ICM的APT表现出两个不同的区域：一个初始较缓的斜率，随后是一个更陡的斜率。有限尺寸缩放分析证实，对于不同的尺寸L，残差能量曲线会塌缩到一条单一的普适曲线上，这种较晚的弯曲似乎是APT的一个普适特征。这使得APT特别适合大规模优化任务。

基于架构的缩放改进和大规模并行性

除了缩放改进，优化问题的一个关键指标是在给定时间内实现尽可能低的残差能量。研究评估了CPU、FPGA和基于sMTJ的概率计算机实现的相对性能，突出了架构优势。

概率计算机架构的一个关键特征是能够以恒定时间概率性地更新系统中的所有自旋。在稀疏问题中，概率计算机架构利用物理并行节点同时更新大的独立集合。分析表明，与CPU相比，概率计算机具有O(n)的缩放优势。此外，基于sMTJ的设备假设在具有100万个p-bit的MRAM芯片中实现纳秒级的波动，可以在前置因子方面实现额外的1到3个数量级的改进。所提出的架构也非常节能，比最先进的GPU和TPU少消耗2到5个数量级的每翻转能量。

单个概率计算芯片的物理设计可行性

研究还评估了为稀疏、结构化问题上的基于副本的算法设计定制专用集成电路（ASIC）的可行性。一个将所有副本集成在芯片上的单片芯片将消除制约当前FPGA实现的片外通信开销。基于7纳米工艺的 rigorous, bottom-up design flow（严谨的自下而上设计流程）分析表明，芯片面积要求随p-bit数量呈近似线性增长。根据这种缩放比例，预计使用7纳米技术，单个芯片可以容纳约766万个p-bit（对应2850个副本），芯片面积为28.61 x 28.61 mm2，这在当前制造技术的能力范围内。

研究结论与意义

本研究证明了概率计算与p-bit为解决三维伊辛自旋玻璃问题提供了一条实用且可扩展的途径。通过DT-SQA算法，利用大量副本可以显著改善缩放指数，这一现象可以通过极端值理论很好地解释。而像APT这样辅以非局部移动的强大算法，则可以进一步改善缩放和求解时间。有限尺寸缩放分析揭示了APT残差能量曲线的普适塌缩，强调了研究结果的普遍性。这使得APT在应用于专用概率硬件时特别适合大规模优化任务。

制造技术的进步现在允许大规模副本系统实现，与软件方法相比，提供了数量级的速度提升。基于单片纳米器件的概率计算机的预测突出了一条路径，使其性能能够与当前求解器竞争并可能超越，同时所有操作都在室温下进行，没有量子比特退相干或固定连接性拓扑等特定的硬件挑战。强大的算法、可扩展的架构和新兴硬件的协同设计，为解决前所未有的规模的硬优化问题提供了一条清晰的途径。除了组合优化，概率计算机在基于能量的模型的训练和推理、贝叶斯学习以及传统求解器性能已饱和的离散空间采样等多样化应用中也具有前景。

这项发表在《Nature Communications》上的工作，为评估实际量子优势建立了一个严谨的经典基线，并将概率计算机定位为应对现实世界优化挑战的可扩展平台。