## Oracle Separation of Quantum Polynomial time and the Polynomial Hierarchy

Avishay Tal

University of California, Berkeley

October 1, 2018

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).