TCS+ Talk

Wednesday September 19, 2018 10:00 AM

Oracle Separation of BQP and the Polynomial Hierarchy

Speaker: Avishay Tal, Simons Institute
Location: Annenberg 322

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.

 

Series TCS+ Talks

Contact: Bonnie Leung bjleung@caltech.edu