Abstracts
Poster Abstracts | Talk Abstracts
Quantum proofs for approximate counting
Presenting Author: William Kretschmer, University of Texas, Austin
We prove a QMA query complexity lower bound for approximate counting: estimating the size of a set given a membership oracle and a quantum witness. This gives rise to an oracle relative to which SBP is not contained in QMA, resolving an open problem of Aaronson [arXiv:1808.02420]. More generally, we prove a lower bound tradeoff between query complexity and witness length for this problem.
- Home
- SQuInT
- Registration
- Program
- Instructions for Presenters
- Survey
- Lodging and Transportation
- Hotel Floor Maps (.pdf)
- Faculty Favorites at Old Town
- Past SQuInT Meetings
SQuInT Chief Organizer
Akimasa Miyake, Associate Professor
amiyake@unm.edu
Rafael Alexander, Postdoctoral Fellow
Chris Jackson, Postdoctoral Fellow
SQuInT Administrator
Gloria Cordova
gjcordo1@unm.edu
505 277-1850
SQuInT Assistant
Wendy Jay
SQuInT Founder
Ivan Deutsch, Regents' Professor, CQuIC Director
ideutsch@unm.edu
