Tuesday, January 28, 2020 2:30 pm
-
2:30 pm
EST (GMT -05:00)
Scott
Aaronson,
David
J.
Bruton
Centennial
Professor
of
Computer
Science
University
of
Texas
at
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).