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

arXiv:2609.35131

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

Mark Goh, Thorge Müller

quant-phSubmitted Sep 28, 2026• Announced Sep 29, 2026• 0 citations
arXivHTMLPDF

Abstract

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.

Related papers

The overlap gap property and its implication for the quantum approximate optimisation algorithm

Mark Xin Hong Goh

The main focus of this thesis can be framed in the following question: How does the presence and absence of the overlap gap property (OGP) affect quantum algorithms such as the quantum approximate optimization algorithm (QAOA)? The OGP, a topological property that occurs when the set of near optimal solutions exhibits a form of strong clustering, is known to inhibit the performance of various classes of algorithms. In classical algorithms, the OGP acts a tight upper bound on many different classes of algorithms including online algorithms and ‘stable’ algorithms such as Lipschitz algorithms. For quantum algorithms, the OGP is known to inhibit the algorithmic performance at shallow depth such as logarithmic depth quantum annealing. This thesis focuses on how the OGP affects the QAOA and advances the understanding of the run-time required for quantum advantage. Improving upon previous results, I prove that at logarithmic depth, the OGP acts as a strict upper bound for the QAOA thus proving that there is indeed no quantum advantage at logarithmic depth. Complementing the analytic result above, I similarly proved that the performance of the mean-field approximate optimization algorithm (MF-AOA), a classical algorithm inspired by the QAOA, is likewise strictly upper-bounded by the OGP. Thus, for the QAOA to exhibit quantum advantage over its classical counterpart, one requires sufficiently high depth such that the QAOA is able to give an output that is greater than the OGP value. Together with my collaborator, we also provide numerical evidence that the depth required for quantum advantage in the QAOA is super-polynomial if one requires the approximation ratio to be higher than the OGP value. While this thesis adds onto the growing body of literature of how the OGP acts as a signal of algorithmic hardness for many classes of algorithms, this work also provides the first instance of how the OGP can inform algorithmic design. This thesis provides evidence that in the presence of the OGP, the variational parameters used to optimize the QAOA’s output at polynomial depth differ depending on whether one wishes to maximize the approximation ratio or to minimize the time to find the optimal solution.Understanding the right schedule is important for designing an optimal quantum control to steer a quantum state into its desired form. Our results also indicate that problems that do not exhibit the OGP are likely to be solved efficiently by quantum annealing or adiabatic quantum computing since the optimal schedule found in the QAOA follows an adiabatic schedule. Lastly, this thesis provides a novel use of the QAOA, that of identifying use cases where efficient classical algorithms exists but are yet to be discovered. Specifically,by applying logarithmic depth QAOA to the binary paint shop problem (BPSP), we show that the performance of the QAOA surpasses that of all known polynomial time classical algorithms. However, given the failure of logarithmic depth QAOA to outperform classical algorithms on sparse optimization problems such as the BPSP, this implies that there must be an efficient classical algorithm that beats all currently known heuristic methods. Applying the MF-AOA to the BPSP, we find that it significantly outperforms all known classical heuristics and applications of the QAOA (and its variants) on the BPSP.

•Jan 1, 2026•0 citations

OGP LIMITS LIMIT SWAPPING IN QAOA

Goh, Mark Xin Hong

The Quantum Approximate Optimization Algorithm (QAOA) is a quantum algorithm designed for combinatorial optimization problem. We show that under the assumption that the Overlap Gap Property (OGP) in the solution space for the Max-q-XORSAT is a monotonic increasing function, the swapping of limits in QAOA leads to suboptimal results limited by the OGP. Furthermore, since the performance of QAOA for the pure q-spin model matches asymptotically for Max-q-XORSAT on large-girth regular hypergraph, we show that the average-case value obtained by QAOA for the pure q-spin model for even q≥4 is bounded away from optimality even when the algorithm runs indefinitely. This suggests that a necessary condition for the validity of limit swapping in QAOA is the absence of OGP in a given combinatorial optimization problem. A corollary of this is that the spectral gap of a Hamiltonian exhibiting the OGP will close in the thermodynamic limit resulting in a limitation of the quantum adiabatic theorem and efficient optimization of QAOA parameters. Furthermore, the results suggests that even when sub-optimised, the performance of QAOA on spin glass is equal in performance to Montanari's classical algorithm in solving the mean field spin glass problem, the best known classical algorithm.

•Mar 20, 2024•0 citations

Mean-Field Approximate Optimization Algorithm

Aditi Misra-Spieldenner, Tim Bode, Peter Schuhmacher +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 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.

PRX Quantum•Sep 12, 2023•22 citations

The Overlap Gap Property Limits Limit Swapping in the QAOA

Mark Xin Hong Goh

Abstract The Quantum Approximate Optimization Algorithm (QAOA) is a quantum algorithm designed for Combinatorial Optimization Problem (COP). We show that if a local algorithm is limited in performance at logarithmic depth for a spin glass type COP with an underlying Erdös-Renyi hypergraph, then a random regular hypergraph is similarly limited in performance as well. As such, we re-derived the fact that the average-case value obtained by the QAOA for even q ≥ 4, Max- q -XORSAT is bounded away from optimality when optimized using asymptotic analysis due to the Overlap Gap Property (OGP). While this result was proven before, the proof is rather technical compared to ours. In addition, we show that the earlier result implicitly also implies limitation at logarithmic depth p ≤ ϵ log n , providing an improvement over limitation at constant depth. Furthermore, the extension to logarithmic depth leads to a tightening of the upper bound that the QAOA outputs at logarithmic depth for MaxCUT and Max- q -XORSAT problems. We also provide some numerical evidence that the limitation should be extended to odd q by showing that the OGP exists for the Max-3-XORSAT on random regular graphs.

arXiv:2404.06087•Quantum Information and Computation•Aug 1, 2025•2 citations

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

Scaling QAOA: transferring optimal adiabatic schedules from small-scale to large-scale variational circuits

Ugo Nzongani, Dylan Laplace Mermoud, Arthur Braida

The Quantum Approximate Optimization Algorithm (QAOA) is a leading approach for combinatorial optimization on near-term quantum devices, yet its scalability is limited by the difficulty of optimizing \(2p\) variational parameters for a large number \(p\) of layers. Recent empirical studies indicate that optimal QAOA angles exhibit concentration and transferability across problem sizes. Leveraging this observation, we propose a schedule-learning framework that transfers spectral-gap-informed adiabatic control strategies from small-scale instances to larger systems. Our method extracts the spectral gap profile of small problems and constructs a continuous schedule governed by \(\partial_t s = κg^q(s)\), where \(g(s)\) is the instantaneous gap and \((κ, q)\) are global hyperparameters. Discretizing this schedule yields closed-form expressions for all QAOA angles, reducing the classical optimization task from \(2p\) parameters to only \(2\), independent of circuit depth. This drastic parameter compression mitigates classical optimization overhead and reduces sensitivity to barren plateau phenomena. Numerical simulations on random QUBO and 3-regular MaxCut instances demonstrate that the learnt schedules transfer effectively to larger systems while achieving competitive approximation ratios. Our results suggest that gap-informed schedule transfers provide a scalable and parameter-efficient strategy for QAOA.

quant-pharXiv:2602.14986•IEEE International Conference on Quantum Control, Computing and Learning (qCCL)•Feb 17, 2026•0 citations
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.
The main focus of this thesis can be framed in the following question: How does the presence and absence of the overlap gap property (OGP) affect quantum algorithms such as the quantum approximate optimization algorithm (QAOA)? The OGP, a topological property that occurs when the set of near optimal solutions exhibits a form of strong clustering, is known to inhibit the performance of various classes of algorithms. In classical algorithms, the OGP acts a tight upper bound on many different classes of algorithms including online algorithms and ‘stable’ algorithms such as Lipschitz algorithms. For quantum algorithms, the OGP is known to inhibit the algorithmic performance at shallow depth such as logarithmic depth quantum annealing. This thesis focuses on how the OGP affects the QAOA and advances the understanding of the run-time required for quantum advantage. Improving upon previous results, I prove that at logarithmic depth, the OGP acts as a strict upper bound for the QAOA thus proving that there is indeed no quantum advantage at logarithmic depth. Complementing the analytic result above, I similarly proved that the performance of the mean-field approximate optimization algorithm (MF-AOA), a classical algorithm inspired by the QAOA, is likewise strictly upper-bounded by the OGP. Thus, for the QAOA to exhibit quantum advantage over its classical counterpart, one requires sufficiently high depth such that the QAOA is able to give an output that is greater than the OGP value. Together with my collaborator, we also provide numerical evidence that the depth required for quantum advantage in the QAOA is super-polynomial if one requires the approximation ratio to be higher than the OGP value. While this thesis adds onto the growing body of literature of how the OGP acts as a signal of algorithmic hardness for many classes of algorithms, this work also provides the first instance of how the OGP can inform algorithmic design. This thesis provides evidence that in the presence of the OGP, the variational parameters used to optimize the QAOA’s output at polynomial depth differ depending on whether one wishes to maximize the approximation ratio or to minimize the time to find the optimal solution.Understanding the right schedule is important for designing an optimal quantum control to steer a quantum state into its desired form. Our results also indicate that problems that do not exhibit the OGP are likely to be solved efficiently by quantum annealing or adiabatic quantum computing since the optimal schedule found in the QAOA follows an adiabatic schedule. Lastly, this thesis provides a novel use of the QAOA, that of identifying use cases where efficient classical algorithms exists but are yet to be discovered. Specifically,by applying logarithmic depth QAOA to the binary paint shop problem (BPSP), we show that the performance of the QAOA surpasses that of all known polynomial time classical algorithms. However, given the failure of logarithmic depth QAOA to outperform classical algorithms on sparse optimization problems such as the BPSP, this implies that there must be an efficient classical algorithm that beats all currently known heuristic methods. Applying the MF-AOA to the BPSP, we find that it significantly outperforms all known classical heuristics and applications of the QAOA (and its variants) on the BPSP.
The Quantum Approximate Optimization Algorithm (QAOA) is a quantum algorithm designed for combinatorial optimization problem. We show that under the assumption that the Overlap Gap Property (OGP) in the solution space for the Max-q-XORSAT is a monotonic increasing function, the swapping of limits in QAOA leads to suboptimal results limited by the OGP. Furthermore, since the performance of QAOA for the pure q-spin model matches asymptotically for Max-q-XORSAT on large-girth regular hypergraph, we show that the average-case value obtained by QAOA for the pure q-spin model for even q≥4 is bounded away from optimality even when the algorithm runs indefinitely. This suggests that a necessary condition for the validity of limit swapping in QAOA is the absence of OGP in a given combinatorial optimization problem. A corollary of this is that the spectral gap of a Hamiltonian exhibiting the OGP will close in the thermodynamic limit resulting in a limitation of the quantum adiabatic theorem and efficient optimization of QAOA parameters. Furthermore, the results suggests that even when sub-optimised, the performance of QAOA on spin glass is equal in performance to Montanari's classical algorithm in solving the mean field spin glass problem, the best known classical algorithm.
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.
Abstract The Quantum Approximate Optimization Algorithm (QAOA) is a quantum algorithm designed for Combinatorial Optimization Problem (COP). We show that if a local algorithm is limited in performance at logarithmic depth for a spin glass type COP with an underlying Erdös-Renyi hypergraph, then a random regular hypergraph is similarly limited in performance as well. As such, we re-derived the fact that the average-case value obtained by the QAOA for even q ≥ 4, Max- q -XORSAT is bounded away from optimality when optimized using asymptotic analysis due to the Overlap Gap Property (OGP). While this result was proven before, the proof is rather technical compared to ours. In addition, we show that the earlier result implicitly also implies limitation at logarithmic depth p ≤ ϵ log n , providing an improvement over limitation at constant depth. Furthermore, the extension to logarithmic depth leads to a tightening of the upper bound that the QAOA outputs at logarithmic depth for MaxCUT and Max- q -XORSAT problems. We also provide some numerical evidence that the limitation should be extended to odd q by showing that the OGP exists for the Max-3-XORSAT on random regular graphs.
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.
The Quantum Approximate Optimization Algorithm (QAOA) is a leading approach for combinatorial optimization on near-term quantum devices, yet its scalability is limited by the difficulty of optimizing 2p2p2p variational parameters for a large number ppp of layers. Recent empirical studies indicate that optimal QAOA angles exhibit concentration and transferability across problem sizes. Leveraging this observation, we propose a schedule-learning framework that transfers spectral-gap-informed adiabatic control strategies from small-scale instances to larger systems. Our method extracts the spectral gap profile of small problems and constructs a continuous schedule governed by ∂ts=κgq(s)\partial_t s = κg^q(s)∂t​s=κgq(s), where g(s)g(s)g(s) is the instantaneous gap and (κ,q)(κ, q)(κ,q) are global hyperparameters. Discretizing this schedule yields closed-form expressions for all QAOA angles, reducing the classical optimization task from 2p2p2p parameters to only 222, independent of circuit depth. This drastic parameter compression mitigates classical optimization overhead and reduces sensitivity to barren plateau phenomena. Numerical simulations on random QUBO and 3-regular MaxCut instances demonstrate that the learnt schedules transfer effectively to larger systems while achieving competitive approximation ratios. Our results suggest that gap-informed schedule transfers provide a scalable and parameter-efficient strategy for QAOA.