arXiv:2611.12795 · v1

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

通过补全框架对Aaronson-Ambainis猜想的简短证明

首次提交 2026-11-10 02:01

版本更新 2026-11-10 02:01

雷达观测 2026-11-10 15:22

摘要

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 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.

作者备注：7 pages