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 seminar - Andrew ChildsExport this event to calendar

Friday, December 11, 2009 — 3:30 PM to 4:30 PM EST

Quantum property testing for sparse graphs

Speaker: Andrew Childs
Affiliation: University of Waterloo
Room: Mathematics & Computer Building (MC) 5158

Abstract:

In property testing, the goal is to determine whether an object has a certain property or is far from having that property. Many properties of graphs can be tested very quickly, even classically; for example, one can decide whether a graph is connected or far from connected in constant time, independent of the size of the graph. However, Goldreich and Ron showed that testing bipartiteness or expansion of n-vertex graphs requires at least about sqrt(n) queries. By derandomizing classical property testing algorithms and applying quantum techniques for collision finding, we show that these problems can be solved in only about n1/3 steps on a quantum computer. Whether quantum algorithms might offer an exponential speedup for testing graph properties remains an interesting open question.

This is joint work with Yi-Kai Liu (Caltech).

Location 
MC - Mathematics & Computer Building
5158
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 (74)
    1. August (7)
    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)