This paper proves new limitations on the power of quantum computers to solve approximate counting---that is, multiplicatively estimating the size of a nonempty set S [ N ] .

Given only a membership oracle for S , it is well known that approximate counting takes ( N S ) quantum queries. But what if a quantum algorithm is also given "QSamples"---i.e., copies of the state S = i S i ---or even the ability to apply reflections about S ? Our first main result is that, even then, the algorithm needs either ( N S ) queries or else ( min S 1 3 N S ) reflections or samples. We also give matching upper bounds.

We prove the lower bound using a novel generalization of the polynomial method of Beals et al. to Laurent polynomials, which can have negative exponents. We lower-bound Laurent polynomial degree using two methods: a new "explosion argument" and a new formulation of the dual polynomials method.

Our second main result rules out the possibility of a black-box Quantum Merlin-Arthur (or QMA) protocol for proving that a set is large. We show that, even if Arthur can make T quantum queries to the set S , and also receives an m -qubit quantum witness from Merlin in support of S being large, we have Tm = ( min S N S ) . This resolves the open problem of giving an oracle separation between SBP and QMA.

Note that QMA is "stronger" than the queries+QSamples model in that Merlin's witness can be anything, rather than just the specific state S , but also "weaker" in that Merlin's witness cannot be trusted. Intriguingly, Laurent polynomials also play a crucial role in our QMA lower bound, but in a completely different manner than in the queries+QSamples lower bound. This suggests that the "Laurent polynomial method" might be broadly useful in complexity theory.