Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR19-015 | 7th February 2019 10:06

QMA Lower Bounds for Approximate Counting

RSS-Feed




TR19-015
Authors: William Kretschmer
Publication: 7th February 2019 10:16
Downloads: 214
Keywords: 


Abstract:

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 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.



ISSN 1433-8092 | Imprint