__
TR18-107 | 31st May 2018 19:36
__

#### Oracle Separation of BQP and PH

**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(\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}$.