Quantum Lower Bounds for Approximate Counting via Laurent Polynomials

Understand

We study quantum algorithms that are given access to trusted and untrusted quantum witnesses.

• We establish strong limitations of such algorithms, via new techniques based on Laurent polynomials (i.e., polynomials with positive and negative integer exponents).
• Specifically, we resolve the complexity of approximate counting, the problem of multiplicatively estimating the size of a nonempty set $S \subseteq [N]$, in two natural generalizations of quantum query complexity.
• Our first result holds in the standard Quantum Merlin--Arthur ($\mathsf{QMA}$) setting, in which a quantum algorithm receives an untrusted quantum witness.