Oracle Separation of BQP and PH
Ran Raz, Avishay Tal
Abstract
We present a distribution 𝓓 over inputs in {± 1} 2 N , such that: (1) There exists a quantum algorithm that makes one (quantum) query to the input, and runs in time O (log N ), that distinguishes between 𝓓 and the uniform distribution with advantage Ω (1/log N ). (2) No Boolean circuit of quasi-polynomial size and constant depth distinguishes between 𝓓 and the uniform distribution with advantage better than polylog(N)/√ N . By well-known reductions, this gives a separation of the classes Promise- BQP and Promise- PH in the black-box model and implies an oracle relative to which BQP is not contained in PH .
Topics & Concepts
OracleMathematicsCombinatoricsUniform distribution (continuous)Binary logarithmConstant (computer programming)Discrete mathematicsTime complexityComputer scienceStatisticsSoftware engineeringProgramming languageQuantum Computing Algorithms and ArchitectureCryptography and Data SecurityComplexity and Algorithms in Graphs