@inproceedings{2cec9b435e604b249382fd5f98a783be,

title = "Oracle separation of BQP and pH",

abstract = "We present a distribution D over inputs in (±1)2N , 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 D and the uniform distribution with advantage Ω(1/log N). (2) No Boolean circuit of quasipoly(N) size and constant depth distinguishes between D 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 O relative to which BQPO ⊈ PHO.",

keywords = "BQP, Bounded depth circuits, Oracle separation, Polynomial hierarchy",

author = "Ran Raz and Avishay Tal",

note = "Publisher Copyright: {\textcopyright} 2019 Association for Computing Machinery.; 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019 ; Conference date: 23-06-2019 Through 26-06-2019",

year = "2019",

month = jun,

day = "23",

doi = "10.1145/3313276.3316315",

language = "English (US)",

series = "Proceedings of the Annual ACM Symposium on Theory of Computing",

publisher = "Association for Computing Machinery",

pages = "13--23",

editor = "Moses Charikar and Edith Cohen",

booktitle = "STOC 2019 - Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing",

}