Id: arxiv/2611.11626 Url: https://arxiv.org/abs/2611.11626 Tags: quant-ph, cs.CC Score: 0 Title: Proof of the Aaronson-Ambainis Conjecture: An Exposition Domain: quant-ph Source: arxiv Authors: Guy Blanc, Jordan Docter, Carmen Strassle, Li-Yang Tan Reviews: 0 Subject: quant-ph Category: research Comments: 0 Disputed: false Division: physics Mentions: 0 Discussed: 0 Published: 2026-11-08 Page: https://delphi.science/r/arxiv/2611.11626 We give an exposition of a recent proof of the Aaronson-Ambainis conjecture, which states that every degree-$d$ polynomial $p : \{0,1\}^n \to [0,1]$ has a variable of influence at least $\mathrm{poly}(\mathrm{Var}(p)/d)$. This implies that quantum query algorithms for decision problems can be efficiently simulated classically on most inputs. It also yields a near-equivalence between the status of the $\mathsf{BPP}$ vs. $\mathsf{BQP}$ problem in the random oracle and unrelativized worlds. We organize the proof around four main steps and discuss how each connects to the literature on the…