$mathsf{QMA}$ Lower Bounds for Approximate Counting

We prove a query complexity lower bound for $mathsf{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 $mathsf{SBP}^A otsubset mathsf{QMA}^A$, resolving an open problem of Aaronson [2]. Our proof uses the polynomial method to derive a lower bound for the $mathsf{SBQP}$ query complexity of the $mathsf{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.