ECCC-Report TR18-107https://eccc.weizmann.ac.il/report/2018/107Comments and Revisions published for TR18-107en-usThu, 31 May 2018 19:44:13 +0300
Paper TR18-107
| Oracle Separation of BQP and PH |
Ran Raz,
Avishay Tal
https://eccc.weizmann.ac.il/report/2018/107We 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(\log N)$, that distinguishes between $D$ and the uniform distribution with advantage $\Omega(1/\log N)$.
(2) No Boolean circuit of $\mathrm{quasipoly}(N)$ size and constant depth distinguishes between $D$ and the uniform distribution with advantage better than $\mathrm{polylog}(N)/\sqrt{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 $\mathrm{BQP}^{O} \not\subseteq \mathrm{PH}^{O}$.
Thu, 31 May 2018 19:44:13 +0300https://eccc.weizmann.ac.il/report/2018/107