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

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.