Skip to content
Preprint

A short proof of the Aaronson-Ambainis Conjecture via the completion framework

Nov 2026 · 0 citations · 4 references
Physics Computer Science

Abstract

We give a short proof of the Aaronson-Ambainis conjecture. If a partial Boolean function $f$ is defined on a $\delta$-fraction of all $n$-bit strings and have quantum query complexity $Q(f)$, then, for every $0<\epsilon<1$, a deterministic algorithm computes $f$ correctly on at least a $1-\epsilon$ fraction of its domain using $O( Q(f)^6 / (\epsilon \delta)^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 self-contained proof. We also derive the stronger variant of the Aaronson-Ambainis Conjecture, the bounded-polynomial influence conjecture, from our main result in the appendix.

View source

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.