A short proof of the Aaronson-Ambainis Conjecture via the completion framework
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 doma...