- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- BIRS Workshop Lecture Videos /
- Oracle Separation of BQP and the Polynomial Hierarchy
Open Collections
BIRS Workshop Lecture Videos
BIRS Workshop Lecture Videos
Oracle Separation of BQP and the Polynomial Hierarchy Tal, Avishay
Description
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). Based on joint work with Ran Raz.
Item Metadata
Title |
Oracle Separation of BQP and the Polynomial Hierarchy
|
Creator | |
Publisher |
Banff International Research Station for Mathematical Innovation and Discovery
|
Date Issued |
2018-08-16T15:05
|
Description |
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).
Based on joint work with Ran Raz.
|
Extent |
54.0
|
Subject | |
Type | |
File Format |
video/mp4
|
Language |
eng
|
Notes |
Author affiliation: Stanford University
|
Series | |
Date Available |
2019-03-28
|
Provider |
Vancouver : University of British Columbia Library
|
Rights |
Attribution-NonCommercial-NoDerivatives 4.0 International
|
DOI |
10.14288/1.0377637
|
URI | |
Affiliation | |
Peer Review Status |
Unreviewed
|
Scholarly Level |
Postdoctoral
|
Rights URI | |
Aggregated Source Repository |
DSpace
|
Item Media
Item Citations and Data
Rights
Attribution-NonCommercial-NoDerivatives 4.0 International