BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Memento EPFL//
BEGIN:VEVENT
SUMMARY:Quantum IC Seminar : "Sampling probability bounds from bosons"
DTSTART:20260121T110000
DTEND:20260121T120000
DTSTAMP:20260416T071234Z
UID:49ad8a870af92fd67183c7ed17a055ef93e80089d030ccc6fe238fff
CATEGORIES:Conferences - Seminars
DESCRIPTION:John Bostanci\nPlease join us for the IC Seminar with John 
 Bostanci from Columbia University who will give the talk "Sampling pro
 bability bounds from bosons" on Wednesday January 21 from 11am-12pm.\n\nL
 ocation: BC 010\n\nTITLE: "Sampling probability bounds from bosons"\n\nAB
 STRACT: \nA major challenge in quantum query complexity is to prove bound
 s against algorithms querying “structured” oracles\, such as pairs of 
 oracles that are related to each other by a global transformation like the
  Fourier transform.  In the recent classical separation between QMA and Q
 CMA\, the majority of the paper works towards proving that an algorithm qu
 erying the “Hadamard transform” of a random sparse oracle cannot sampl
 e many distinct preimages of 1.  The main technical tool used in the proo
 f is a second quantization of the compressed oracle technique (a bosonic c
 ompressed oracle) for analyzing sparse random oracles.  Surprisingly\, qu
 eries to the Hadamard transform of the sparse oracle take on a relatively 
 simple form in terms of a bosonic hopping operator when viewed in this sec
 ond quantization.  \n\n \n\nThe goal of this talk will be to take a clos
 er look at the bosonic compressed oracle.  We will show how it came about
  from analyzing random sparse oracles\, prove that queries to the Hadamard
  transform are equivalent to applications of a double hopping operator on 
 a bosonic system\, and show how these results imply sampling probability u
 pper bounds. Time permitting\, we will also take a closer look at the appl
 ication of these ideas to the classical oracle separation between QMA and 
 QCMA\, showing how flat polynomial approximations to the exponential func
 tion and perturbation theory can be used to reduce queries to the classica
 l oracle in the QMA/QCMA separation to polynomials in the double hopping o
 perator.  \n\nBIO: \nJohn is a graduate student at Columbia University\,
  advised by Henry Yuen.  He received a masters in computer science from t
 he University of Waterloo\, advised by John Watrous\, and completed his un
 dergraduate degree at Carnegie Mellon University. His recent work focuses 
 on understanding fundamental properties of quantum states like unclonabili
 ty\, including proving the first classical oracle separation between quant
 um and classical witnesses.  \n\nJohn Bostanci will give a QSE Quantum Se
 minar "Separating QMA from QCMA with a classical oracle" on January 19 at
  12:00pm\, with a pizza lunch. 
LOCATION:BC 010 https://plan.epfl.ch/?room==BC%20010
STATUS:CONFIRMED
END:VEVENT
END:VCALENDAR