广义概率近似优化算法（PAOA）：量子优化计算的经典替代方案

《Nature Communications》：Generalized Probabilistic Approximate Optimization Algorithm

本研究针对组合优化问题中传统模拟退火算法效率受限的挑战，提出了广义概率近似优化算法（PAOA）。通过构建混合经典-概率架构，研究人员实现了参数化的快速采样策略，在FPGA硬件平台上成功解决了三维自旋玻璃问题。该算法不仅恢复了模拟退火作为特例，更在Sherrington-Kirkpatrick模型上展现出优于量子近似优化算法（QAOA）的性能，为重尾分布问题提供了自适应退火新策略，为经典优化算法的发展开辟了新方向。

　　

在组合优化和统计物理领域，探索复杂能量景观的蒙特卡洛算法一直是核心工具。经典方法如模拟退火（Simulated Annealing, SA）虽被广泛应用，但其依赖缓慢平衡过程的特点限制了在崎岖能量景观上的性能。随着量子计算的发展，量子近似优化算法（Quantum Approximate Optimization Algorithm, QAOA）为优化问题提供了新思路，但其实际优势仍不确定，且受限于当前量子设备的规模。这些挑战催生了对新型非平衡策略的需求，旨在保持算法简洁性的同时提高解的质量。

受到QAOA的启发，Weitz等人提出了一种基于低维马尔可夫转移矩阵直接参数化的经典变分协议，引入了概率近似优化算法（PAOA）的概念。在这项奠基性工作的基础上，加州大学圣巴巴拉分校和纽约大学的研究团队在《Nature Communications》上发表了题为"广义概率近似优化算法"的研究，正式提出并推广了PAOA框架。

PAOA的核心创新在于将能量景观本身视为可优化的变分对象，通过概率计算机的采样反馈动态重塑景观。该方法构建了一个双层优化循环：外层循环中经典优化器调整变分参数θ；内层循环中概率计算机从当前参数化的变分景观中采样状态。这种设计使PAOA能够发现通往解决方案的非平衡路径，摆脱了传统平衡采样的限制。

研究团队探索了多种变分ansatz（近似解）参数化策略，从单一全局退火计划到完全参数化的耦合矩阵，形成了丰富的算法谱系。特别值得注意的是，当限制于每时间步一个参数的全局退火计划时，PAOA能够自动发现类似模拟退火的结构，这表明SA可以作为变分蒙特卡洛的特殊情况被恢复。

在技术方法层面，研究主要依托概率计算（p-computing）框架，利用二进制随机单元（p-bits）网络通过异步更新进行玻尔兹曼分布采样。关键实验包括：通过多数逻辑门基准验证算法有效性；在FPGA上实现带片上退火的三维自旋玻璃优化；与QAOA在Sherrington-Kirkpatrick（SK）模型上的参数匹配对比；以及针对重尾SK模型的多元退火策略研究。研究使用了COBYLA优化算法进行参数优化，并通过大量独立MCMC运行评估性能。

PAOA框架与变分ansatz谱系

研究团队提出的PAOA框架采用混合经典-概率架构，通过迭代更新权重矩阵J和偏置向量h，利用概率计算机的反馈来近似精确马尔可夫流。如图1所示，该系统的ansatz大小M可以超过原始问题大小N，因为可能引入隐藏变量来增加表示能力。研究人员定义了四种代表性ansatz，对应不同的自由参数数量Γ：当Γ=1时，景观由每个层k的单个学习逆温度β^(k)缩放；当Γ=2时，两个独立计划分配给图的不同部分；当Γ=N时，每个节点分配局部计划β_i^(k)；当Γ=N(N-1)/2时，整个对称耦合矩阵J_ij^(k)用作变分ansatz。

多数逻辑门基准验证

为说明PAOA在精确和近似动力学下的行为，研究人员解决了涉及四节点多数逻辑门的小型优化问题。如图2所示，通过比较基于梯度的优化和使用COBYLA算法的基于MCMC的近似，发现两种方法收敛到几乎相同的最小值，证实了无导数优化可以紧密跟踪真实梯度。这一基准测试为后续大规模实验奠定了基础。

发现模拟退火行为

研究的一个关键发现是，PAOA在受限参数化下能够自动恢复模拟退火行为。如图3所示，研究人员将PAOA应用于大小为L³=6³的三维立方格子，采用最简单的Γ=1全局退火ansatz。经过优化后，PAOA consistently学会了从高温（低β）开始并逐渐冷却（增加β）的计划，尽管从平坦的β=2计划开始，却 resembling 经典SA。这一发现表明模拟退火可以作为变分蒙特卡洛的特殊情况被恢复。

FPGA实现与性能优势

为实现大规模退火计划，研究团队设计了完全在片上执行退火的p计算机架构，与早期需要片外资源进行退火的实现形成对比。FPGA采用定点算法，实例化了10个独立的L³=6³自旋玻璃图副本，每个周期支持2160个p-bit的并行更新。如表II所示，该架构在FPGA上实现了比优化CPU实现约800倍的壁钟时间减少，证明了PAOA在硬件上的高效性。

PAOA与QAOA的SK模型对比

在Sherrington-Kirkpatrick（SK）模型上的对比实验显示，PAOA在等参数条件下表现出竞争优势。如图4所示，研究人员使用双计划ansatz（恰好2p个参数）评估PAOA，与深度p的QAOA参数数量匹配。结果表明，PAOA的平均近似比 consistently 高于标准QAOA，且使用N=26训练的计划能够很好地推广到N=500的更大实例。这一发现对QAOA在此类问题上的量子优势提出了挑战。

Lévy SK模型中的多元退火

为测试PAOA是否能够自适应地利用问题结构，研究人员研究了耦合权重遵循重尾Lévy分布的变体。如图5所示，通过引入每个节点的耦合强度λ_i=∑_j|J_ij|，并将节点分为重组和轻组，PAOA自动学会了将较慢的退火计划分配给强耦合节点，重现了先前工作中手工设计的启发式方法。这一发现表明PAOA可以作为发现无序系统中新算法策略的工具。

研究结论表明，PAOA作为一个变分蒙特卡洛框架，推广了模拟退火并支持与现有Ising硬件兼容的各种参数化。通过将能量景观本身视为变分对象并通过蒙特卡洛采样的经典反馈进行更新，PAOA能够使用浅层马尔可夫链从非平衡分布中进行高效采样。

该研究的重要意义在于三个方面：首先，PAOA提供了一个严格、可扩展和高性能的变分采样基准，适用于超出当前量子设备可达范围的问题规模；其次，算法能够自动发现针对问题结构的自适应启发式策略，为优化算法的设计自动化提供了新思路；最后，FPGA实现证明了PAOA在现有硬件上的可行性，为经典优化算法在实际问题中的应用开辟了新途径。

尽管PAOA在目前测试的问题上表现出色，研究人员也明确指出，在干涉发挥明确作用的问题上（如Montanaro等人构建的合成示例），量子优势仍有望出现。这些干涉主导的机制是PAOA或任何经典采样器难以竞争的领域。然而，除非这种干涉驱动的优势在实际问题类中得到明确证明，否则QAOA不太可能产生显著的量子优势。

总体而言，这项研究为经典优化算法的发展提供了新范式，通过将变分原理与概率计算相结合，在保持算法简洁性的同时提高了解决复杂优化问题的能力。随着硬件技术的进步和算法参数的丰富，PAOA有望在组合优化、机器学习和统计物理等领域发挥重要作用。