PhD Seminar • Quantum Computing | Complexity Theory • Oracle Separations for Quantum-Classical Polynomial Hierarchy

Please note: This PhD seminar will take place in QNC 1201.

Avantika Agarwal, PhD candidate
David R. Cheriton School of Computer Science

Supervisors: Professors Shalev Ben-David, Eric Blais

We study the quantum-classical polynomial hierarchy, QCPH, which is the class of languages solvable by a constant number of alternating classical quantifiers followed by a quantum verifier. Our main result is that QCPH is infinite relative to a random oracle (previously, this was not even known relative to any oracle). We further prove that higher levels of PH are not contained in lower levels of QCPH relative to a random oracle; this is a strengthening of the somewhat recent result that PH is infinite relative to a random oracle (Rossman, Servedio, and Tan 2016).

To establish this, we give a new switching lemma for quantum algorithms which may be of independent interest. Our lemma says that if we apply a random restriction to a function f with low quantum query complexity, the restricted function becomes exponentially close (in terms of depth) to a small depth decision tree. Our switching lemma works even in a “worst-case” sense, in that only the indices to be restricted are random; the values they are restricted to are chosen adversarially. Moreover, the switching lemma also works for polynomial degree in place of quantum query complexity.

This talk is based on joint work with Prof. Shalev Ben-David.