# Oracle separation of BQP and PH

## Author(s): Raz, Ran; Tal, Avishay

To refer to this page use: http://arks.princeton.edu/ark:/88435/pr1q82t
 Abstract: We present a distribution D over inputs in {−1,1}2N, such that: (1) There exists a quantum algorithm that makes one (quantum) query to the input, and runs in time O(logN), that distinguishes between D and the uniform distribution with advantage Ω(1/logN). (2) No Boolean circuit of quasi-polynomial 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. Publication Date: Jun-2019 Citation: Raz, Ran, and Avishay Tal. "Oracle separation of BQP and PH." Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (2019): pp. 13-23. doi:10.1145/3313276.3316315 DOI: 10.1145/3313276.3316315 Pages: 13 - 23 Type of Material: Conference Article Series/Report no.: STOC 2019; Journal/Proceeding Title: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing Version: Author's manuscript