Date: April 6, 2026
Time: 3:45-5 p.m.
Location: Gates Hall, 122 or Click here to attend via Zoom
Speaker: John Bostanci, Columbia University
Abstract: I will talk about a pair of results showing unconditional classical oracle separations between the class of languages that can be verified with a quantum proof (QMA) and the class of languages that can be verified using a classical proof (QCMA). The first of these results uses an oracle problem known as “spectral Forrelation”, where the oracle describes a pair of sets and the task is to decide whether there exist a quantum state whose standard basis measurement is well supported on one subset while its Fourier basis measurement is well supported on the other. The second involves an oracle problem known as code intersection, where the task is, given a collection of hash functions and a desired hash, to find a codeword of a certain classical code that hashes to the desired hash.
Our lower bounds come from a simple observation that a query algorithm with a classical witness can be re-run many times to generate many samples from a distribution, while a quantum witness is a “use once” object. Proving a bound on the resulting sampling task for spectral Forrelation involves a novel “second quantization” perspective on the compressed oracle method, and for the code intersection problem requires codes with extremely good list-recovery properties.
Bio: John is a Ph.D. student in the Theory Group at Columbia advised by Henry Yuen. Before that he was a graduate student at the Institute for Quantum Computing at the University of Waterloo, advised by John Watrous, and before that he was an undergraduate at Carnegie Mellon University. He studies theoretical computer science, with a focus on quantum computation.