Seminar • Institute for Quantum Computing — New Insights About Quantum Approximate CountingExport this event to calendar

Tuesday, January 28, 2020 2:30 PM EST

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).

Location 
QNC - Quantum Nano Centre
0101
200 University Avenue West

Waterloo, ON N2L 3G1
Canada

S M T W T F S
26
27
28
29
30
31
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1
2
3
4
5
  1. 2024 (98)
    1. April (21)
    2. March (27)
    3. February (25)
    4. January (25)
  2. 2023 (296)
    1. December (20)
    2. November (28)
    3. October (15)
    4. September (25)
    5. August (30)
    6. July (30)
    7. June (22)
    8. May (23)
    9. April (32)
    10. March (31)
    11. February (18)
    12. January (22)
  3. 2022 (245)
  4. 2021 (210)
  5. 2020 (217)
  6. 2019 (255)
  7. 2018 (217)
  8. 2017 (36)
  9. 2016 (21)
  10. 2015 (36)
  11. 2014 (33)
  12. 2013 (23)
  13. 2012 (4)
  14. 2011 (1)
  15. 2010 (1)
  16. 2009 (1)
  17. 2008 (1)