"Non UBC"@en .
"DSpace"@en .
"Tal, Avishay"@en .
"2019-03-28T10:36:09Z"@en .
"2018-08-16T15:05"@en .
"We present an oracle, A, relative to which BQP^A is not contained in PH^A.\n\nFollowing the approach of Aaronson [STOC, 2010], our oracle separation is obtained by finding a distribution D over Boolean strings of length N such that:\n(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.\n(2) No AC0 circuit of quasi-polynomial size can distinguish between D and the uniform distribution with advantage better than\npolylog(N)/sqrt(N).\n\nBased on joint work with Ran Raz."@en .
"https://circle.library.ubc.ca/rest/handle/2429/69321?expand=metadata"@en .
"54.0"@en .
"video/mp4"@en .
""@en .
"Author affiliation: Stanford University"@en .
"Oaxaca (Mexico : State)"@en .
"10.14288/1.0377637"@en .
"eng"@en .
"Unreviewed"@en .
"Vancouver : University of British Columbia Library"@en .
"Banff International Research Station for Mathematical Innovation and Discovery"@en .
"Attribution-NonCommercial-NoDerivatives 4.0 International"@en .
"http://creativecommons.org/licenses/by-nc-nd/4.0/"@en .
"Postdoctoral"@en .
"BIRS Workshop Lecture Videos (Oaxaca (Mexico : State))"@en .
"Mathematics"@en .
"Computer science"@en .
"Fourier analysis"@en .
"Theoretical computer science"@en .
"Oracle Separation of BQP and the Polynomial Hierarchy"@en .
"Moving Image"@en .
"http://hdl.handle.net/2429/69321"@en .