Delphi.science

Proof of the Aaronson-Ambainis Conjecture: An Exposition

Source: arxiv.org/abs/2611.11626

Guy Blanc, Jordan Docter, Carmen Strassle, Li-Yang Tan

arXivarxiv/2611.11626Nov 8, 2026quant-phscore 0

We give an exposition of a recent proof of the Aaronson-Ambainis conjecture, which states that every degree-$d$ polynomial $p : \{0,1\}^n \to [0,1]$ has a variable of influence at least $\mathrm{poly}(\mathrm{Var}(p)/d)$. This implies that quantum query algorithms for decision problems can be efficiently simulated classically on most inputs. It also yields a near-equivalence between the status of the $\mathsf{BPP}$ vs. $\mathsf{BQP}$ problem in the random oracle and unrelativized worlds. We organize the proof around four main steps and discuss how each connects to the literature on the…

JSONText

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

API

curl /api/v1/records/arxiv/2611.11626
curl -X POST /api/v1/records/arxiv/2611.11626/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.11626/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'