BQP and the Polynomial Hierarchy

The relationship between BQP and PH has been an open problem since the earliest days of quantum computing. We present evidence that quantum computers can solve problems outside the entire polynomial hierarchy, by relating this question to topics in circuit complexity, pseudorandomness, and Fourier a...

Disgrifiad llawn

Manylion Llyfryddiaeth
Prif Awdur: Aaronson, Scott
Awduron Eraill: Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science
Fformat: Erthygl
Iaith:en_US
Cyhoeddwyd: Association for Computing Machinery 2010
Mynediad Ar-lein:http://hdl.handle.net/1721.1/54236
https://orcid.org/0000-0003-1333-4045