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:2111.01254 · Society for Industrial and Applied Mathematics eBooks

Unique Games hardness of Quantum Max-Cut, and a conjectured vector-valued Borell's inequality

Yeongwoo Hwang, Joe Neeman, Ojas Parekh, Kevin Thompson, John Wright

Published Jan 1, 2023• 31 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1137/1.9781611977554.ch48

Related papers

Sphere valued noise stability and quantum MAX-CUT hardness

Steven Heilman

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

arXiv:2306.03912•The Annals of Probability•Jul 1, 2025•0 citations

Sharp Hardness for MAX-3-CUT and Quantum MAX-CUT

Steven Heilman

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\approx.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 $α_{\rm BOV}+ε$ for every $ε>0$, where $α_{\rm BOV}\approx 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 $S^{k-1}$-valued Borell inequality for correlations in $[-.5843,.5843]$ for all $k\geq3$.

cs.CCCross-listedarXiv:2608.00333•Aug 4, 2026•4 citations

A conjecture on a tight norm inequality in the finite-dimensional l_p

A. S. Holevo, A. V. Utkin

We suggest a tight inequality for norms in $d$-dimensional space $l_p $ which has simple formulation but appears hard to prove. We give a proof for $d=3$ and provide a detailed numerical check for $d\leq 200$ confirming the conjecture. We conclude with a brief survey of solutions for kin problems which anyhow concern minimization of the output entropy of certain quantum channel and rely upon the symmetry properties of the problem. Key words and phrases: $l_p $-norm, Rényi entropy, tight inequality, maximization of a convex function.

quant-pharXiv:2603.24017•Mar 26, 2026

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

Sandhu, Juspreet Singh

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.

•Jan 1, 2023•0 citations

Near-optimal Quantum algorithms for multivariate mean estimation

Arjan Cornelissen, Yassine Hamoudi, Sofiène Jerbi

We propose the first near-optimal quantum algorithm for estimating in Euclidean norm the mean of a vector-valued random variable with finite mean and covariance. Our result aims at extending the theory of multivariate sub-Gaussian estimators [Lugosi and Mendelson, 2019] to the quantum setting. Unlike classically, where any univariate estimator can be turned into a multivariate estimator with at most a logarithmic overhead in the dimension, no similar result can be proved in the quantum setting. Indeed, [Heinrich, 2004] ruled out the existence of a quantum advantage for the mean estimation problem when the sample complexity is smaller than the dimension. Our main result is to show that, outside this low-precision regime, there does exist a quantum estimator that outperforms any classical estimator. More precisely, we prove that the approximation error can be decreased by a factor of about the square root of the ratio between the dimension and the sample complexity. Our approach is substantially more involved than in the univariate setting, where most quantum estimators rely only on phase estimation. We exploit a variety of additional algorithmic techniques such as linear amplitude amplification, the Bernstein-Vazirani algorithm, and quantum singular value transformation. Our analysis is also deeply rooted in proving concentration inequalities for multivariate truncated statistics. Finally, we describe several applications of our algorithms, notably in measuring the expectation values of commuting observables and in the field of machine learning.

arXiv:2111.09787•ACM Symposium on Theory of Computing (STOC)•Jun 9, 2022•37 citations

Quantum Gaussian maximizers and log-Sobolev inequalities

Alexander Semenovich Holevo, Sergey N. Filippov

Letters in Mathematical Physics•Jan 19, 2023•8 citations
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 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+εα_3+εα3​+ε for every ε>0ε>0ε>0, where α3≈.83600811464α_3\approx.83600811464α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][-1/2,2/5][−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+εα_{\rm BOV}+εαBOV​+ε for every ε>0ε>0ε>0, where αBOV≈0.9563372685α_{\rm BOV}\approx 0.9563372685α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−1S^{k-1}Sk−1-valued Borell inequality for correlations in [−.5843,.5843][-.5843,.5843][−.5843,.5843] for all k≥3k\geq3k≥3.
We suggest a tight inequality for norms in ddd-dimensional space $l_p $ which has simple formulation but appears hard to prove. We give a proof for d=3d=3d=3 and provide a detailed numerical check for d≤200d\leq 200d≤200 confirming the conjecture. We conclude with a brief survey of solutions for kin problems which anyhow concern minimization of the output entropy of certain quantum channel and rely upon the symmetry properties of the problem. Key words and phrases: $l_p $-norm, Rényi entropy, tight inequality, maximization of a convex function.
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 propose the first near-optimal quantum algorithm for estimating in Euclidean norm the mean of a vector-valued random variable with finite mean and covariance. Our result aims at extending the theory of multivariate sub-Gaussian estimators [Lugosi and Mendelson, 2019] to the quantum setting. Unlike classically, where any univariate estimator can be turned into a multivariate estimator with at most a logarithmic overhead in the dimension, no similar result can be proved in the quantum setting. Indeed, [Heinrich, 2004] ruled out the existence of a quantum advantage for the mean estimation problem when the sample complexity is smaller than the dimension. Our main result is to show that, outside this low-precision regime, there does exist a quantum estimator that outperforms any classical estimator. More precisely, we prove that the approximation error can be decreased by a factor of about the square root of the ratio between the dimension and the sample complexity. Our approach is substantially more involved than in the univariate setting, where most quantum estimators rely only on phase estimation. We exploit a variety of additional algorithmic techniques such as linear amplitude amplification, the Bernstein-Vazirani algorithm, and quantum singular value transformation. Our analysis is also deeply rooted in proving concentration inequalities for multivariate truncated statistics. Finally, we describe several applications of our algorithms, notably in measuring the expectation values of commuting observables and in the field of machine learning.