PAOA通过随机采样优化伊辛模型，比传统方法更快更准。
Generalized Probabilistic Approximate Optimization Algorithm
- 基于独立采样调整耦合参数，无需梯度即可迭代优化
- 在26自旋的SK模型上性能优于QAOA，在重尾问题上超越退火法
- 适用于现成伊辛机和概率计算机，可扩展至多温调控优化
我们提出广义的随机近似优化算法（PAOA），这是一种经典变分蒙特卡洛框架，扩展并形式化了Weitz等人先前的工作，可在现有伊辛机和概率计算机上实现参数化、快速采样。PAOA通过独立样本的成本评估，迭代调整二元随机单元网络的耦合参数。我们建立了无导数更新与全马尔可夫流梯度之间的直接对应关系，证明了PAOA具有严谨的变分结构。受限参数化下的模拟退火成为其极限情形，我们在基于FPGA的概率计算机上实现了该机制，并在芯片内完成退火以求解大规模三维自旋玻璃问题。在参数匹配的26自旋谢林顿-柯克帕特里克（Sherrington-Kirkpatrick, SK）模型上，与QAOA对比显示PAOA性能更优。我们进一步表明，PAOA通过优化多个温度曲线自然扩展了模拟退火，在如SK-Lévy等重尾问题上表现优于传统退火法。
原文摘要 · Abstract (English)
We introduce a generalized \textit{Probabilistic Approximate Optimization Algorithm (PAOA)}, a classical variational Monte Carlo framework that extends and formalizes prior work by Weitz \textit{et al.}~\cite{Combes_2023}, enabling parameterized and fast sampling on present-day Ising machines and probabilistic computers. PAOA operates by iteratively modifying the couplings of a network of binary stochastic units, guided by cost evaluations from independent samples. We establish a direct correspondence between derivative-free updates and the gradient of the full Markov flow over the exponentially large state space, showing that PAOA admits a principled variational formulation. Simulated annealing emerges as a limiting case under constrained parameterizations, and we implement this regime on an FPGA-based probabilistic computer with on-chip annealing to solve large 3D spin-glass problems. Benchmarking PAOA against QAOA on the canonical 26-spin Sherrington-Kirkpatrick model with matched parameters reveals superior performance for PAOA. We show that PAOA naturally extends simulated annealing by optimizing multiple temperature profiles, leading to improved performance over SA on heavy-tailed problems such as SK-Lévy.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。