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

The Gaussian noise stability of a function f : R 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(x 1 ). In this work, we conjecture that a natural generalization of this result holds for functions f : R n → S k-1 which output k-dimensional unit vectors. Our main conjecture, which we call the vector-valued Borell's inequality, asserts that the expectation E x∼ρy f (x), f (y) is minimized by the function f (x) = x ≤k / x ≤k , where x ≤k = (x 1 , . . . , 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 the vector-valued Borell's inequality: