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.10838

The Quantum Overlap Gap Property and Algorithmic Hardness for the Quantum Hypergraph Max-Cut Problem

Mikhail Mints, Eric R. Anschuetz

quant-phcs.CCSubmitted Sep 9, 2026• Announced Sep 11, 2026• 0 citations
arXivHTMLPDF

Abstract

In this work, we analyze the average-case hardness of approximation for the Quantum Hypergraph Max-Cut problem using the theoretical framework of the Quantum Overlap Gap Property (QOGP). We establish two main results. Our first result applies to a wide class of stable quantum algorithms, satisfying a Lipschitz property with respect to the quantum Wasserstein distance of order $2$. We show a weak hardness result, demonstrating that for any Lipschitz constant $L$, there is some $k$ such that $L$-stable algorithms cannot approximate the optimal solution to Quantum Hypergraph Max-Cut on $k$-uniform hypergraphs in the average case. Additionally, we establish a strong hardness result where $k$ is independent of $L$, but only for a more restricted class of local quantum algorithms defined using the quantum Wasserstein distance of order $\infty$. We apply these results to establish concrete depth lower bounds for popular quantum algorithms for preparing near-optimal states for this problem.

Comments
60 pages, 3 figures

Related papers

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

On the approximability of random-hypergraph MAX-3-XORSAT problems with quantum algorithms

Eliot Kapit, Brandon Barton, Sean Feeney +5 more

A canonical feature of the constraint satisfaction problems in NP is approximation hardness, where in the worst case, finding sufficient-quality approximate solutions is exponentially hard for all known methods. Fundamentally, the lack of any guided local minimum escape method ensures both exact and approximate classical approximation hardness, but the equivalent mechanism(s) for quantum algorithms are poorly understood. For algorithms based on Hamiltonian time evolution, we explore this question through the prototypically hard MAX-3-XORSAT problem class. We conclude that the mechanisms for quantum exact and approximation hardness are fundamentally distinct. We review known results from the literature, and identify mechanisms that make conventional quantum methods (such as Adiabatic Quantum Computing) weak approximation algorithms in the worst case. We construct a family of spectrally filtered quantum algorithms that escape these issues, and develop analytical theories for their performance. We show that, for random hypergraphs in the approximation-hard regime, if we define the energy to be $E = N_{\mathrm{unsat}}-N_{\mathrm{sat}}$, spectrally filtered quantum optimization will return states with $E \leq q_m E_{\mathrm{GS}}$ (where $E_{\rm GS}$ is the ground state energy) in sub-quadratic time, where conservatively, $q_m \simeq 0.59$. This is in contrast to $q_m \to 0$ for the hardest instances with classical searches. We test all of these claims with extensive numerical simulations. We do not claim that this approximation guarantee holds for all possible hypergraphs, though our algorithm's mechanism can likely generalize widely. These results suggest that quantum computers are more powerful for approximate optimization than had been previously assumed.

arXiv:2312.06104•Dec 11, 2023•1 citation

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

Quantum approximate optimization algorithms for maximum cut on low-girth graphs

Tongyang Li, Yan‐Kun Su, Ziyi Yang +1 more

Abstract Maximum cut (MaxCut) on graphs is a classic NP-hard problem. In quantum computing, Farhi, Gutmann, and Goldstone proposed the Quantum Approximate Optimization Algorithm (QAOA) for solving the MaxCut problem. Its guarantee on cut fraction (the fraction of edges in the output cut over all edges) was mainly studied for high-girth graphs, i.e., graphs with only long cycles. On the other hand, low-girth graphs are ubiquitous in theoretical computer science, including expander graphs being outstanding examples with wide applications in theory and beyond. In this paper, we apply QAOA to MaxCut on a set of expander graphs proposed by Mohanty and O'Donnell known as additive product graphs. Additionally, we apply multi-angle QAOA (ma-QAOA) to better utilize the graph structure of additive product graphs in ansatz design. In theory, we derive an iterative formula to calculate the expected cut fraction of such graphs. This formula also extends to the quantum MaxCut problem. On the other hand, we conduct numerical experiments to compare between best-known classical local algorithms and QAOA with constant depth. Our results demonstrate that QAOA outperforms the best-known classical algorithms by 0.3% to 5.2% on several additive product graphs, while ma-QAOA further enhances this advantage by an additional 0.6% to 2.5%. In particular, we observe cases that ma-QAOA exhibits superiority over best-known classical algorithms but QAOA does not. Furthermore, we extend our experiments to planar graphs such as tiling grid graphs, where QAOA also demonstrates an advantage.

arXiv:2410.04409•Physical Review Research•May 28, 2025•3 citations

On the (Classical and Quantum) Fine-Grained Complexity of Approximate CVP and Max-Cut

Huang, Jeremy Ahrens, Young Kun Ko, Chunhao Wang

We show a linear-size reduction from gap Max-2-Lin(2) (a generalization of the approximate Maximum Cut, or gap Max-Cut, problem) to γ-CVP_p for γ = O(1) and finite p ≥ 1, as well as a no-go theorem against poly-sized non-adaptive quantum reductions from k-SAT to CVP₂. This implies three headline results: (i) Faster algorithms for γ-CVP_p are also faster algorithms for Max-2-Lin(2) and Max-Cut. Depending on the approximation regime, even a 2^{0.78n}-time or 2^{0.3n}-time algorithm would improve upon state-of-the-art algorithms such as Williams' 2004 algorithm [TCS 2005] or Arora, Barak, and Steurer’s 2010 algorithm [JACM 2015]. This provides evidence that γ-CVP_p for γ = O(1) requires exponential time, improving upon the previous exponential lower-bound for γ-CVP₂ with γ < 3 by Bennett, Golovnev, and Stephens-Davidowitz [FOCS 2017]. (ii) A new almost 2^{(1/2 + ε/4ς + o(1)) n}-time classical algorithm and a new almost 2^{(1/3 + ε/6ς + o(1)) n}-time quantum algorithm for (1-ε, 1-ς)-gap Max-Cut. This algorithm is faster than the algorithm of Arora, Barak and Steurer [JACM 2015], as well as the algorithm of Williams [TCS 2005], and the algorithm of Manurangsi and Trevisan [APPROX 2018] when c₀ ε < ς < c₁ ε for constants c₀, c₁. (iii) If the Quantum Strong Exponential Time Hypothesis (QSETH) can be used to show a 2^{δ n}-time lower-bound for Max-Cut, Max-2-Lin(2), or CVP₂ for any constant δ > 0, it must be via an adaptive quantum reduction unless NP ⊆ pr-QSZK. This illuminates some difficulties in characterizing the hardness of approximate constraint satisfaction problems and shows that the post-quantum security of lattice-based cryptography likely cannot be supported by QSETH. This result complements the no-go results of Aggarwal and Kumar [FOCS 2023], who showed that the classical security of lattice-based cryptography likely cannot be supported by the classical Strong Exponential Time Hypothesis (SETH).

arXiv:2411.04124•Leibniz international proceedings in informatics•Nov 6, 2024•0 citations

Improving the Quantum Approximate Optimization Algorithm with postselection

Sami Boulebnane

Combinatorial optimization is among the main applications envisioned for near-term and fault-tolerant quantum computers. In this work, we consider a well-studied quantum algorithm for combinatorial optimization: the Quantum Approximate Optimization Algorithm (QAOA) applied to the MaxCut problem on 3-regular graphs. We explore the idea of improving the solutions returned by the simplest version of the algorithm (depth-1 QAOA) using a form of postselection that can be efficiently simulated by state preparation. We derive theoretical upper and lower bounds showing that a constant (though small) increase of the fraction of satisfied edges is indeed achievable. Numerical experiments on large problem instances (beyond classical simulatability) complement and support our bounds. We also consider a distinct technique: local updates, which can be applied not only to QAOA but any optimization algorithm. In the case of QAOA, the resulting improvement can be sharply quantified theoretically for large problem instances and in absence of postselection. Combining postselection and local updates, the theory is no longer tractable but numerical evidence suggests that improvements from both methods can be combined.

arXiv:2011.05425•Nov 10, 2020•1 citation
In this work, we analyze the average-case hardness of approximation for the Quantum Hypergraph Max-Cut problem using the theoretical framework of the Quantum Overlap Gap Property (QOGP). We establish two main results. Our first result applies to a wide class of stable quantum algorithms, satisfying a Lipschitz property with respect to the quantum Wasserstein distance of order 222. We show a weak hardness result, demonstrating that for any Lipschitz constant LLL, there is some kkk such that LLL-stable algorithms cannot approximate the optimal solution to Quantum Hypergraph Max-Cut on kkk-uniform hypergraphs in the average case. Additionally, we establish a strong hardness result where kkk is independent of LLL, but only for a more restricted class of local quantum algorithms defined using the quantum Wasserstein distance of order ∞\infty∞. We apply these results to establish concrete depth lower bounds for popular quantum algorithms for preparing near-optimal states for this problem.
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.
A canonical feature of the constraint satisfaction problems in NP is approximation hardness, where in the worst case, finding sufficient-quality approximate solutions is exponentially hard for all known methods. Fundamentally, the lack of any guided local minimum escape method ensures both exact and approximate classical approximation hardness, but the equivalent mechanism(s) for quantum algorithms are poorly understood. For algorithms based on Hamiltonian time evolution, we explore this question through the prototypically hard MAX-3-XORSAT problem class. We conclude that the mechanisms for quantum exact and approximation hardness are fundamentally distinct. We review known results from the literature, and identify mechanisms that make conventional quantum methods (such as Adiabatic Quantum Computing) weak approximation algorithms in the worst case. We construct a family of spectrally filtered quantum algorithms that escape these issues, and develop analytical theories for their performance. We show that, for random hypergraphs in the approximation-hard regime, if we define the energy to be E=Nunsat−NsatE = N_{\mathrm{unsat}}-N_{\mathrm{sat}}E=Nunsat​−Nsat​, spectrally filtered quantum optimization will return states with E≤qmEGSE \leq q_m E_{\mathrm{GS}}E≤qm​EGS​ (where EGSE_{\rm GS}EGS​ is the ground state energy) in sub-quadratic time, where conservatively, qm≃0.59q_m \simeq 0.59qm​≃0.59. This is in contrast to qm→0q_m \to 0qm​→0 for the hardest instances with classical searches. We test all of these claims with extensive numerical simulations. We do not claim that this approximation guarantee holds for all possible hypergraphs, though our algorithm's mechanism can likely generalize widely. These results suggest that quantum computers are more powerful for approximate optimization than had been previously assumed.
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.
Abstract Maximum cut (MaxCut) on graphs is a classic NP-hard problem. In quantum computing, Farhi, Gutmann, and Goldstone proposed the Quantum Approximate Optimization Algorithm (QAOA) for solving the MaxCut problem. Its guarantee on cut fraction (the fraction of edges in the output cut over all edges) was mainly studied for high-girth graphs, i.e., graphs with only long cycles. On the other hand, low-girth graphs are ubiquitous in theoretical computer science, including expander graphs being outstanding examples with wide applications in theory and beyond. In this paper, we apply QAOA to MaxCut on a set of expander graphs proposed by Mohanty and O'Donnell known as additive product graphs. Additionally, we apply multi-angle QAOA (ma-QAOA) to better utilize the graph structure of additive product graphs in ansatz design. In theory, we derive an iterative formula to calculate the expected cut fraction of such graphs. This formula also extends to the quantum MaxCut problem. On the other hand, we conduct numerical experiments to compare between best-known classical local algorithms and QAOA with constant depth. Our results demonstrate that QAOA outperforms the best-known classical algorithms by 0.3% to 5.2% on several additive product graphs, while ma-QAOA further enhances this advantage by an additional 0.6% to 2.5%. In particular, we observe cases that ma-QAOA exhibits superiority over best-known classical algorithms but QAOA does not. Furthermore, we extend our experiments to planar graphs such as tiling grid graphs, where QAOA also demonstrates an advantage.
We show a linear-size reduction from gap Max-2-Lin(2) (a generalization of the approximate Maximum Cut, or gap Max-Cut, problem) to γ-CVP_p for γ = O(1) and finite p ≥ 1, as well as a no-go theorem against poly-sized non-adaptive quantum reductions from k-SAT to CVP₂. This implies three headline results: (i) Faster algorithms for γ-CVP_p are also faster algorithms for Max-2-Lin(2) and Max-Cut. Depending on the approximation regime, even a 2^{0.78n}-time or 2^{0.3n}-time algorithm would improve upon state-of-the-art algorithms such as Williams' 2004 algorithm [TCS 2005] or Arora, Barak, and Steurer’s 2010 algorithm [JACM 2015]. This provides evidence that γ-CVP_p for γ = O(1) requires exponential time, improving upon the previous exponential lower-bound for γ-CVP₂ with γ < 3 by Bennett, Golovnev, and Stephens-Davidowitz [FOCS 2017]. (ii) A new almost 2^{(1/2 + ε/4ς + o(1)) n}-time classical algorithm and a new almost 2^{(1/3 + ε/6ς + o(1)) n}-time quantum algorithm for (1-ε, 1-ς)-gap Max-Cut. This algorithm is faster than the algorithm of Arora, Barak and Steurer [JACM 2015], as well as the algorithm of Williams [TCS 2005], and the algorithm of Manurangsi and Trevisan [APPROX 2018] when c₀ ε < ς < c₁ ε for constants c₀, c₁. (iii) If the Quantum Strong Exponential Time Hypothesis (QSETH) can be used to show a 2^{δ n}-time lower-bound for Max-Cut, Max-2-Lin(2), or CVP₂ for any constant δ > 0, it must be via an adaptive quantum reduction unless NP ⊆ pr-QSZK. This illuminates some difficulties in characterizing the hardness of approximate constraint satisfaction problems and shows that the post-quantum security of lattice-based cryptography likely cannot be supported by QSETH. This result complements the no-go results of Aggarwal and Kumar [FOCS 2023], who showed that the classical security of lattice-based cryptography likely cannot be supported by the classical Strong Exponential Time Hypothesis (SETH).
Combinatorial optimization is among the main applications envisioned for near-term and fault-tolerant quantum computers. In this work, we consider a well-studied quantum algorithm for combinatorial optimization: the Quantum Approximate Optimization Algorithm (QAOA) applied to the MaxCut problem on 3-regular graphs. We explore the idea of improving the solutions returned by the simplest version of the algorithm (depth-1 QAOA) using a form of postselection that can be efficiently simulated by state preparation. We derive theoretical upper and lower bounds showing that a constant (though small) increase of the fraction of satisfied edges is indeed achievable. Numerical experiments on large problem instances (beyond classical simulatability) complement and support our bounds. We also consider a distinct technique: local updates, which can be applied not only to QAOA but any optimization algorithm. In the case of QAOA, the resulting improvement can be sharply quantified theoretically for large problem instances and in absence of postselection. Combining postselection and local updates, the theory is no longer tractable but numerical evidence suggests that improvements from both methods can be combined.