Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR18-107 | 31st May 2018 19:36

Oracle Separation of BQP and PH

RSS-Feed




TR18-107
Authors: Ran Raz, Avishay Tal
Publication: 31st May 2018 19:44
Downloads: 18272
Keywords: 


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}$.



ISSN 1433-8092 | Imprint