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 Colloquium - David GossetExport this event to calendar

Friday, January 22, 2021 — 3:30 PM EST

Title: Fast simulation of planar Clifford circuits

Speaker: David Gosset
Aflliation: University of Waterloo
YouTube Link: https://youtu.be/LjmjiEPTSNo

Abstract:

Clifford circuits are a special family of quantum circuits that can be simulated on a classical computer in polynomial time using linear algebra. Recent work has shown that Clifford circuits composed of nearest-neighbor gates in planar geometries can solve certain linear algebra problems provably faster --as measured by circuit depth-- than classical computers. We don't know if these linear algebra tasks also admit polynomial quantum speedups in terms of total runtime (gate complexity). Motivated by this question, here we show that treewidth and planarity can be used to improve classical algorithms for simulating Clifford circuits. Our main result is a classical algorithm with runtime asymptotically upper bounded as n^{W/2} which samples from the output distribution obtained by measuring each qubit of a quantum planar graph state in given Pauli bases, where W is the matrix multiplication exponent. We also provide a classical algorithm with the same asymptotic runtime which samples from the output distribution of any constant-depth Clifford circuit in a planar geometry. This is joint work with Daniel Grier, Alex Kerzner, and Luke Schaeffer (arxiv:2009.03218).

S M T W T F S
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
1
2
  1. 2021 (84)
    1. October (1)
    2. September (7)
    3. August (7)
    4. July (10)
    5. June (12)
    6. May (7)
    7. April (9)
    8. March (13)
    9. February (8)
    10. January (10)
  2. 2020 (119)
    1. December (5)
    2. November (12)
    3. October (12)
    4. September (12)
    5. August (11)
    6. July (17)
    7. June (11)
    8. May (6)
    9. March (11)
    10. February (11)
    11. January (11)
  3. 2019 (167)
  4. 2018 (136)
  5. 2017 (103)
  6. 2016 (137)
  7. 2015 (136)
  8. 2014 (88)
  9. 2013 (48)
  10. 2012 (39)
  11. 2011 (36)
  12. 2010 (40)
  13. 2009 (40)
  14. 2008 (39)
  15. 2007 (15)