SPHERE VALUED NOISE STABILITY AND QUANTUM MAX-CUT HARDNESS

• 成果类型: Article
• 署名作者: Heilman, Steven
• 署名单位: University of Southern California
• 刊物名称: ANNALS OF PROBABILITY
• ISSN/ISSBN: 0091-1798
• DOI: 10.1214/24-AOP1732
• 发表日期: 2025
• 页码: 1197-1222
• 关键词: approximation algorithms

摘要

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 son 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 0.9859. In contrast, a polynomial time algorithm is known with approximation factor 0.956. . ..