{"id":"arxiv/2611.12795","url":"https://arxiv.org/abs/2611.12795","tags":["quant-ph","cs.CC"],"score":0,"title":"A short proof of the Aaronson-Ambainis Conjecture via the completion framework","domain":"quant-ph","source":"arxiv","authors":["Thomas Huffstutler","David Miloschewsky","Supartha Podder"],"reviews":0,"subject":"quant-ph","summary":"We give a short proof of the Aaronson-Ambainis conjecture. If a partial Boolean function $f$ is defined on a $δ$-fraction of all $n$-bit strings and have quantum query complexity $Q(f)$, then, for every $0<ε<1$, a deterministic algorithm computes $f$ correctly on at least a $1-ε$ fraction of its domain using $O( Q(f)^6 / (εδ)^2)$ queries. Our proof uses the completion framework and establishes a more general bound in terms of the classical adversary measure. The only result we use from Turturean's recent proof is a special case of his certificate inequality, for which we provide a…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-11-09","reactions":{}}