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.

(Session 5 : Sunday from 5:00pm - 7:00pm)


SQuInT Chief Organizer
Akimasa Miyake, Associate Professor

SQuInT Local Organizers
Rafael Alexander, Postdoctoral Fellow
Chris Jackson, Postdoctoral Fellow

SQuInT Administrator
Gloria Cordova
505 277-1850

SQuInT Assistant
Wendy Jay

SQuInT Founder
Ivan Deutsch, Regents' Professor, CQuIC Director

Tweet About SQuInT 2019!