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

Abstract

The Gaussian noise stability of a function $f:{\mathbb{R}}^n\to \{-1,1\}$ is the expected value of $f(\mathbf{x})\cdot f(\mathbf{y})$ over $\ddot{I}$-correlated Gaussian random variables $\mathbf{x}$ and $\mathbf{y}$. Borell's inequality states that for $-1\le \ddot{I}\le 0$, this is minimized by the halfspace $f(x)=\mathrm{sign}(x_1)$. In this work, we generalize this result to hold for functions $f:{\mathbb{R}}^n\to S^{k-1}$ which output $k$-dimensional unit vectors. Our main conjecture, which we call the $\text{vector-valued Borell’s inequality}$, asserts that the expected value of $⟨f(\mathbf{x}),f(\mathbf{y})⟩$ is minimized by the function $f(x)=x_{\le k}/\Vert x_{\le k}\Vert$, where $x_{\le k}=(x_1,\dots ,x_k)$. 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$. As an application of this conjecture, we show that it implies several hardness of approximation results for a special case of the local Hamiltonian problem related to the anti-ferromagnetic Heisenberg model known as Quantum Max-Cut. This can be viewed as a natural quantum analogue of the classical Max-Cut problem and has been proposed as a useful testbed for developing algorithms. We show the following, assuming our conjecture: (1) The integrality gap of the basic SDP is $0.498$, matching an existing rounding algorithm. Combined with existing results, this shows that the basic SDP does not achieve the optimal approximation ratio. (2) It is Unique Games-hard (UG-hard) to compute a $(0.956+\epsilon )$-approximation to the value of the best product state, matching an existing approximation algorithm. (3) It is UG-hard to compute a $(0.956+\epsilon )$-approximation to the value of the best (possibly entangled) state.

76 pages; v3 treats the vector-valued Borell's inequality as a conjecture rather than a theorem, due to an error in previous versions