{"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","summary":"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…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-11-08","reactions":{}}