Abstract
We give an explicit black-box problem that can be solved by a bounded-error quantum polynomial-time algorithm (BQP, in short), but cannot be solved by a classical algorithm in the polynomial hierarchy.
Following the approach of Aaronson [STOC, 2010], our result is obtained by finding a distribution D over Boolean strings of length N such that:
(1) There exists a quantum algorithm that runs in time polylog(N) and distinguishes between D and the uniform distribution over Boolean strings of length N.
(2) No Boolean circuit of quasi-polynomial size and constant depth can distinguish between D and the uniform distribution with advantage better than polylog(N)/sqrt(N).
Joint work with Ran Raz.