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

2026/07/31 by Steven Heilman
Computer Science · Mathematics · #cs.CC #math.CO #math.PR

paper · pdf

46 pages

arxiv created 2026/07/31 · arxiv updated 2026/08/04

Abstract

Assuming the Unique Games Conjecture, we show it is NP-hard to approximate MAX-3-CUT within a multiplicative factor of α₃+ε for every ε>0, where α₃≈.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}≈ 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≥3.

Citations

• Quantum Max-Cut is NP hard to approximate
• Derandomised tensor product gap amplification for quantum Hamiltonians
• Reinforced Generation of Combinatorial Structures: Hardness of Approximation
• Improved Algorithms for Quantum MaxCut via Partially Entangled Matchings
• Tight approximability of MAX 2-SAT and relatives, under UGC
• Approximation Algorithms for Quantum Max-d-Cut
• Sphere Valued Noise Stability and Quantum MAX-CUT Hardness
• Three Candidate Plurality is Stablest for Correlations at most 1/10
• Hyperstable Sets with Voting and Algorithmic Hardness Applications
• Unique Games hardness of Quantum Max-Cut, and a conjectured vector-valued Borell's inequality
• The complexity of antiferromagnetic interactions and 2D lattices
• Standard Simplices and Pluralities are Not the Most Noise Stable
• Complexity classification of local Hamiltonian problems
• Analytical Approach to Parallel Repetition
• New NP-hardness results for 3-Coloring and 2-to-1 Label Cover
• Robust Optimality of Gaussian Noise Stability
• Sharp kernel clustering algorithms and their associated Grothendieck inequalities
• Maximally Stable Gaussian Partitions with Discrete Applications
• Noise stability of functions with low influences: invariance and optimality
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Spherical rearrangements, subharmonic functions, and ∗-functions in n-space