Quantum IC Seminar : "Sampling probability bounds from bosons"
Event details
| Date | 21.01.2026 |
| Hour | 11:00 › 12:00 |
| Speaker | John Bostanci |
| Location | |
| Category | Conferences - Seminars |
| Event Language | English |
Please join us for the IC Seminar with John Bostanci from Columbia University who will give the talk "Sampling probability bounds from bosons" on Wednesday January 21 from 11am-12pm.
Location: BC 010
TITLE: "Sampling probability bounds from bosons"
ABSTRACT:
A major challenge in quantum query complexity is to prove bounds 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 QCMA, the majority of the paper works towards proving that an algorithm querying the “Hadamard transform” of a random sparse oracle cannot sample many distinct preimages of 1. The main technical tool used in the proof is a second quantization of the compressed oracle technique (a bosonic compressed oracle) for analyzing sparse random oracles. Surprisingly, queries 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 second quantization.
The goal of this talk will be to take a closer 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 upper bounds. Time permitting, we will also take a closer look at the application of these ideas to the classical oracle separation between QMA and QCMA, showing how flat polynomial approximations to the exponential function and perturbation theory can be used to reduce queries to the classical oracle in the QMA/QCMA separation to polynomials in the double hopping operator.
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 give a QSE Quantum Seminar "Separating QMA from QCMA with a classical oracle" on January 19 at 12:00pm, with a pizza lunch.
Practical information
- General public
- Free
Organizer
- Yihui Quek