All reports by Author William Kretschmer:

__
TR19-015
| 7th February 2019
__

William Kretschmer#### QMA Lower Bounds for Approximate Counting

William Kretschmer

We prove a query complexity lower bound for $QMA$ protocols that solve approximate counting: estimating the size of a set given a membership oracle. This gives rise to an oracle $A$ such that $SBP^A \not\subset QMA^A$, resolving an open problem of Aaronson [2]. Our proof uses the polynomial method to ... more >>>