Spring 2020

Quantum Lower Bounds for Approximate Counting via Laurent Polynomials

Tuesday, February 18th, 2020, 4:00 pm5:00 pm

Add to Calendar


Robin Kothari (Microsoft Research)

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.