Talks
Fall 2018

Oracle Separation of BQP and the Polynomial Hierarchy

Monday, September 10th, 2018 2:30 pm3:30 pm

Add to Calendar

Speaker: 

Avishay Tal (Stanford University)

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.