New Insights About Quantum Approximate Counting

Special Colloquium Featuring Scott Aaronson University of Texas, Austin

Approximate counting -- given a black-box function f:[N]->{0,1}, multiplicatively estimate the number of x's such that f(x)=1 -- is one of the most basic problems in quantum algorithms. In 1998, Brassard, Hoyer, Mosca, and Tapp (BHMT) gave a fully quadratic quantum speedup for the problem, while Nayak and Wu showed that this speedup was optimal. What else is there to say? In this talk:   

• I'll describe a new, "simpler" quantum approximate counting algorithm, which achieves the same speedup as BHMT while requiring no Quantum Fourier Transforms, just pure Grover iterations.    
• I'll describe a new proof that there's no exponential speedup for quantum approximate counting, even if, in addition to black-box queries to f, the algorithm also gets uniform superpositions |S> over the set all x's such that f(x)=1, and the ability to reflect about |S>. The proof relies on a novel generalization of the polynomial method to Laurent polynomials (which can have negative exponents).    
• I'll sketch a new proof, *also* based on Laurent polynomials, that there's no super-efficient QMA protocol for approximate counting.

Based on joint work with Patrick Rall (arXiv:1908.10846) as well as Robin Kothari, William Kretschmer, and Justin Thaler (arXiv:1904.08914).

Assortment of snacks and coffee to be served at 2:00.