University COVID-19 update

The University of Waterloo is constantly updating our most Frequently Asked Questions.

Questions about buildings and services? Visit the list of Modified Services.

Please note: The University of Waterloo is closed for all events until further notice.

Tutte Collouium - Luke SchaefferExport this event to calendar

Friday, November 1, 2019 — 3:30 PM EDT

Title: A Quantum Query Complexity Trichotomy for Regular Languages

Speaker: Luke Schaeffer
Affiliation: University of Waterloo
Room: MC 5501

Abstract:

We consider the quantum query complexity of regular languages and discover a surprising trichotomy: each regular language has query complexity either Theta(1), ~Theta(sqrt(n)) or Theta(n). Briefly, the query complexity of an algorithm is the number of bits of input it needs to read. In this setting, one can prove unconditional lower bounds for problems which in some cases (especially for quantum algorithms) coincide with the upper bounds. For example, Grover's algorithm searches a list of n items with only O(sqrt(n)) quantum queries, and a query complexity argument proves this is optimal.

The regular languages are defined by regular expressions or, equivalently, recognized by finite automata. We show that each regular language is either easy (Theta(1) queries), medium (~Theta(sqrt(n)) queries, or hard (Theta(n) queries), and characterize the regular languages of each type. Interestingly, the  ~Theta(sqrt(n)) languages correspond (modulo technical details) to the well-studied "star-free languages", which we use to interpret those languages as generalizations of Grover's algorithm. We provide examples where this perspective yields new quantum query algorithms.

(This is based on joint work with Scott Aaronson and Daniel Grier)

Location 
MC - Mathematics & Computer Building
5501
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. 2020 (72)
    1. August (5)
    2. July (17)
    3. June (11)
    4. May (6)
    5. March (11)
    6. February (11)
    7. January (11)
  2. 2019 (167)
    1. December (5)
    2. November (15)
    3. October (18)
    4. September (15)
    5. August (9)
    6. July (17)
    7. June (18)
    8. May (16)
    9. April (9)
    10. March (24)
    11. February (13)
    12. January (8)
  3. 2018 (138)
  4. 2017 (103)
  5. 2016 (137)
  6. 2015 (136)
  7. 2014 (88)
  8. 2013 (48)
  9. 2012 (39)
  10. 2011 (36)
  11. 2010 (40)
  12. 2009 (40)
  13. 2008 (39)
  14. 2007 (15)