@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",
}