← Back to Research

Generalized Probabilistic Approximate Optimization Algorithm

Abdelrahman S. Abdelrahman1, Shuvro Chowdhury1, Flaviano Morone2, Kerem Y. Camsari1

  1. Department of Electrical and Computer Engineering, University of California, Santa Barbara, CA, USA
  2. Center for Quantum Phenomena, Department of Physics, New York University, New York, NY, USA

Nature Communications · 2026

A variational Monte Carlo framework that learns stochastic dynamics and connects them to probabilistic hardware.

Original paper ↗ Code ↗ Slides ↗ Citation ↓

The question

Can the dynamics of a probabilistic computer become the object of learning? Generalized PAOA parameterizes the couplings, fields, and schedules of a stochastic system, then improves them using sampled costs. The figures follow that idea from its mathematical construction to benchmarks and a learned annealing principle.

Figure 1

Start with a learnable Markov flow.

A classical optimizer updates the parameters that drive a probabilistic computer. Exact probability flow provides the theoretical description; independent samples provide a practical estimate when the state space becomes too large to enumerate.

The feedback loop. The classical optimizer updates couplings and biases; the probabilistic computer returns configurations from the resulting dynamics. The cost is evaluated from those samples, so the learned object is a search procedure rather than a single candidate solution.

Figure 1: Start with a learnable Markov flow.
From the paper, p. 2.
Figure 2

Check the theory on a majority gate.

A four-node majority gate makes the target distribution small enough to inspect directly. Analytical and sample-based optimization reach matching outcomes, connecting the variational formulation to the sampling procedure used in larger systems.

Panels (a) and (b). The four-node majority gate provides a small problem with eight valid input–output combinations. The loss curves compare exact-gradient training with sample-based, gradient-free optimization, so both methods can be checked against the same known target.

Panels (c) and (d). Follow the probability assigned to each state over two layers. The exact Markov calculation is shown in (c); the MCMC approximation is shown in (d). Both concentrate probability on truth-table states rather than treating every configuration as equally likely.

Figure 2: Check the theory on a majority gate.
From the paper, p. 5.
Figure 3

Recover annealing on an FPGA.

The next step moves from a small truth table to a three-dimensional spin glass. Optimizing the schedule on an FPGA-based probabilistic computer shifts the energy distribution toward lower-energy solutions and recovers an annealing-like trajectory.

Panels (a) and (b). The FPGA supplies configurations while a CPU updates the annealing schedule. The energy histogram compares the same spin-glass instance before and after optimization; the useful change is a larger concentration of samples near the putative ground state.

Panel (c). Schedules at depths 5, 10, and 15 start from the same flat inverse-temperature profile. The learned profiles resemble cooling schedules. The insets compare success probabilities across repeated optimization runs, exposing variation that a single best schedule would hide.

Figure 3: Recover annealing on an FPGA.
From the paper, p. 6.
Figure 4

Compare matched parameter budgets.

PAOA and QAOA are compared on the 26-spin Sherrington–Kirkpatrick model using matched parameter counts. The energy and approximation-ratio plots show how each method changes as the number of layers increases.

Panels (a) and (b). Panel (a) compares energy at matched parameter counts on 26-spin test instances. Panel (b) summarizes approximation ratios and bootstrap confidence intervals; PAOA schedules are transferred from a separate training set without retraining.

Figure 4: Compare matched parameter budgets.
From the paper, p. 7.
Figure 5

Let different spins follow different schedules.

Heavy-tailed couplings create distinct groups of strongly and weakly connected spins. A two-schedule ansatz learns different temperature profiles for these groups, suggesting a problem-dependent annealing strategy that can be extended to larger depths.

Panels (a) and (b). Sorting the heavy-tailed couplings separates strongly and weakly connected spins. The two groups receive different learned schedules, making the comparison about the structure of the problem rather than simply increasing annealing depth.

Panels (c)–(e). The learned distinction motivates longer double schedules. The final panels compare average and instance-by-instance success against single-schedule simulated annealing, showing both aggregate performance and variation across the tested problems.

Figure 5: Let different spins follow different schedules.
From the paper, p. 8.

Putting it together

Learning a procedure for search.

The progression connects a variational description, a controlled benchmark, hardware execution, and a learned scheduling rule. PAOA provides a framework for adapting the stochastic search process to the structure of the problem.

Citation

Abdelrahman, A. S., Chowdhury, S., Morone, F., & Camsari, K. Y. Generalized Probabilistic Approximate Optimization Algorithm. Nature Communications, 17, 498 (2026). https://doi.org/10.1038/s41467-025-67187-5

BibTeX

@article{abdelrahman2026paoa,
  title = {Generalized Probabilistic Approximate Optimization Algorithm},
  author = {Abdelrahman, Abdelrahman S. and Chowdhury, Shuvro and Morone, Flaviano and Camsari, Kerem Y.},
  journal = {Nature Communications},
  volume = {17},
  pages = {498},
  year = {2026},
  doi = {10.1038/s41467-025-67187-5}
}
Publication figure