ECCC-Report TR19-015https://eccc.weizmann.ac.il/report/2019/015Comments and Revisions published for TR19-015en-usThu, 07 Feb 2019 10:16:08 +0200
Paper TR19-015
| QMA Lower Bounds for Approximate Counting |
William Kretschmer
https://eccc.weizmann.ac.il/report/2019/015We 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 derive a lower bound for the $SBQP$ query complexity of the $AND$ of two approximate counting instances. We use Laurent polynomials as a tool in our proof, showing that the "Laurent polynomial method" can be useful even for problems involving ordinary polynomials.Thu, 07 Feb 2019 10:16:08 +0200https://eccc.weizmann.ac.il/report/2019/015