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

PRX Quantum

Mean-Field Approximate Optimization Algorithm

Aditi Misra-Spieldenner, Tim Bode, Peter Schuhmacher, Tobias Stollenwerk, Dmitry Bagrets, Frank K. Wilhelm

Published Sep 12, 2023• 22 citations
Publisher

Abstract

The quantum approximate optimization algorithm (QAOA) is suggested as a promising application on early quantum computers.Here a quantum-inspired classical algorithm, the mean-field approximate optimization algorithm (mean-field AOA), is developed by replacement of the quantum evolution of the QAOA with classical spin dynamics through the mean-field approximation.Because of the alternating structure of the QAOA, this classical dynamics can be found exactly for any number of QAOA layers.We benchmark its performance against the QAOA on the Sherrington-Kirkpatrick model and the partition problem, and find that the mean-field AOA outperforms the QAOA in both cases for most instances.Our algorithm can thus serve as a tool to delineate optimization problems that can be solved classically from those that cannot, i.e., we believe that it will help to identify instances where a true quantum advantage can be expected from the QAOA.To quantify quantum fluctuations around the mean-field trajectories, we solve an effective scattering problem in time, which is characterized by a spectrum of time-dependent Lyapunov exponents.These provide an indicator for the hardness of a given optimization problem relative to the mean-field AOA.

DOI
10.1103/prxquantum.4.030335

Related papers

Mean-Field Approximate Optimization Algorithm

Aditi Misra-Spieldenner, Tim Bode, Schuhmacher, Peter K. +3 more

The Quantum Approximate Optimization Algorithm (QAOA) is suggested as a promising application on early quantum computers. Here, a quantum-inspired classical algorithm, the mean-field Approximate Optimization Algorithm (mean-field AOA), is developed by replacing the quantum evolution of the QAOA with classical spin dynamics through the mean-field approximation. Due to the alternating structure of the QAOA, this classical dynamics can be found exactly for any number of QAOA layers. We benchmark its performance against the QAOA on the Sherrington-Kirkpatrick (SK) model and the partition problem, and find that the mean-field AOA outperforms the QAOA in both cases for most instances. Our algorithm can thus serve as a tool to delineate optimization problems that can be solved classically from those that cannot, i.e. we believe that it will help to identify instances where a true quantum advantage can be expected from the QAOA. To quantify quantum fluctuations around the mean-field trajectories, we solve an effective scattering problem in time, which is characterized by a spectrum of time-dependent Lyapunov exponents. These provide an indicator for the hardness of a given optimization problem relative to the mean-field AOA.

arXiv:2303.00329•Mar 1, 2023•2 citations

The Overlap Gap Property: Separating Quantum and Quantum-Inspired Approximate Optimization Algorithms

Mark Goh, Thorge Müller

In this paper, we prove that the Mean-Field Approximate Optimization Algorithm (MF-AOA), a quantum-inspired classical algorithm of the Quantum Approximate Optimization Algorithm (QAOA), is unable to give arbitrary near optimal solution for problems exhibiting the Overlap Gap Property (OGP). We show this by relating the MF-AOA to finite-memory Approximate Message Passing (AMP) algorithms, which are known to be limited in performance by the OGP. Thus, our paper argues that problems exhibiting the OGP are one such instance where the QAOA can outperform the MF-AOA and AMP algorithms in general. We supplement this by numerically simulating the performance of the QAOA on instances of Max-$4$-XORSAT that exhibit the OGP and find that the QAOA is able to surpass the barrier, while our finite-size scaling analysis favors a super-polynomial over a polynomial depth dependence. In addition, we observe a non-differentiable point in the performance of the QAOA near by the OGP barrier, where the optimal QAOA parameters change from an adiabatic to a non-adiabatic schedule.

quant-pharXiv:2609.35131•Sep 29, 2026•0 citations

QAOA.jl: Toolkit for the Quantum and Mean-Field Approximate Optimization Algorithms

Tim Bode, Dmitry Bagrets, Aditi Misra-Spieldenner +2 more

Quantum algorithms are an area of intensive research thanks to their potential for speeding up certain specific tasks exponentially.However, for the time being, high error rates on the existing hardware realizations preclude the application of many algorithms that are based on the assumption of fault-tolerant quantum computation.On such noisy intermediatescale quantum (NISQ) devices (Preskill, 2018), the exploration of the potential of heuristic quantum algorithms has attracted much interest.A leading candidate for solving combinatorial optimization problems is the so-called Quantum Approximate Optimization Algorithm (QAOA) (Farhi et al., 2014).QAOA.jl is a Julia package (Bezanson et al., 2017) that implements the mean-field Approximate Optimization Algorithm (mean-field AOA) (Misra-Spieldenner et al., 2023) -a quantum-inspired classical algorithm derived from the QAOA via the mean-field approximation.This novel algorithm is useful in assisting the search for quantum advantage by providing a tool to discriminate (combinatorial) optimization problems that can be solved classically from those that cannot.Note that QAOA.jl has already been used during the research leading to Misra-Spieldenner et al. (2023).

The Journal of Open Source Software•Jun 28, 2023•2 citations

The Quantum Approximate Optimization Algorithm and the Sherrington-Kirkpatrick Model at Infinite Size

Edward Farhi, Jeffrey Goldstone, Sam Gutmann +1 more

The Quantum Approximate Optimization Algorithm (QAOA) is a general-purpose algorithm for combinatorial optimization problems whose performance can only improve with the number of layers p . While QAOA holds promise as an algorithm that can be run on near-term quantum computers, its computational power has not been fully explored. In this work, we study the QAOA applied to the Sherrington-Kirkpatrick (SK) model, which can be understood as energy minimization of n spins with all-to-all random signed couplings. There is a recent classical algorithm by Montanari that, assuming a widely believed conjecture, can efficiently find an approximate solution for a typical instance of the SK model to within ( 1 − ϵ ) times the ground state energy. We hope to match its performance with the QAOA.Our main result is a novel technique that allows us to evaluate the typical-instance energy of the QAOA applied to the SK model. We produce a formula for the expected value of the energy, as a function of the 2 p QAOA parameters, in the infinite size limit that can be evaluated on a computer with O ( 16 p ) complexity. We evaluate the formula up to p = 12 , and find that the QAOA at p = 11 outperforms the standard semidefinite programming algorithm. Moreover, we show concentration: With probability tending to one as n → ∞ , measurements of the QAOA will produce strings whose energies concentrate at our calculated value. As an algorithm running on a quantum computer, there is no need to search for optimal parameters on an instance-by-instance basis since we can determine them in advance. What we have here is a new framework for analyzing the QAOA, and our techniques can be of broad interest for evaluating its performance on more general problems where classical algorithms may fail.

arXiv:1910.08187•Quantum•Jul 7, 2022•226 citations

Efficient Classical Computation of Quantum Mean Values for Shallow QAOA Circuits

Wei-Feng Zhuang, Ya-Nan Pu, Hong-Ze Xu +9 more

The Quantum Approximate Optimization Algorithm (QAOA), which is a variational quantum algorithm, aims to give sub-optimal solutions of combinatorial optimization problems. It is widely believed that QAOA has the potential to demonstrate application-level quantum advantages in the noisy intermediate-scale quantum(NISQ) processors with shallow circuit depth. Since the core of QAOA is the computation of expectation values of the problem Hamiltonian, an important practical question is whether we can find an efficient classical algorithm to solve quantum mean value in the case of general shallow quantum circuits. Here, we present a novel graph decomposition based classical algorithm that scales linearly with the number of qubits for the shallow QAOA circuits in most optimization problems except for complete graph case. Numerical tests in Max-cut, graph coloring and Sherrington-Kirkpatrick model problems, compared to the state-of-the-art method, shows orders of magnitude performance improvement. Our results are not only important for the exploration of quantum advantages with QAOA, but also useful for the benchmarking of NISQ processors.

arXiv:2112.11151•Dec 21, 2021•3 citations

Solving Boolean Satisfiability Problems With The Quantum Approximate Optimization Algorithm

Sami Boulebnane, Ashley Montanaro

One of the most prominent application areas for quantum computers is solving hard constraint satisfaction and optimization problems. However, detailed analyses of the complexity of standard quantum algorithms have suggested that outperforming classical methods for these problems would require extremely large and powerful quantum computers. The quantum approximate optimization algorithm (QAOA) is designed for near-term quantum computers, yet previous work has shown strong limitations on the ability of QAOA to outperform classical algorithms for optimization problems. Here we instead apply QAOA to hard constraint satisfaction problems, where both classical and quantum algorithms are expected to require exponential time. We analytically characterize the average success probability of QAOA on a constraint satisfaction problem commonly studied using statistical physics methods: random k -SAT at the threshold for satisfiability, as the number of variables n goes to infinity. We complement these theoretical results with numerical experiments on the performance of QAOA for small n , which match the limiting theoretical bounds closely. We then compare QAOA with leading classical solvers. For random 8-SAT, we find that for more than 14 quantum circuit layers, QAOA achieves more efficient scaling than the highest-performance classical solver we tested, WalkSATlm. Our results suggest that near-term quantum algorithms for solving constraint satisfaction problems may outperform their classical counterparts. Published by the American Physical Society 2024

arXiv:2208.06909•PRX Quantum•Sep 10, 2024•57 citations
The quantum approximate optimization algorithm (QAOA) is suggested as a promising application on early quantum computers.Here a quantum-inspired classical algorithm, the mean-field approximate optimization algorithm (mean-field AOA), is developed by replacement of the quantum evolution of the QAOA with classical spin dynamics through the mean-field approximation.Because of the alternating structure of the QAOA, this classical dynamics can be found exactly for any number of QAOA layers.We benchmark its performance against the QAOA on the Sherrington-Kirkpatrick model and the partition problem, and find that the mean-field AOA outperforms the QAOA in both cases for most instances.Our algorithm can thus serve as a tool to delineate optimization problems that can be solved classically from those that cannot, i.e., we believe that it will help to identify instances where a true quantum advantage can be expected from the QAOA.To quantify quantum fluctuations around the mean-field trajectories, we solve an effective scattering problem in time, which is characterized by a spectrum of time-dependent Lyapunov exponents.These provide an indicator for the hardness of a given optimization problem relative to the mean-field AOA.
The Quantum Approximate Optimization Algorithm (QAOA) is suggested as a promising application on early quantum computers. Here, a quantum-inspired classical algorithm, the mean-field Approximate Optimization Algorithm (mean-field AOA), is developed by replacing the quantum evolution of the QAOA with classical spin dynamics through the mean-field approximation. Due to the alternating structure of the QAOA, this classical dynamics can be found exactly for any number of QAOA layers. We benchmark its performance against the QAOA on the Sherrington-Kirkpatrick (SK) model and the partition problem, and find that the mean-field AOA outperforms the QAOA in both cases for most instances. Our algorithm can thus serve as a tool to delineate optimization problems that can be solved classically from those that cannot, i.e. we believe that it will help to identify instances where a true quantum advantage can be expected from the QAOA. To quantify quantum fluctuations around the mean-field trajectories, we solve an effective scattering problem in time, which is characterized by a spectrum of time-dependent Lyapunov exponents. These provide an indicator for the hardness of a given optimization problem relative to the mean-field AOA.
In this paper, we prove that the Mean-Field Approximate Optimization Algorithm (MF-AOA), a quantum-inspired classical algorithm of the Quantum Approximate Optimization Algorithm (QAOA), is unable to give arbitrary near optimal solution for problems exhibiting the Overlap Gap Property (OGP). We show this by relating the MF-AOA to finite-memory Approximate Message Passing (AMP) algorithms, which are known to be limited in performance by the OGP. Thus, our paper argues that problems exhibiting the OGP are one such instance where the QAOA can outperform the MF-AOA and AMP algorithms in general. We supplement this by numerically simulating the performance of the QAOA on instances of Max-444-XORSAT that exhibit the OGP and find that the QAOA is able to surpass the barrier, while our finite-size scaling analysis favors a super-polynomial over a polynomial depth dependence. In addition, we observe a non-differentiable point in the performance of the QAOA near by the OGP barrier, where the optimal QAOA parameters change from an adiabatic to a non-adiabatic schedule.
Quantum algorithms are an area of intensive research thanks to their potential for speeding up certain specific tasks exponentially.However, for the time being, high error rates on the existing hardware realizations preclude the application of many algorithms that are based on the assumption of fault-tolerant quantum computation.On such noisy intermediatescale quantum (NISQ) devices (Preskill, 2018), the exploration of the potential of heuristic quantum algorithms has attracted much interest.A leading candidate for solving combinatorial optimization problems is the so-called Quantum Approximate Optimization Algorithm (QAOA) (Farhi et al., 2014).QAOA.jl is a Julia package (Bezanson et al., 2017) that implements the mean-field Approximate Optimization Algorithm (mean-field AOA) (Misra-Spieldenner et al., 2023) -a quantum-inspired classical algorithm derived from the QAOA via the mean-field approximation.This novel algorithm is useful in assisting the search for quantum advantage by providing a tool to discriminate (combinatorial) optimization problems that can be solved classically from those that cannot.Note that QAOA.jl has already been used during the research leading to Misra-Spieldenner et al. (2023).
The Quantum Approximate Optimization Algorithm (QAOA) is a general-purpose algorithm for combinatorial optimization problems whose performance can only improve with the number of layers p . While QAOA holds promise as an algorithm that can be run on near-term quantum computers, its computational power has not been fully explored. In this work, we study the QAOA applied to the Sherrington-Kirkpatrick (SK) model, which can be understood as energy minimization of n spins with all-to-all random signed couplings. There is a recent classical algorithm by Montanari that, assuming a widely believed conjecture, can efficiently find an approximate solution for a typical instance of the SK model to within ( 1 − ϵ ) times the ground state energy. We hope to match its performance with the QAOA.Our main result is a novel technique that allows us to evaluate the typical-instance energy of the QAOA applied to the SK model. We produce a formula for the expected value of the energy, as a function of the 2 p QAOA parameters, in the infinite size limit that can be evaluated on a computer with O ( 16 p ) complexity. We evaluate the formula up to p = 12 , and find that the QAOA at p = 11 outperforms the standard semidefinite programming algorithm. Moreover, we show concentration: With probability tending to one as n → ∞ , measurements of the QAOA will produce strings whose energies concentrate at our calculated value. As an algorithm running on a quantum computer, there is no need to search for optimal parameters on an instance-by-instance basis since we can determine them in advance. What we have here is a new framework for analyzing the QAOA, and our techniques can be of broad interest for evaluating its performance on more general problems where classical algorithms may fail.
The Quantum Approximate Optimization Algorithm (QAOA), which is a variational quantum algorithm, aims to give sub-optimal solutions of combinatorial optimization problems. It is widely believed that QAOA has the potential to demonstrate application-level quantum advantages in the noisy intermediate-scale quantum(NISQ) processors with shallow circuit depth. Since the core of QAOA is the computation of expectation values of the problem Hamiltonian, an important practical question is whether we can find an efficient classical algorithm to solve quantum mean value in the case of general shallow quantum circuits. Here, we present a novel graph decomposition based classical algorithm that scales linearly with the number of qubits for the shallow QAOA circuits in most optimization problems except for complete graph case. Numerical tests in Max-cut, graph coloring and Sherrington-Kirkpatrick model problems, compared to the state-of-the-art method, shows orders of magnitude performance improvement. Our results are not only important for the exploration of quantum advantages with QAOA, but also useful for the benchmarking of NISQ processors.
One of the most prominent application areas for quantum computers is solving hard constraint satisfaction and optimization problems. However, detailed analyses of the complexity of standard quantum algorithms have suggested that outperforming classical methods for these problems would require extremely large and powerful quantum computers. The quantum approximate optimization algorithm (QAOA) is designed for near-term quantum computers, yet previous work has shown strong limitations on the ability of QAOA to outperform classical algorithms for optimization problems. Here we instead apply QAOA to hard constraint satisfaction problems, where both classical and quantum algorithms are expected to require exponential time. We analytically characterize the average success probability of QAOA on a constraint satisfaction problem commonly studied using statistical physics methods: random k -SAT at the threshold for satisfiability, as the number of variables n goes to infinity. We complement these theoretical results with numerical experiments on the performance of QAOA for small n , which match the limiting theoretical bounds closely. We then compare QAOA with leading classical solvers. For random 8-SAT, we find that for more than 14 quantum circuit layers, QAOA achieves more efficient scaling than the highest-performance classical solver we tested, WalkSATlm. Our results suggest that near-term quantum algorithms for solving constraint satisfaction problems may outperform their classical counterparts. Published by the American Physical Society 2024