TCS+ Talk

Abstract:  We present an oracle, A, relative to which BQP^A is not contained in PH^A. 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.