{"id":"arxiv/2611.09773","url":"https://arxiv.org/abs/2611.09773","tags":["cs.CC","quant-ph"],"score":0,"title":"A proof of the Aaronson-Ambainis conjecture","domain":"cs.CC","source":"arxiv","authors":["David Turturean"],"reviews":0,"subject":"cs.CC","summary":"Aaronson and Ambainis conjectured that every bounded polynomial of low degree on the discrete cube has an influential variable. They showed that the conjecture implies that the acceptance probability of every quantum algorithm making $T$ queries can be approximated on most inputs by a classical algorithm making $\\mathrm{poly}(T)$ queries. We prove their conjecture: every function $f\\colon\\{-1,1\\}^n\\to[-1,1]$ of degree at most $d\\ge1$ has a variable of influence at least $c\\,\\operatorname{Var}(f)^{5/2}/d^{6}$, where $c>0$ is an absolute constant. In the original formulation, for polynomials…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-11-06","reactions":{}}