BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Memento EPFL//
BEGIN:VEVENT
SUMMARY:QSE Quantum Seminar: "Separating QMA from QCMA with a classical or
 acle"
DTSTART:20260119T120000
DTEND:20260119T133000
DTSTAMP:20260528T092931Z
UID:29fea0adc4a9c07c19e2da98a151447ac7cd1453d9039eeeb6670909
CATEGORIES:Conferences - Seminars
DESCRIPTION:John Bostanci\nPlease join us for the QSE Center Quantum Se
 minar with John Bostanci from Columbia University who will give the ta
 lk "Separating QMA from QCMA with a classical oracle" on Monday January 
 19 from 12pm to 1:30pm.\nLocation: CE 1 104\n\nPizzas will be available a
 t 12:00. All PhDs\, postdocs\, students\, group leaders\, and PIs are welc
 ome to join us.\n\nTITLE: "Separating QMA from QCMA with a classical orac
 le"\n\nABSTRACT: \nWe construct a classical oracle proving that\, in a re
 lativized setting\, the set of languages decidable by an efficient quantum
  verifier with a quantum witness (QMA) is strictly bigger than those decid
 able with access only to a classical witness (QCMA). The separating classi
 cal oracle we construct is for a decision problem we coin spectral Forrela
 tion -- the oracle describes two subsets of the boolean hypercube\, and th
 e computational task is to decide if there exists a quantum state whose st
 andard basis measurement distribution is well supported on one subset whil
 e its Fourier basis measurement distribution is well supported on the othe
 r subset. This is equivalent to estimating the spectral norm of a "Forrela
 tion" matrix between two sets that are accessible through membership queri
 es. \n\nOur lower bound derives from a simple observation that a query al
 gorithm with a classical witness can be run multiple times to generate man
 y samples from a distribution\, while a quantum witness is a "use once" ob
 ject. This observation allows us to reduce proving a QCMA lower bound to p
 roving a sampling hardness result which does not simultaneously prove a QM
 A lower bound. To prove said sampling hardness result for QCMA\, we observ
 e that quantum access to the oracle can be compressed by expressing the pr
 oblem in terms of bosons -- a novel "second quantization" perspective on c
 ompressed oracle techniques\, which may be of independent interest. Using 
 this compressed perspective on the sampling problem\, we prove the samplin
 g hardness result\, completing the proof.\n\nBIO: \nJohn is a graduate st
 udent at Columbia University\, advised by Henry Yuen.  He received a mast
 ers in computer science from the University of Waterloo\, advised by John 
 Watrous\, and completed his undergraduate degree at Carnegie Mellon Univer
 sity. His recent work focuses on understanding fundamental properties of q
 uantum states like unclonability\, including proving the first classical o
 racle separation between quantum and classical witnesses.  \n\nJohn Bosta
 nci will also give a Quantum IC Seminar on Wednesday January 21 at 11am: 
 "Sampling probability bounds from bosons"
LOCATION:CE 1 104 https://plan.epfl.ch/?room==CE%201%20104
STATUS:CONFIRMED
END:VEVENT
END:VCALENDAR