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

Abstract

Assuming the Unique Games Conjecture, we show it is NP-hard to approximate MAX-3-CUT within a multiplicative factor of ${\alpha }_3+\epsilon$ for every $\epsilon >0$, where ${\alpha }_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 ${\alpha }_{\mathrm{BOV}}+\epsilon$ for every $\epsilon >0$, where ${\alpha }_{\mathrm{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\ge 3$.

46 pages