Generalized Probabilistic Approximate Optimization Algorithm

Abstract

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.

Nature Communications (2025)

References in corpus (26)

• Solving the Quantum Many-Body Problem with Artificial Neural Networks
• Computational complexity and fundamental limitations to fermionic quantum Monte Carlo simulations
• Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices
• The Quantum Approximate Optimization Algorithm and the Sherrington-Kirkpatrick Model at Infinite Size
• Effect of barren plateaus on gradient-free optimization
• p-Bits for Probabilistic Spin Logic
• Massively Parallel Probabilistic Computing with Sparse Ising Machines
• Analysis of the infinity-replica symmetry breaking solution of the Sherrington-Kirkpatrick model
• A Comparison of Various Classical Optimizers for a Variational Quantum Linear Solver
• Comparing Monte Carlo methods for finding ground states of Ising spin glasses: population annealing, simulated annealing and parallel tempering
• Adiabatic Spectroscopy and a Variational Quantum Adiabatic Algorithm
• Quantum approximate optimization via learning-based adaptive optimization
• An Expressive Ansatz for Low-Depth Quantum Approximate Optimisation
• All-to-all reconfigurability with sparse and higher-order Ising machines
• Designing Quantum Annealing Schedules using Bayesian Optimization
• Fast Simulation of High-Depth QAOA Circuits
• Extending relax-and-round combinatorial optimization solvers with quantum correlations
• Low-depth Clifford circuits approximately solve MaxCut
• Emulating Quantum Interference with Generalized Ising Machines
• Message Passing Variational Autoregressive Network for Solving Intractable Ising Models
• Optimal schedules for annealing algorithms
• Ground States of the Sherrington-Kirkpatrick Spin Glass with Levy Bonds
• Machine Learning Quantum Systems with Magnetic p-bits
• Quantum speedups in solving near-symmetric optimization problems by low-depth QAOA
• Sub-universal variational circuits for combinatorial optimization problems
• Quantum Approximate Optimization Algorithm in Finite Size and Large Depth and Equivalence to Quantum Annealing