QMA vs. QCMA and Pseudorandomness

Title: QMA vs. QCMA and Pseudorandomness

Abstract: In quantum complexity theory, the complexity classes QMA and QCMA are 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.

Bio: Henry Yuen is the Srivani Family Associate Professor of Computer Science at Columbia University. His research focuses on the interplay between quantum computing, complexity theory, cryptography, and information theory. Yuen received a BA in mathematics from the University of Southern California in 2010, and received his PhD in computer science at MIT in 2016. He is a recipient of the NSF CAREER award and a Sloan Fellowship.