BQP vs. the Polynomial Hierarchy

E1002076

complexity theory paper computer science paper research paper

"BQP vs. the Polynomial Hierarchy" is a highly influential research paper by Scott Aaronson that investigates the relationship between quantum polynomial-time computation and the classical polynomial hierarchy, with major implications for our understanding of quantum advantage and complexity theory.

Try in SPARQL Jump to: Statements Referenced by

Statements (49)

Predicate	Object
instanceOf	complexity theory paper ⓘ computer science paper ⓘ research paper ⓘ
area	theoretical computer science ⓘ
author	Scott Aaronson NERFINISHED ⓘ
concernsClass	BPP NERFINISHED ⓘ BQP NERFINISHED ⓘ NP ⓘ P NERFINISHED ⓘ PH ⓘ PP NERFINISHED ⓘ P^{#P} NERFINISHED ⓘ
contribution	connects quantum query algorithms with the structure of the polynomial hierarchy ⓘ develops new techniques for proving oracle separations between quantum and classical complexity classes ⓘ formalizes problems designed to separate quantum computation from the polynomial hierarchy ⓘ provides evidence against the containment of BQP in PH in the relativized setting ⓘ
field	computational complexity theory ⓘ quantum computing ⓘ
focus	limitations of classical simulation of quantum algorithms ⓘ relationship between quantum polynomial time and the polynomial hierarchy ⓘ
implication	indicates that resolving BQP versus PH likely requires nonrelativizing techniques ⓘ suggests limitations of classical relativizing techniques for proving upper bounds on BQP ⓘ supports the view that quantum computers may solve problems beyond the reach of the polynomial hierarchy ⓘ
influenced	research on fine-grained separations between quantum and classical complexity classes ⓘ studies of random oracles in quantum complexity ⓘ subsequent work on quantum supremacy proposals ⓘ
influencedBy	earlier work on oracle separations in complexity theory ⓘ research on quantum query complexity ⓘ
language	English ⓘ
mainResult	argues that Fourier Checking is not in the polynomial hierarchy relative to a random oracle under plausible conjectures ⓘ exhibits an oracle relative to which BQP is not contained in the polynomial hierarchy ⓘ gives evidence that quantum computers can solve certain problems outside the polynomial hierarchy in the relativized world ⓘ introduces the Fourier Checking problem as a candidate for demonstrating quantum advantage over the polynomial hierarchy ⓘ shows that Fourier Checking is solvable in BQP relative to a random oracle ⓘ
status	highly cited ⓘ influential in quantum complexity theory ⓘ
topic	BQP NERFINISHED ⓘ Fourier Checking problem NERFINISHED ⓘ Fourier Fishing problem NERFINISHED ⓘ black-box separations ⓘ oracle separations ⓘ polynomial hierarchy ⓘ quantum advantage ⓘ query complexity ⓘ relativized complexity classes ⓘ
usesMethod	Fourier analysis of Boolean functions ⓘ oracle constructions ⓘ probabilistic method ⓘ query complexity lower bounds ⓘ

Referenced by (1)

Full triples — surface form annotated when it differs from this entity's canonical label.

Scott Aaronson → notableWork → BQP vs. the Polynomial Hierarchy ⓘ