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

NISQ Hardness and Convex Relaxations: Random Max-CSPs and Mean-Field Spin Glasses

Sandhu, Juspreet Singh

Published Jan 1, 2023• 0 citations
OpenAlex

Abstract

The Unique-Games Conjecture (UGC)~\cite{khot2002power} is a central open-question in theoretical computer science. If true, it implies optimal inapproximability results for \emph{every} Max-CSP. Despite impressive recent progress towards the conjecture~\cite{khot2017independent, barak2018small, subhash2018pseudorandom, dinur2018non, dinur2018towards} there are no candidate instances for \emph{every} Max-CSP that would saturate the integrality gap of Raghavendra's ``UGC-optimal'' Semi-Definite Program (SDP)~\cite{raghavendra2008optimal}. In parallel, though it is known that reducing the factoring problem into Max-3-SAT can yield an efficient quantum algorithm for approximating conjectured classically hard Max-CSP instances~\cite{szegedy2022quantum}, no ``natural'' family of Max-CSP instances are known to give quantum advantage. Furthermore, it is an open-question whether efficient quantum algorithms can approximate Max-CSPs better than classical polynomial time algorithms on instances that saturate the integrality gap of Raghavendra's SDP~\cite{szegedy2022quantum}. A natural complementary starting point, therefore, is to investigate the complexity landscape of \emph{random} instances of \emph{sparse} Max-CSPs. \\ \vspace{2mm} In this thesis, we make further progress in understanding the complexity landscape of such Max-CSPs. We prove that \emph{random} instances of \emph{all} Max-CSPs exhibit solution-space geometries akin to those of objects from statistical physics called \emph{mean-field spin glasses}~\cite{jones2022random}. As a consequence of this connection, the optimal number of clauses satisfied by typical instances of such Max-CSPs can be expressed as a function of the \emph{ground state energy density} of the related mean-field spin glass. Complementing this connection, we prove that certain solution-space geometries, called \emph{overlap-gap properties}~\cite{gamarnik2021overlap2}, continue to obstruct larger families of algorithms such as \emph{local quantum algorithms} and \emph{overlap-concentrated algorithms} on typical instances of such Max-CSPs~\cite{chou2022limitations, sandhu2023lowdegree}. We provide the exact approximation ratio at which the obstruction occurs, using a result of Huang and Sellke~\cite{huang2021tight}. In the absence of overlap-gap properties, we give unifying sum-of-squares (SoS) relaxations using novel maximum-entropy constraints for optimizing mean-field spin glasses on the sphere that match the conjectured optimal value achievable by any efficient algorithm~\cite{dorsi2022sumofsquares}. This relaxation can \emph{certify} the correct energy of the instances (with high probability) in the \emph{full-Replica Symmetry Breaking} regime, providing an efficient algorithmic proof of the Parisi formula on the sphere in this regime. In doing so, we circumvent prior certification lower-bounds against the standard SoS hierarchy on these problems~\cite{bhattiprolu2016sum} and provide a proof template to obtain low-degree SoS certificates for the spectral statistics of certain random matrices under the appropriate entropy constraints. \\ Our work adds to the growing body of recent results linking variants of the overlap-gap property to algorithmic hardness for increasingly powerful families of algorithms. Additionally, our work gives explicit negative results for quantum advantage on random optimization problems using NISQ algorithms and ports over various statistical physics concepts into the sum-of-squares framework, yielding further fine-grained understanding of the complexity landscape of typical instances of sparse Max-CSPs.

Related papers

Local Algorithms and the Failure of Log-Depth Quantum Advantage on Sparse Random CSPs

Antares Chen, Neng Huang, Kunal Marwaha

We construct and analyze a message-passing algorithm for random constraint satisfaction problems (CSPs) at large clause density, generalizing work of El Alaoui, Montanari, and Sellke for Maximum Cut [arXiv:2111.06813] through a connection between random CSPs and mean-field Ising spin glasses. For CSPs with even predicates, the algorithm asymptotically solves a stochastic optimal control problem dual to an extended Parisi variational principle. This gives an optimal fraction of satisfied constraints among algorithms obstructed by the branching overlap gap property of Huang and Sellke [arXiv:2110.07847], notably including the Quantum Approximate Optimization Algorithm and all quantum circuits on a bounded-degree architecture of up to $ε\cdot \log n$ depth.

arXiv:2310.01563•Leibniz international proceedings in informatics•Oct 2, 2023•1 citation

Limitations of Local Quantum Algorithms on Random MAX-k-XOR and Beyond

Chi-Ning Chou, Peter J. Love, Juspreet Singh Sandhu +1 more

We introduce a notion of \emph{generic local algorithm} which strictly generalizes existing frameworks of local algorithms such as \emph{factors of i.i.d.} by capturing local \emph{quantum} algorithms such as the Quantum Approximate Optimization Algorithm (QAOA). Motivated by a question of Farhi et al. [arXiv:1910.08187, 2019] we then show limitations of generic local algorithms including QAOA on random instances of constraint satisfaction problems (CSPs). Specifically, we show that any generic local algorithm whose assignment to a vertex depends only on a local neighborhood with $o(n)$ other vertices (such as the QAOA at depth less than $ε\log(n)$) cannot arbitrarily-well approximate boolean CSPs if the problem satisfies a geometric property from statistical physics called the coupled overlap-gap property (OGP) [Chen et al., Annals of Probability, 47(3), 2019]. We show that the random MAX-k-XOR problem has this property when $k\geq4$ is even by extending the corresponding result for diluted $k$-spin glasses. Our concentration lemmas confirm a conjecture of Brandao et al. [arXiv:1812.04170, 2018] asserting that the landscape independence of QAOA extends to logarithmic depth -- in other words, for every fixed choice of QAOA angle parameters, the algorithm at logarithmic depth performs almost equally well on almost all instances. One of these concentration lemmas is a strengthening of McDiarmid's inequality, applicable when the random variables have a highly biased distribution, and may be of independent interest.

arXiv:2108.06049•Leibniz international proceedings in informatics•Aug 13, 2021•12 citations

Bounds on approximating Max k XOR with quantum and classical local algorithms

Kunal Marwaha, Stuart Hadfield

We consider the power of local algorithms for approximately solving Max k XOR, a generalization of two constraint satisfaction problems previously studied with classical and quantum algorithms (MaxCut and Max E3LIN2). In Max k XOR each constraint is the XOR of exactly k variables and a parity bit. On instances with either random signs (parities) or no overlapping clauses and D+1 clauses per variable, we calculate the expected satisfying fraction of the depth-1 QAOA from Farhi et al [arXiv:1411.4028] and compare with a generalization of the local threshold algorithm from Hirvonen et al [arXiv:1402.2543]. Notably, the quantum algorithm outperforms the threshold algorithm for k > 4 .On the other hand, we highlight potential difficulties for the QAOA to achieve computational quantum advantage on this problem. We first compute a tight upper bound on the maximum satisfying fraction of nearly all large random regular Max k XOR instances by numerically calculating the ground state energy density P(k) of a mean-field k -spin glass [arXiv:1606.02365]. The upper bound grows with k much faster than the performance of both one-local algorithms. We also identify a new obstruction result for low-depth quantum circuits (including the QAOA) when k=3 , generalizing a result of Bravyi et al [arXiv:1910.08980] when k=2 . We conjecture that a similar obstruction exists for all k .

arXiv:2109.10833•Quantum•Jul 7, 2022•22 citations

Beating Random Assignment for Approximating Quantum 2-Local Hamiltonian Problems.

Ojas Parekh, Kevin Thompson

The quantum k-Local Hamiltonian problem is a natural generalization of classical constraint satisfaction problems (k-CSP) and is complete for QMA, a quantum analog of NP. Although the complexity of k-Local Hamiltonian problems has been well studied, only a handful of approximation results are known. For Max 2-Local Hamiltonian where each term is a rank 3 projector, a natural quantum generalization of classical Max 2-SAT, the best known approximation algorithm was the trivial random assignment, yielding a 0.75-approximation. We present the first approximation algorithm beating this bound, a classical polynomial-time 0.764-approximation. For strictly quadratic instances, which are maximally entangled instances, we provide a 0.801 approximation algorithm, and numerically demonstrate that our algorithm is likely a 0.821-approximation. We conjecture these are the hardest instances to approximate. We also give improved approximations for quantum generalizations of other related classical 2-CSPs. Finally, we exploit quantum connections to a generalization of the Grothendieck problem to obtain a classical constant-factor approximation for the physically relevant special case of strictly quadratic traceless 2-Local Hamiltonians on bipartite interaction graphs, where a inverse logarithmic approximation was the best previously known (for general interaction graphs). Our work employs recently developed techniques for analyzing classical approximations of CSPs and is intended to be accessible to both quantum information scientists and classical computer scientists.

arXiv:2012.12347•Leibniz international proceedings in informatics•Aug 1, 2021•5 citations

Spectral Certificates and Non-commutative Sum-of-Squares Lower Bounds for Hamiltonians

Nicholas Kocurek, Chinmay Nirkhe

A central question in quantum many-body physics is estimating the ground energy of a $k$-local Hamiltonian system. In this work, we present a spectral technique for certifying a lower bound on the ground energy of a random $n$-qubit Hamiltonian system defined as the sum of signed $k$-local Pauli operators. In particular, we prove that for any constant $\ell$, there exists an efficiently computable length $n^{O(\ell)}$ certificate that is always a lower bound on the ground energy with the promise that, with high probability over the random Hamiltonian distribution, the certificate value is an $\varepsilon$-good approximation of the true ground energy when the number of terms is sufficiently large. Second, we show by construction that this technique, while successful on average over random Hamiltonian systems, can fail to produce good certificates on worst-case instances. Our spectral technique for producing these certificates comes from extending classical results on $k$-XOR refutations to $k$-local Pauli Hamiltonians by crafting a quantum variant of the Kikuchi matrix for CSP refutations. To show the limitations of this technique, we prove non-commutative Sum-of-Squares lower bounds for worst-case signed $k$-local Pauli operators. More generally, we explore how the non-commutative Sum-of-Squares relaxation can be understood as augmenting the standard Sum-of-Squares relaxation with the commutation relations between the Pauli operators. We instantiate the resulting framework with a modification to prior quantum code-based NLTS Hamiltonians that yields stronger complexity guarantees for the low-energy space; our Hamiltonian family satisfies simultaneously (1) $Ω(\log n)$-circuit depth lower bounds for all low-energy states, (2) constant-gap NP-hardness to approximate the ground energy, and (3) a constant-gap non-commutative Sum-of-Squares integrality gap up to $Ω(n)$-levels.

cs.CCCross-listedarXiv:2511.02264•Nov 5, 2025•0 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 Unique-Games Conjecture (UGC)\cite{khot2002power} is a central open-question in theoretical computer science. If true, it implies optimal inapproximability results for \emph{every} Max-CSP. Despite impressive recent progress towards the conjecture\cite{khot2017independent, barak2018small, subhash2018pseudorandom, dinur2018non, dinur2018towards} there are no candidate instances for \emph{every} Max-CSP that would saturate the integrality gap of Raghavendra's UGC-optimal'' Semi-Definite Program (SDP)~\cite{raghavendra2008optimal}. In parallel, though it is known that reducing the factoring problem into Max-3-SAT can yield an efficient quantum algorithm for approximating conjectured classically hard Max-CSP instances~\cite{szegedy2022quantum}, no natural'' family of Max-CSP instances are known to give quantum advantage. Furthermore, it is an open-question whether efficient quantum algorithms can approximate Max-CSPs better than classical polynomial time algorithms on instances that saturate the integrality gap of Raghavendra's SDP~\cite{szegedy2022quantum}. A natural complementary starting point, therefore, is to investigate the complexity landscape of \emph{random} instances of \emph{sparse} Max-CSPs. \ \vspace{2mm} In this thesis, we make further progress in understanding the complexity landscape of such Max-CSPs. We prove that \emph{random} instances of \emph{all} Max-CSPs exhibit solution-space geometries akin to those of objects from statistical physics called \emph{mean-field spin glasses}\cite{jones2022random}. As a consequence of this connection, the optimal number of clauses satisfied by typical instances of such Max-CSPs can be expressed as a function of the \emph{ground state energy density} of the related mean-field spin glass. Complementing this connection, we prove that certain solution-space geometries, called \emph{overlap-gap properties}\cite{gamarnik2021overlap2}, continue to obstruct larger families of algorithms such as \emph{local quantum algorithms} and \emph{overlap-concentrated algorithms} on typical instances of such Max-CSPs~\cite{chou2022limitations, sandhu2023lowdegree}. We provide the exact approximation ratio at which the obstruction occurs, using a result of Huang and Sellke~\cite{huang2021tight}. In the absence of overlap-gap properties, we give unifying sum-of-squares (SoS) relaxations using novel maximum-entropy constraints for optimizing mean-field spin glasses on the sphere that match the conjectured optimal value achievable by any efficient algorithm~\cite{dorsi2022sumofsquares}. This relaxation can \emph{certify} the correct energy of the instances (with high probability) in the \emph{full-Replica Symmetry Breaking} regime, providing an efficient algorithmic proof of the Parisi formula on the sphere in this regime. In doing so, we circumvent prior certification lower-bounds against the standard SoS hierarchy on these problems~\cite{bhattiprolu2016sum} and provide a proof template to obtain low-degree SoS certificates for the spectral statistics of certain random matrices under the appropriate entropy constraints. \ Our work adds to the growing body of recent results linking variants of the overlap-gap property to algorithmic hardness for increasingly powerful families of algorithms. Additionally, our work gives explicit negative results for quantum advantage on random optimization problems using NISQ algorithms and ports over various statistical physics concepts into the sum-of-squares framework, yielding further fine-grained understanding of the complexity landscape of typical instances of sparse Max-CSPs.
We construct and analyze a message-passing algorithm for random constraint satisfaction problems (CSPs) at large clause density, generalizing work of El Alaoui, Montanari, and Sellke for Maximum Cut [arXiv:2111.06813] through a connection between random CSPs and mean-field Ising spin glasses. For CSPs with even predicates, the algorithm asymptotically solves a stochastic optimal control problem dual to an extended Parisi variational principle. This gives an optimal fraction of satisfied constraints among algorithms obstructed by the branching overlap gap property of Huang and Sellke [arXiv:2110.07847], notably including the Quantum Approximate Optimization Algorithm and all quantum circuits on a bounded-degree architecture of up to ε⋅log⁡nε\cdot \log nε⋅logn depth.
We introduce a notion of \emph{generic local algorithm} which strictly generalizes existing frameworks of local algorithms such as \emph{factors of i.i.d.} by capturing local \emph{quantum} algorithms such as the Quantum Approximate Optimization Algorithm (QAOA). Motivated by a question of Farhi et al. [arXiv:1910.08187, 2019] we then show limitations of generic local algorithms including QAOA on random instances of constraint satisfaction problems (CSPs). Specifically, we show that any generic local algorithm whose assignment to a vertex depends only on a local neighborhood with o(n)o(n)o(n) other vertices (such as the QAOA at depth less than εlog⁡(n)ε\log(n)εlog(n)) cannot arbitrarily-well approximate boolean CSPs if the problem satisfies a geometric property from statistical physics called the coupled overlap-gap property (OGP) [Chen et al., Annals of Probability, 47(3), 2019]. We show that the random MAX-k-XOR problem has this property when k≥4k\geq4k≥4 is even by extending the corresponding result for diluted kkk-spin glasses. Our concentration lemmas confirm a conjecture of Brandao et al. [arXiv:1812.04170, 2018] asserting that the landscape independence of QAOA extends to logarithmic depth -- in other words, for every fixed choice of QAOA angle parameters, the algorithm at logarithmic depth performs almost equally well on almost all instances. One of these concentration lemmas is a strengthening of McDiarmid's inequality, applicable when the random variables have a highly biased distribution, and may be of independent interest.
We consider the power of local algorithms for approximately solving Max k XOR, a generalization of two constraint satisfaction problems previously studied with classical and quantum algorithms (MaxCut and Max E3LIN2). In Max k XOR each constraint is the XOR of exactly k variables and a parity bit. On instances with either random signs (parities) or no overlapping clauses and D+1 clauses per variable, we calculate the expected satisfying fraction of the depth-1 QAOA from Farhi et al [arXiv:1411.4028] and compare with a generalization of the local threshold algorithm from Hirvonen et al [arXiv:1402.2543]. Notably, the quantum algorithm outperforms the threshold algorithm for k > 4 .On the other hand, we highlight potential difficulties for the QAOA to achieve computational quantum advantage on this problem. We first compute a tight upper bound on the maximum satisfying fraction of nearly all large random regular Max k XOR instances by numerically calculating the ground state energy density P(k) of a mean-field k -spin glass [arXiv:1606.02365]. The upper bound grows with k much faster than the performance of both one-local algorithms. We also identify a new obstruction result for low-depth quantum circuits (including the QAOA) when k=3 , generalizing a result of Bravyi et al [arXiv:1910.08980] when k=2 . We conjecture that a similar obstruction exists for all k .
The quantum k-Local Hamiltonian problem is a natural generalization of classical constraint satisfaction problems (k-CSP) and is complete for QMA, a quantum analog of NP. Although the complexity of k-Local Hamiltonian problems has been well studied, only a handful of approximation results are known. For Max 2-Local Hamiltonian where each term is a rank 3 projector, a natural quantum generalization of classical Max 2-SAT, the best known approximation algorithm was the trivial random assignment, yielding a 0.75-approximation. We present the first approximation algorithm beating this bound, a classical polynomial-time 0.764-approximation. For strictly quadratic instances, which are maximally entangled instances, we provide a 0.801 approximation algorithm, and numerically demonstrate that our algorithm is likely a 0.821-approximation. We conjecture these are the hardest instances to approximate. We also give improved approximations for quantum generalizations of other related classical 2-CSPs. Finally, we exploit quantum connections to a generalization of the Grothendieck problem to obtain a classical constant-factor approximation for the physically relevant special case of strictly quadratic traceless 2-Local Hamiltonians on bipartite interaction graphs, where a inverse logarithmic approximation was the best previously known (for general interaction graphs). Our work employs recently developed techniques for analyzing classical approximations of CSPs and is intended to be accessible to both quantum information scientists and classical computer scientists.
A central question in quantum many-body physics is estimating the ground energy of a kkk-local Hamiltonian system. In this work, we present a spectral technique for certifying a lower bound on the ground energy of a random nnn-qubit Hamiltonian system defined as the sum of signed kkk-local Pauli operators. In particular, we prove that for any constant ℓ\ellℓ, there exists an efficiently computable length nO(ℓ)n^{O(\ell)}nO(ℓ) certificate that is always a lower bound on the ground energy with the promise that, with high probability over the random Hamiltonian distribution, the certificate value is an ε\varepsilonε-good approximation of the true ground energy when the number of terms is sufficiently large. Second, we show by construction that this technique, while successful on average over random Hamiltonian systems, can fail to produce good certificates on worst-case instances. Our spectral technique for producing these certificates comes from extending classical results on kkk-XOR refutations to kkk-local Pauli Hamiltonians by crafting a quantum variant of the Kikuchi matrix for CSP refutations. To show the limitations of this technique, we prove non-commutative Sum-of-Squares lower bounds for worst-case signed kkk-local Pauli operators. More generally, we explore how the non-commutative Sum-of-Squares relaxation can be understood as augmenting the standard Sum-of-Squares relaxation with the commutation relations between the Pauli operators. We instantiate the resulting framework with a modification to prior quantum code-based NLTS Hamiltonians that yields stronger complexity guarantees for the low-energy space; our Hamiltonian family satisfies simultaneously (1) Ω(log⁡n)Ω(\log n)Ω(logn)-circuit depth lower bounds for all low-energy states, (2) constant-gap NP-hardness to approximate the ground energy, and (3) a constant-gap non-commutative Sum-of-Squares integrality gap up to Ω(n)Ω(n)Ω(n)-levels.
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.