# Generalized Probabilistic Approximate Optimization Algorithm

arXiv: https://arxiv.org/abs/2507.07420 · HTML: https://mlsanity.com/paper/2507.07420/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 48 references that are in the map.
- First posted on arXiv 10 Jul 2025.

## Builds on (most cited first, 12 of 12)

- [Effect of barren plateaus on gradient-free optimization](https://mlsanity.com/paper/2011.12245/) (2020)
- [Massively Parallel Probabilistic Computing with Sparse Ising Machines](https://mlsanity.com/paper/2110.02481/) (2021)
- [Scrambled Linear Pseudorandom Number Generators](https://mlsanity.com/paper/1805.01407/) (2018)
- [All-to-all reconfigurability with sparse and higher-order Ising machines](https://mlsanity.com/paper/2312.08748/) (2023)
- [The Quantum Approximate Optimization Algorithm at High Depth for MaxCut on Large-Girth Regular Graphs and the Sherrington-Kirkpatrick Model](https://mlsanity.com/paper/2110.14206/) (2021)
- [Nonequilibrium Monte Carlo for unfreezing variables in hard combinatorial optimization](https://mlsanity.com/paper/2111.13628/) (2021)
- [Fast Simulation of High-Depth QAOA Circuits](https://mlsanity.com/paper/2309.04841/) (2023)
- [Message Passing Variational Autoregressive Network for Solving Intractable Ising Models](https://mlsanity.com/paper/2404.06225/) (2024)
- [Quantum approximate optimization via learning-based adaptive optimization](https://mlsanity.com/paper/2303.14877/) (2023)
- [Sub-universal variational circuits for combinatorial optimization problems](https://mlsanity.com/paper/2308.14981/) (2023)
- [Machine Learning Quantum Systems with Magnetic p-bits](https://mlsanity.com/paper/2310.06679/) (2023)
- [Quantum speedups in solving near-symmetric optimization problems by low-depth QAOA](https://mlsanity.com/paper/2411.04979/) (2024)

## Built on by (most cited first, 1 of 1)

- [Probabilistic Algorithms for Ising Machines from Optimization to Generative AI](https://mlsanity.com/paper/2610.03972/) (2026)

## Abstract (arXiv)

We introduce a generalized textitProbabilistic Approximate Optimization Algorithm (PAOA), a classical variational Monte Carlo framework that extends and formalizes prior work by Weitz textitet al.~citeCombes2023, 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'evy.