Computer Science/Discrete Mathematics Seminar I

In quantum complexity theory, QMA and QCMA represent two different generalizations of NP. Both are defined as sets of languages whose Yes instances can be efficiently checked by a quantum verifier that is given a witness. With QMA the witness can be a quantum state, whereas with QCMA the witness must be a classical string. It is clear that QMA contains QCMA, but could there be a separation? In other words, can a quantum state prove more to a polynomial-time quantum verifier than a polynomial-length classical string?

In 2007, Aaronson and Kuperberg asked whether there is a (classical) oracle separation between QMA and QCMA. We show that such an oracle exists if a certain quantum pseudorandomness conjecture holds. Roughly speaking, the conjecture posits that quantum algorithms cannot, by making few queries, distinguish between the uniform distribution over permutations versus permutations drawn from so-called "dense" distributions. It turns out that this pseudorandomness conjecture is deeply related to another, seemingly-unrelated, question in theoretical computer science known as the Aaronson-Ambainis conjecture.

Our result can be viewed as establishing a "win-win" scenario: either there is a classical oracle separation of QMA from QCMA, or there is quantum advantage in distinguishing pseudorandom distributions on permutations.

This is joint work with Jiahui Liu and Saachi Mutreja. No special knowledge about quantum computation will be assumed for this talk.