We're sorry but this page doesn't work properly without JavaScript enabled. Please enable it to continue.
Feedback

Oracle Separation of BQP and the PH

00:00
playback rate
1
subtitles
off
playback rate
0.25
0.5
0.75
1
1.25
1.5
1.75
2
quality
576p
0
 Cite
 Share
 Related Material
 Download Purchase
No logo availableBanff International Research Station (BIRS) for Mathematical Innovation and Discovery
 Tal, Avishay

Formal Metadata

Title
Oracle Separation of BQP and the PH
Alternative Title
Oracle Separation of BQP and the Polynomial Hierarchy
Title of Series
Number of Parts
17
Author
Contributors
License
CC Attribution - NonCommercial - NoDerivatives 4.0 International:
You are free to use, copy, distribute and transmit the work or content in unchanged form for any legal and non-commercial purpose as long as the work is attributed to the author in the manner specified by the author or licensor.
Identifiers
Publisher
Release Date
Language

Content Metadata

Subject Area
Genre
Abstract
We present an oracle, A, relative to which BQP^A is not contained in PH^A. Following the approach of Aaronson [STOC, 2010], our oracle separation is obtained by finding a distribution D over Boolean strings of length N such that: (1) There exists a quantum algorithm that runs in time polylog(N) and distinguishes between D and the uniform distribution over Boolean strings of length N. (2) No AC0 circuit of quasi-polynomial size can distinguish between D and the uniform distribution with advantage better than polylog(N)/sqrt(N).