Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

QAOA pseudo-Boltzmann states

Pablo Díez-Valle

Published May 23, 2022• 1 citation
OpenAlex

Abstract

In this letter, we provide analytical and numerical evidence that the single-layer Quantum Approximate Optimization Algorithm (QAOA) on universal Ising spin models produces thermal-like states with Gaussian perturbations. We find that these pseudo-Boltzmann states can not be efficiently simulated on classical computers according to state-of-art techniques, and we relate this distribution to the optimization potential of QAOA. Moreover, we observe that the temperature depends on a hidden universal correlation between the energy of a state and the covariance of other energy levels and the Hamming distances of the state to those energies.

Related papers

Quantum Approximate Optimization Algorithm Pseudo-Boltzmann States

Pablo Díez-Valle, Diego Porras, Juan José García‐Ripoll

In this Letter, we provide analytical and numerical evidence that the single-layer quantum approximate optimization algorithm on universal Ising spin models produces thermal-like states. We find that these pseudo-Boltzmann states can not be efficiently simulated on classical computers according to the general state-of-the-art condition that ensures rapid mixing for Ising models. Moreover, we observe that the temperature depends on a hidden universal correlation between the energy of a state and the covariance of other energy levels and the Hamming distances of the state to those energies.

arXiv:2201.03358•Physical Review Letters•Feb 2, 2023•26 citations

Connection between single-layer quantum approximate optimization algorithm interferometry and thermal distribution sampling

Pablo Díez-Valle, Diego Porras, Juan José García‐Ripoll

The quantum approximate optimization algorithm (QAOA) was originally proposed to find approximate solutions to combinatorial optimization problems on quantum computers. However, the algorithm has also attracted interest for sampling purposes since it was theoretically demonstrated under reasonable complexity assumptions that one layer of the algorithm already engineers a probability distribution beyond what can be simulated by classical computers. In this regard, a recent study has also shown that, in universal Ising models, this global probability distribution resembles pure but thermal-like distributions at a temperature that depends on the internal correlations of the spin model. In this work, through an interferometric interpretation of the algorithm, we extend the theoretical derivation of the amplitudes of the eigenstates and the Boltzmann distributions generated by a single-layer QAOA. We also review the implications of this behavior from practical and fundamental perspectives.

arXiv:2310.09172•Frontiers in Quantum Science and Technology•Feb 14, 2024•5 citations

Universal resources for quantum approximate optimization algorithm and quantum annealing

Pablo Díez-Valle, Fernando J. Gómez-Ruiz, Diego Porras +1 more

The Quantum Approximate Optimization Algorithm (QAOA) is a variational ansatz that resembles the Trotterized dynamics of a Quantum Annealing (QA) protocol. This work formalizes this connection formally and empirically, showing the angles of a multilayer QAOA circuit converge to universal QA trajectories. Furthermore, the errors in both QAOA circuits and QA paths act as thermal excitations in pseudo-Boltzmann probability distributions whose temperature decreases with the invested resource -- i.e. integrated angles or total time -- and which in QAOA also contain a higher temperature arising from the Trotterization. This also means QAOA and QA are cooling protocols and simulators of partition functions whose target temperature can be tuned by rescaling the universal trajectory. The average cooling power of both methods exhibits favorable algebraic scalings with respect to the target temperature and problem size, whereby in QAOA the coldest temperature is inversely proportional to the number of layers, $T\sim 1/p$, and to the integrated angles -- or integrated interactions in QA.

quant-pharXiv:2506.03241•Physical Review Research•Jun 5, 2025•3 citations

QAOA pseudo-Boltzmann sampling beyond the rapid-mixing regime on superconducting quantum computers

Feliks Kivelä, Pablo Díez-Valle, Juan José García‐Ripoll +1 more

Abstract The quantum approximate optimization algorithm (QAOA) is a variational quantum algorithm developed for solving combinatorial optimization problems. It has also been shown to generate pseudo-Boltzmann distributions, with potential applications in various fields of computer science and computational physics. In this work, we build upon previous theoretical results and demonstrate pseudo-Boltzmann sampling with single-layer QAOA on real superconducting quantum computers. We show that the pseudo-Boltzmann distribution and the ability to adjust its effective temperature survive the accumulated errors of a real, noisy superconducting quantum processor. On an IBM processor, we are able to reach temperatures below a classical minimum-temperature boundary that guarantees the rapid mixing of single-site Glauber dynamics. We also run controlled simulations of QAOA with various noise models to characterize how increasing error rates raises the effective temperature of the distribution and limits the lowest accessible temperature.

Quantum Science and Technology•Sep 17, 2026•0 citations

Expectation values from the single-layer quantum approximate optimization algorithm on Ising problems

Asier Ozaeta, Wim van Dam, Peter L. McMahon

Abstract We report on the energy-expectation-value landscapes produced by the single-layer ( p = 1) quantum approximate optimization algorithm ( QAOA ) when being used to solve Ising problems. The landscapes are obtained using an analytical formula that we derive. The formula allows us to predict the landscape for any given Ising problem instance and consequently predict the optimal QAOA parameters for heuristically solving that instance using the single-layer QAOA . We have validated our analytical formula by showing that it accurately reproduces the landscapes published in recent experimental reports. We then applied our methods to address the question: how well is the single-layer QAOA able to solve large benchmark problem instances? We used our analytical formula to calculate the optimal energy-expectation values for benchmark M AX -C UT problems containing up to 7000 vertices and 41 459 edges. We also calculated the optimal energy expectations for general Ising problems with up to 100 000 vertices and 150 000 edges. Our results provide an estimate for how well the single-layer QAOA may work when run on a quantum computer with thousands of qubits. In addition to providing performance estimates when optimal angles are used, we are able to use our analytical results to investigate the difficulties one may encounter when running the QAOA in practice for different classes of Ising instances. We find that depending on the parameters of the Ising Hamiltonian, the expectation-value landscapes can be rather complex, with sharp features that necessitate highly accurate rotation gates in order for the QAOA to be run optimally on quantum hardware. We also present analytical results that explain some of the qualitative landscape features that are observed numerically.

arXiv:2012.03421•Quantum Science and Technology•Sep 7, 2022•39 citations

Approximate Boltzmann distributions in quantum approximate optimization

Phillip C. Lotshaw, George Siopsis, James Ostrowski +4 more

Approaches to compute or estimate the output probability distributions from the quantum approximate optimization algorithm (QAOA) are needed to assess the likelihood it will obtain a quantum computational advantage. We analyze output from QAOA circuits solving 7200 random MaxCut instances, with $n=14--23$ qubits and depth parameter $p\ensuremath{\le}12$, and find that the average basis state probabilities follow approximate Boltzmann distributions: The average probabilities scale exponentially with their energy (cut value), with a peak at the optimal solution. We describe the rate of exponential scaling or effective temperature in terms of a series with a leading-order term $T\ensuremath{\sim}{C}_{\mathrm{min}}/n\sqrt{p}$, with ${C}_{\mathrm{min}}$ the optimal solution energy. Using this scaling, we generate approximate output distributions with up to 38 qubits and find these give accurate accounts of important performance metrics in cases we can simulate exactly.

arXiv:2212.01857•Physical Review A•Oct 12, 2023•18 citations
In this letter, we provide analytical and numerical evidence that the single-layer Quantum Approximate Optimization Algorithm (QAOA) on universal Ising spin models produces thermal-like states with Gaussian perturbations. We find that these pseudo-Boltzmann states can not be efficiently simulated on classical computers according to state-of-art techniques, and we relate this distribution to the optimization potential of QAOA. Moreover, we observe that the temperature depends on a hidden universal correlation between the energy of a state and the covariance of other energy levels and the Hamming distances of the state to those energies.
In this Letter, we provide analytical and numerical evidence that the single-layer quantum approximate optimization algorithm on universal Ising spin models produces thermal-like states. We find that these pseudo-Boltzmann states can not be efficiently simulated on classical computers according to the general state-of-the-art condition that ensures rapid mixing for Ising models. Moreover, we observe that the temperature depends on a hidden universal correlation between the energy of a state and the covariance of other energy levels and the Hamming distances of the state to those energies.
The quantum approximate optimization algorithm (QAOA) was originally proposed to find approximate solutions to combinatorial optimization problems on quantum computers. However, the algorithm has also attracted interest for sampling purposes since it was theoretically demonstrated under reasonable complexity assumptions that one layer of the algorithm already engineers a probability distribution beyond what can be simulated by classical computers. In this regard, a recent study has also shown that, in universal Ising models, this global probability distribution resembles pure but thermal-like distributions at a temperature that depends on the internal correlations of the spin model. In this work, through an interferometric interpretation of the algorithm, we extend the theoretical derivation of the amplitudes of the eigenstates and the Boltzmann distributions generated by a single-layer QAOA. We also review the implications of this behavior from practical and fundamental perspectives.
The Quantum Approximate Optimization Algorithm (QAOA) is a variational ansatz that resembles the Trotterized dynamics of a Quantum Annealing (QA) protocol. This work formalizes this connection formally and empirically, showing the angles of a multilayer QAOA circuit converge to universal QA trajectories. Furthermore, the errors in both QAOA circuits and QA paths act as thermal excitations in pseudo-Boltzmann probability distributions whose temperature decreases with the invested resource -- i.e. integrated angles or total time -- and which in QAOA also contain a higher temperature arising from the Trotterization. This also means QAOA and QA are cooling protocols and simulators of partition functions whose target temperature can be tuned by rescaling the universal trajectory. The average cooling power of both methods exhibits favorable algebraic scalings with respect to the target temperature and problem size, whereby in QAOA the coldest temperature is inversely proportional to the number of layers, T∼1/pT\sim 1/pT∼1/p, and to the integrated angles -- or integrated interactions in QA.
Abstract The quantum approximate optimization algorithm (QAOA) is a variational quantum algorithm developed for solving combinatorial optimization problems. It has also been shown to generate pseudo-Boltzmann distributions, with potential applications in various fields of computer science and computational physics. In this work, we build upon previous theoretical results and demonstrate pseudo-Boltzmann sampling with single-layer QAOA on real superconducting quantum computers. We show that the pseudo-Boltzmann distribution and the ability to adjust its effective temperature survive the accumulated errors of a real, noisy superconducting quantum processor. On an IBM processor, we are able to reach temperatures below a classical minimum-temperature boundary that guarantees the rapid mixing of single-site Glauber dynamics. We also run controlled simulations of QAOA with various noise models to characterize how increasing error rates raises the effective temperature of the distribution and limits the lowest accessible temperature.
Abstract We report on the energy-expectation-value landscapes produced by the single-layer ( p = 1) quantum approximate optimization algorithm ( QAOA ) when being used to solve Ising problems. The landscapes are obtained using an analytical formula that we derive. The formula allows us to predict the landscape for any given Ising problem instance and consequently predict the optimal QAOA parameters for heuristically solving that instance using the single-layer QAOA . We have validated our analytical formula by showing that it accurately reproduces the landscapes published in recent experimental reports. We then applied our methods to address the question: how well is the single-layer QAOA able to solve large benchmark problem instances? We used our analytical formula to calculate the optimal energy-expectation values for benchmark M AX -C UT problems containing up to 7000 vertices and 41 459 edges. We also calculated the optimal energy expectations for general Ising problems with up to 100 000 vertices and 150 000 edges. Our results provide an estimate for how well the single-layer QAOA may work when run on a quantum computer with thousands of qubits. In addition to providing performance estimates when optimal angles are used, we are able to use our analytical results to investigate the difficulties one may encounter when running the QAOA in practice for different classes of Ising instances. We find that depending on the parameters of the Ising Hamiltonian, the expectation-value landscapes can be rather complex, with sharp features that necessitate highly accurate rotation gates in order for the QAOA to be run optimally on quantum hardware. We also present analytical results that explain some of the qualitative landscape features that are observed numerically.
Approaches to compute or estimate the output probability distributions from the quantum approximate optimization algorithm (QAOA) are needed to assess the likelihood it will obtain a quantum computational advantage. We analyze output from QAOA circuits solving 7200 random MaxCut instances, with n=14−−23n=14--23n=14−−23 qubits and depth parameter $p\ensuremath{\le}12$, and find that the average basis state probabilities follow approximate Boltzmann distributions: The average probabilities scale exponentially with their energy (cut value), with a peak at the optimal solution. We describe the rate of exponential scaling or effective temperature in terms of a series with a leading-order term $T\ensuremath{\sim}{C}_{\mathrm{min}}/n\sqrt{p}$, with Cmin{C}_{\mathrm{min}}Cmin​ the optimal solution energy. Using this scaling, we generate approximate output distributions with up to 38 qubits and find these give accurate accounts of important performance metrics in cases we can simulate exactly.