Avishay Tal: Oracle Separation of BQP and the Polynomial Hierarchy

Abstract:
In their seminal paper, Bennett, Bernstein, Brassard and Vazirani
[SICOMP, 1997] showed that relative to an oracle, quantum algorithms
are unable to solve NP-complete problems in sub-exponential time
(i.e., that Grover's search is optimal in this setting).

In this work, we show a strong converse to their result. Namely, we
show that, relative to an oracle, there exist computational tasks that
can be solved efficiently by a quantum algorithm, but require
exponential time for any algorithm in the polynomial hierarchy. (The
polynomial hierarchy is a hierarchy of complexity classes that
captures P, NP, coNP, and their generalizations.)

The tasks that exhibit this "quantum advantage" arise from a
pseudo-randomness approach initiated by Aaronson [STOC, 2010]. Our
core technical result is constructing a distribution over Boolean
strings that "look random" to constant-depth circuits of
quasi-polynomial size, but can be distinguished from the uniform
distribution by very efficient quantum algorithms.

Joint work with Ran Raz.