Oracle Separation of BQP and PH
- 31 August 2022
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 69 (4), 1-21
- https://doi.org/10.1145/3530258
Abstract
We present a distribution 𝓓 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 𝓓 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.Keywords
Funding Information
- Simons Collaboration on Algorithms and Geometry
- National Science Foundation (CCF-1412958, and CCF-1763311)
- Motwani Postdoctoral Fellowship
This publication has 13 references indexed in Scilit:
- On the Correlation of Parity and Small-Depth CircuitsSIAM Journal on Computing, 2014
- BQP and the polynomial hierarchyPublished by Association for Computing Machinery (ACM) ,2010
- Quantum Complexity TheorySIAM Journal on Computing, 1997
- On the Power of Quantum ComputationSIAM Journal on Computing, 1997
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum ComputerSIAM Journal on Computing, 1997
- A fast quantum mechanical algorithm for database searchPublished by Association for Computing Machinery (ACM) ,1996
- Constant depth circuits, Fourier transform, and learnabilityJournal of the ACM, 1993
- Parity, circuits, and the polynomial-time hierarchyTheory of Computing Systems, 1984
- Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1SIAM Journal on Computing, 1981
- On a Formula for the Product-Moment Coefficient of any Order of a Normal Frequency Distribution in any Number of VariablesBiometrika, 1918