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:2608.00333

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

Steven Heilman

cs.CCmath.COmath.PRquant-phSubmitted Jul 31, 2026• Announced Aug 4, 2026• 4 citations
arXivHTMLPDF

Abstract

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

Comments
46 pages

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

The classical limit of Quantum Max-Cut

Vir B. Bulchandani, Stephen Piddock

It is well-known in physics that the limit of large quantum spin $S$ should be understood as a semiclassical limit. This raises the question of whether such emergent classicality facilitates the approximation of computationally hard quantum optimization problems, such as the local Hamiltonian problem. We demonstrate this explicitly for spin-$S$ generalizations of Quantum Max-Cut ($\mathrm{QMaxCut}_S$), equivalent to the problem of finding the ground state energy of an arbitrary spin-$S$ quantum Heisenberg antiferromagnet ($\mathrm{QHA}_S$). We prove that approximating the value of $\mathrm{QHA}_S$ to inverse polynomial accuracy is QMA-complete for all $S$, extending previous results for $S=1/2$. We also present two distinct families of classical approximation algorithms for $\mathrm{QMaxCut}_S$ based on rounding the output of a semidefinite program to a product of Bloch coherent states. The approximation ratios for both our proposed algorithms strictly increase with $S$ and converge to the Briët-Oliveira-Vallentin approximation ratio $α_{\mathrm{BOV}} \approx 0.956$ from below as $S \to \infty$.

arXiv:2401.12968•Jan 23, 2024•1 citation

Quantum Max-Cut is NP hard to approximate

Stephen Piddock

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-CUT$_k$ (the rank-k constrained version of MAX-CUT) to MAX-CUT$_{k+1}$, where MAX-CUT and PRODUCT-QMC coincide with MAX-CUT$_1$ and MAX-CUT$_3$ respectively. We thus prove that Max-Cut$_k$ is APX-complete for all constant $k$.

arXiv:2510.07995•Oct 9, 2025•10 citations

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

Yeongwoo Hwang, Joe Neeman, Ojas Parekh +2 more

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.

arXiv:2111.01254•Society for Industrial and Applied Mathematics eBooks•Jan 1, 2023•31 citations

An Approximation Algorithm for the MAX-2-Local Hamiltonian Problem

Hallgren, Sean, Lee, Eunou, Ojas Parekh

We present a classical approximation algorithm for the MAX-2-Local Hamiltonian problem. This is a maximization version of the QMA-complete 2-Local Hamiltonian problem in quantum computing, with the additional assumption that each local term is positive semidefinite. The MAX-2-Local Hamiltonian problem generalizes NP-hard constraint satisfaction problems, and our results may be viewed as generalizations of approximation approaches for the MAX-2-CSP problem. We work in the product state space and extend the framework of Goemans and Williamson for approximating MAX-2-CSPs. The key difference is that in the product state setting, a solution consists of a set of normalized 3-dimensional vectors rather than boolean numbers, and we leverage approximation results for rank-constrained Grothendieck inequalities. For MAX-2-Local Hamiltonian we achieve an approximation ratio of 0.328. This is the first example of an approximation algorithm beating the random quantum assignment ratio of 0.25 by a constant factor.

Leibniz international proceedings in informatics•Jan 1, 2020•7 citations

An Optimal Product-State Approximation for 2-Local Quantum Hamiltonians with Positive Terms

Ojas Parekh, Thompson, Kevin

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.

arXiv:2206.08342•Jun 16, 2022•50 citations
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 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….
It is well-known in physics that the limit of large quantum spin SSS should be understood as a semiclassical limit. This raises the question of whether such emergent classicality facilitates the approximation of computationally hard quantum optimization problems, such as the local Hamiltonian problem. We demonstrate this explicitly for spin-SSS generalizations of Quantum Max-Cut (QMaxCutS\mathrm{QMaxCut}_SQMaxCutS​), equivalent to the problem of finding the ground state energy of an arbitrary spin-SSS quantum Heisenberg antiferromagnet (QHAS\mathrm{QHA}_SQHAS​). We prove that approximating the value of QHAS\mathrm{QHA}_SQHAS​ to inverse polynomial accuracy is QMA-complete for all SSS, extending previous results for S=1/2S=1/2S=1/2. We also present two distinct families of classical approximation algorithms for QMaxCutS\mathrm{QMaxCut}_SQMaxCutS​ based on rounding the output of a semidefinite program to a product of Bloch coherent states. The approximation ratios for both our proposed algorithms strictly increase with SSS and converge to the Briët-Oliveira-Vallentin approximation ratio αBOV≈0.956α_{\mathrm{BOV}} \approx 0.956αBOV​≈0.956 from below as S→∞S \to \inftyS→∞.
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_kk​ (the rank-k constrained version of MAX-CUT) to MAX-CUTk+1_{k+1}k+1​, where MAX-CUT and PRODUCT-QMC coincide with MAX-CUT1_11​ and MAX-CUT3_33​ respectively. We thus prove that Max-Cutk_kk​ is APX-complete for all constant kkk.
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 present a classical approximation algorithm for the MAX-2-Local Hamiltonian problem. This is a maximization version of the QMA-complete 2-Local Hamiltonian problem in quantum computing, with the additional assumption that each local term is positive semidefinite. The MAX-2-Local Hamiltonian problem generalizes NP-hard constraint satisfaction problems, and our results may be viewed as generalizations of approximation approaches for the MAX-2-CSP problem. We work in the product state space and extend the framework of Goemans and Williamson for approximating MAX-2-CSPs. The key difference is that in the product state setting, a solution consists of a set of normalized 3-dimensional vectors rather than boolean numbers, and we leverage approximation results for rank-constrained Grothendieck inequalities. For MAX-2-Local Hamiltonian we achieve an approximation ratio of 0.328. This is the first example of an approximation algorithm beating the random quantum assignment ratio of 0.25 by a constant factor.
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.