Reproduce “Proof of the Aaronson-Ambainis Conjecture: An Exposition” on OpenResearch

Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.

Universal app for Apple silicon and Intel. Requires macOS 11 or later.

About this paper

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

The authors prove that every bounded polynomial of degree at most d on Boolean inputs has a coordinate whose influence is at least Ω(Var(p)^8/d^12), where influence is the expected squared change when that bit flips. They use this result to establish the Aaronson–Ambainis conjecture for decision problems: classical algorithms can approximate quantum acceptance probabilities with polynomially many queries on most inputs, not for search problems.

Summary by alphaXiv.

Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.