THIS SITE

Information for

Tutte Colloquium - David GossetExport this event to calendar

Friday, September 21, 2018 — 3:30 PM EDT

Title: Quantum advantage with shallow circuits

Speaker: David Gosset
Affiliation: University of Waterloo
Room: MC 5501

Abstract:

A constant-depth quantum circuit is a parallel quantum computation that proceeds for a constant number of time steps.  In this work we prove that constant-depth quantum circuits are more powerful than their classical counterparts. We describe a linear algebra problem which can be solved with certainty by a constant-depth quantum circuit composed of one- and two-qubit gates. In contrast, we prove that any classical probabilistic circuit composed of bounded fan-in gates that solves the problem with high probability must have depth logarithmic in the input size. The quantum advantage for this task is due to a strong form of quantum nonlocality which we establish is present in the measurement statistics of quantum states generated by constant-depth quantum circuits.

This is joint work with Sergey Bravyi and Robert Koenig .

Location 
MC - Mathematics & Computer Building
5501
200 University Avenue West
Waterloo, ON N2L 3G1
Canada

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