Reproduce “BQP and the Polynomial Hierarchy” 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
Scott Aaronson
Scott Aaronson's 2009 paper introduces the 'Fourier Checking' and 'Fourier Fishing' oracle problems, providing the first formal, relativized evidence that BQP (Bounded-Error Quantum Polynomial-Time) is not contained within the Polynomial Hierarchy (PH). It posits the 'Generalized Linial-Nisan Conjecture,' which, if true, would imply an oracle separation of BQP from PH for decision problems.
Key insights
- The computational distinction between quantum algorithms and classical AC^0 circuits may lie in the 'low-fat' property of approximating polynomials, where quantum algorithms exploit 'massive cancellations' for efficient computation.
- The BQP vs. PH problem can be reduced to proving the Generalized Linial-Nisan Conjecture, which links quantum complexity theory to specific open problems in classical pseudorandomness and circuit lower bounds.
- New oracle problems like Fourier Fishing and Fourier Checking provide more structured and amenable testbeds for exploring separations between BQP and classical complexity classes.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.