2023/06/06 by Steven Heilman, Heilman, Steven · 1 citation
Computer Science · #Bayesian Modeling and Causal Inference #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #FOS: Physical sciences #Machine Learning and Algorithms #Probability (math.PR) #Quantum Physics (quant-ph)
paper · pdf · doi:10.48550/arxiv.2306.03912
openalex publication_date 2023/06/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We prove a vector-valued inequality for the Gaussian noise stability (i.e. we prove a vector-valued Borell inequality) for Euclidean functions taking values in the two-dimensional sphere, for all correlation parameters at most 1/10 in absolute value. This inequality was conjectured (for all correlation parameters at most 1 in absolute value) by Hwang, Neeman, Parekh, Thompson and Wright. Such an inequality is needed to prove sharp computational hardness of the product state Quantum MAX-CUT problem, assuming the Unique Games Conjecture. In fact, assuming the Unique Games Conjecture, we show that the product state of Quantum MAX-CUT is NP-hard to approximate within a multiplicative factor of .9859. In contrast, a polynomial time algorithm is known with approximation factor .956….