QSE Quantum Seminar: "Separating QMA from QCMA with a classical oracle"

Please join us for the QSE Center Quantum Seminar with John Bostanci from Columbia University who will give the talk "Separating QMA from QCMA with a classical oracle" on Monday January 19 from 12pm to 1:30pm.
Location: CE 1 104

Pizzas will be available at 12:00. All PhDs, postdocs, students, group leaders, and PIs are welcome to join us.

TITLE: "Separating QMA from QCMA with a classical oracle"

ABSTRACT: 
We construct a classical oracle proving that, in a relativized setting, the set of languages decidable by an efficient quantum verifier with a quantum witness (QMA) is strictly bigger than those decidable with access only to a classical witness (QCMA). The separating classical oracle we construct is for a decision problem we coin spectral Forrelation -- the oracle describes two subsets of the boolean hypercube, and the computational task is to decide if there exists a quantum state whose standard basis measurement distribution is well supported on one subset while its Fourier basis measurement distribution is well supported on the other subset. This is equivalent to estimating the spectral norm of a "Forrelation" matrix between two sets that are accessible through membership queries. 

Our lower bound derives from a simple observation that a query algorithm with a classical witness can be run multiple times to generate many samples from a distribution, while a quantum witness is a "use once" object. This observation allows us to reduce proving a QCMA lower bound to proving a sampling hardness result which does not simultaneously prove a QMA lower bound. To prove said sampling hardness result for QCMA, we observe that quantum access to the oracle can be compressed by expressing the problem in terms of bosons -- a novel "second quantization" perspective on compressed oracle techniques, which may be of independent interest. Using this compressed perspective on the sampling problem, we prove the sampling hardness result, completing the proof.

BIO: 
John is a graduate student at Columbia University, advised by Henry Yuen.  He received a masters in computer science from the University of Waterloo, advised by John Watrous, and completed his undergraduate degree at Carnegie Mellon University. His recent work focuses on understanding fundamental properties of quantum states like unclonability, including proving the first classical oracle separation between quantum and classical witnesses.  

John Bostanci will also give a Quantum IC Seminar on Wednesday January 21 at 11am: "Sampling probability bounds from bosons"