Abstract
We present a distribution over inputs in ± 12N, 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.
Original language | English (US) |
---|---|
Article number | 30 |
Journal | Journal of the ACM |
Volume | 69 |
Issue number | 4 |
DOIs | |
State | Published - Aug 31 2022 |
Externally published | Yes |
All Science Journal Classification (ASJC) codes
- Software
- Control and Systems Engineering
- Information Systems
- Hardware and Architecture
- Artificial Intelligence
Keywords
- BQP
- bounded depth circuits
- oracle separation
- polynomial hierarchy