We prove a vector-valued inequality for the Gaussian noise stability (i.e. we prove a vector-valued Borell inequality) for Euclidean functions taking values in the two-dimensional sphere, for all correlation parameters at most 1/10 in absolute value. This inequality was conjectured (for all correlation parameters at most 1 in absolute value) by Hwang, Neeman, Parekh, Thompson and Wright. Such an inequality is needed to prove sharp computational hardness of the product state Quantum MAX-CUT problem, assuming the unique games conjecture. In fact, assuming the unique games conjecture, we show that the product state of Quantum MAX-CUT is NP-hard to approximate within a multiplicative factor of 0.9859. In contrast, a polynomial time algorithm is known with approximation factor 0.956….
We prove a vector-valued inequality for the Gaussian noise stability (i.e. we prove a vector-valued Borell inequality) for Euclidean functions taking values in the two-dimensional sphere, for all correlation parameters at most 1/10 in absolute value. This inequality was conjectured (for all correlation parameters at most 1 in absolute value) by Hwang, Neeman, Parekh, Thompson and Wright. Such an inequality is needed to prove sharp computational hardness of the product state Quantum MAX-CUT problem, assuming the unique games conjecture. In fact, assuming the unique games conjecture, we show that the product state of Quantum MAX-CUT is NP-hard to approximate within a multiplicative factor of 0.9859. In contrast, a polynomial time algorithm is known with approximation factor 0.956….
Assuming the Unique Games Conjecture, we show it is NP-hard to approximate MAX-3-CUT within a multiplicative factor of α3+ε for every ε>0, where α3≈.83600811464 is the approximation ratio of Frieze-Jerrum's polynomial-time algorithm from 1995. That is, we prove sharp hardness of approximation for MAX-3-CUT. This result resolves a conjecture of Khot-Kindler-Mossel-O'Donnell from 2004 by proving the three candidate Plurality is Stablest Conjecture for correlations in [−1/2,2/5] and generalizes the Majority is Stablest Theorem of Mossel-O'Donnell-Oleszkiewicz [Annals of Math, 2010].
With a similar strategy we prove: assuming the Unique Games Conjecture, it is NP-hard to approximate the product-state value of Quantum MAX-CUT within a multiplicative factor of αBOV+ε for every ε>0, where αBOV≈0.9563372685 is the approximation ratio of the Briët-de Oliveira Filho-Vallentin algorithm. This sharp hardness result completes the conjectured hardness of Hwang-Neeman-Parekh-Thompson-Wright from 2021 by proving their Sk−1-valued Borell inequality for correlations in [−.5843,.5843] for all k≥3.
The Gaussian noise stability of a function f: ℝn → {-1,1} is the expected value of f (x) · f (y) over ρ-correlated Gaussian random variables x and y. Borell's inequality states that for —1 ≤ ρ ≤ 0, this is minimized by the mean-zero halfspace f (x) = sign(x1). In this work, we conjecture that a natural generalization of this result holds for functions f: ℝn → Sk-1 which output k-dimensional unit vectors. Our main conjecture, which we call the vector-valued Borell's inequality, asserts that the expectation Ex~ρy 〈f(x), f(y)〉 is minimized by the function f (x) = x≤k/||x≤k||, where x≤k = (x1,…, xk). We give several pieces of evidence in favor of this conjecture, including a proof that it does indeed hold in the special case of n = k.
We resolve the approximability of the maximum energy of the Quantum Max Cut (QMC) problem using product states. A classical 0.498-approximation, using a basic semidefinite programming relaxation, is known for QMC, paralleling the celebrated 0.878-approximation for classical Max Cut. For Max Cut, improving the 0.878-approximation is Unique-Games-hard (UG-hard), and one might expect that improving the 0.498-approximation is UG-hard for QMC. In contrast, we give a classical 1/2-approximation for QMC that is unconditionally optimal, since simple examples exhibit a gap of 1/2 between the energies of an optimal product state and general quantum state. Our result relies on a new nonlinear monogamy of entanglement inequality on a triangle that is derived from the second level of the quantum Lasserre hierarchy. This inequality also applies to the quantum Heisenberg model, and our results generalize to instances of Max 2-Local Hamiltonian where each term is positive and has no 1-local parts. Finally, we give further evidence that product states are essential for approximations of 2-Local Hamiltonian.
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.
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 ∞. We apply these results to establish concrete depth lower bounds for popular quantum algorithms for preparing near-optimal states for this problem.
We unconditionally prove that it is NP-hard to compute a constant multiplicative approximation to the QUANTUM MAX-CUT problem on an unweighted graph of constant bounded degree. The proof works in two stages: first we demonstrate a generic reduction to computing the optimal value of a quantum problem, from the optimal value over product states. Then we prove an approximation preserving reduction from MAX-CUT to PRODUCT-QMC the product state version of QUANTUM MAX-CUT. More precisely, in the second part, we construct a PTAS reduction from MAX-CUTk (the rank-k constrained version of MAX-CUT) to MAX-CUTk+1, where MAX-CUT and PRODUCT-QMC coincide with MAX-CUT1 and MAX-CUT3 respectively. We thus prove that Max-Cutk is APX-complete for all constant k.