TY - ELEC
AU - Tal, Avishay
PY - 2018
TI - Oracle Separation of BQP and the Polynomial Hierarchy
LA - eng
M3 - Moving Image
AB - 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.
N2 - 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.
UR - https://open.library.ubc.ca/collections/48630/items/1.0377637
ER - End of Reference