Lune

SODA2023Top-tier venue

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

Yeongwoo Hwang, Joe Neeman, Ojas Parekh, Kevin Thompson, John Wright

Abstract

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:

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

2 top-tier papers have cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers2

  1. Approximation Algorithms for Noncommutative CSPsEric Culf, Hamoon Mousavi, Taro SpirigFOCS 2024 · 7 citations
  2. The Quantum and Classical Streaming Complexity of Quantum and Classical Max-CutJohn Kallaugher, Ojas ParekhFOCS 2022 · 1 citation

Builds on1

  1. Optimizing strongly interacting fermionic HamiltoniansMatthew B. Hastings, Ryan O'DonnellSTOC 2022 · 30 citations

Related papers

  1. Noise Stability on the Boolean Hypercube via a Renormalized Brownian MotionRonen Eldan, Dan Mikulincer, Prasad RaghavendraSTOC 2023 · 4 citations
  2. An Invariance Principle for the Multi-slice, with ApplicationsMark Braverman, Subhash Khot, Noam Lifshitz, Dor MinzerFOCS 2021 · 29 citations
  3. Exponential improvements to the average-case hardness of BosonSamplingAdam Bouland, Ishaun Datta, Bill Fefferman, Felipe HernandezFOCS 2025 · 1 citation
  4. Tight Running Time Lower Bounds for Strong Inapproximability of Maximum k-Coverage, Unique Set Cover and Related Problems (via t-Wise Agreement Testing Theorem)Pasin ManurangsiSODA 2020 · 30 citations
  5. Nearly All k-SAT Functions Are UnateJózsef Balogh, Dingding Dong, Bernard Lidický, Nitya Mani et al.STOC 2023 · 4 citations
Dusk over the sea between two cliffs drawn in fine vertical lines