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.
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 ε⋅logn depth.
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 .
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≥4 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.
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.
The ability of the quantum approximate optimization algorithm (QAOA) to deliver a quantum advantage on combinatorial optimization problems is still unclear. Recently, a scaling advantage over a classical solver was postulated to exist for random 8-SAT at the satisfiability threshold. At the same time, the viability of quantum error mitigation for deep circuits on near-term devices has been put into doubt. Here we analyze the QAOA's performance on random Max- k XOR as a function of k and the clause-to-variable ratio. As a classical benchmark, we use the mean-field approximate optimization algorithm and find that it performs better than or equal to the QAOA on average. Still, for large k and numbers of layers p , there may remain a window of opportunity for the QAOA. However, by extrapolating our numerical results, we find that reaching high levels of satisfaction would require extremely large p , which must be considered rather difficult both in the variational context and on near-term devices.
We present a quantum algorithm that has rigorous runtime guarantees for several families of binary optimization problems, including Quadratic Unconstrained Binary Optimization (QUBO), Ising spin glasses (p-spin model), and k-local constraint satisfaction problems (k-CSP). We show that either (a) the algorithm finds the optimal solution in time O*(2(0.5−c)n) for an n-independent constant c, a 2cn advantage over Grover’s algorithm; or (b) there are sufficiently many low-cost solutions such that classical random guessing produces a (1−η) approximation to the optimal cost value in sub-exponential time for arbitrarily small choice of η. Additionally, we show that for a large fraction of random instances from the k-spin model and for any fully satisfiable or slightly frustrated k-CSP formula, statement (a) is the case. The algorithm and its analysis are largely inspired by Hastings’ short-path algorithm.
A central question in quantum information theory is the circuit complexity of states arising from standard many-body models. We study this question for quantum p-spin glasses, random Hamiltonians whose interactions act on p-tuples of qubits through Pauli strings. Anschuetz, Gamarnik, and Kiani (arXiv:2404.07231) showed that the optimum energy is separated from the best energy achievable by product states. This leaves open whether shallow circuits can close the gap, since even depth-one circuits can generate entanglement.
We show that the entanglement needed to close the product-state gap cannot be generated at shallow depth. When the average interaction degree grows with n, we prove that, for all sufficiently large fixed p, any circuit preparing an n-qubit state whose normalized energy is within a fixed positive constant of the optimum must have depth Ωp(logn). In the bounded-average-degree regime, we prove a fixed-depth obstruction: for every fixed D, a sufficiently large degree prefactor rules out depth-D preparation of near-ground states. Both results hold uniformly over circuits with an arbitrary number of ancilla qubits.
Our results give an obstruction in the spirit of the No Low-Energy Trivial States problem of Freedman and Hastings (arXiv:1301.1363), but for random quantum spin glasses rather than code-based Hamiltonians such as those of Anshu, Breuckmann, and Nirkhe (arXiv:2206.13228), whose ground states admit polynomial-size preparation circuits. This setting opens a probabilistic route to NLTS-like questions: we recast state-preparation lower bounds for random quantum Hamiltonians as uniform control of Gaussian processes indexed by shallow circuits.