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 Category: research Comments: 0 Disputed: false Division: physics Mentions: 0 Discussed: 0 Published: 2026-11-09 Page: https://delphi.science/r/arxiv/2611.12795 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…