Quantum Lower Bounds for Approximate Counting via Laurent Polynomials

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⊆[N], in two natural generalizations of quantum query complexity.

Based on joint work with Scott Aaronson, William Kretschmer, and Justin Thaler, arXiv:1904.08914.