IQC Colloquium - Adam Bene Watts - MITExport this event to calendar

Monday, June 17, 2019 — 2:30 PM EDT

A separation between QNC0 and AC0

Previously, Bravyi, Gosset and Konig (Science 2018) showed a separation between constant depth quantum circuits and constant depth classical circuits with bounded fanin. We find a related problem which separates shallow classical and quantum circuits even if the classical circuit has unbounded fan-in AND gates. The problem is based on a technique borrowed from measurement based quantum computation which allows us to construct a cat state with Pauli errors in constant depth. The classical lower bounds are proved using bounds from nonlocal games, circuit lightcones, and the switching lemma.

Reception and refreshments at 2:00pm in QNC 0101.

Talk to begin at 2:30pm.

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
1
2
3
4
5
6
  1. 2019 (93)
    1. November (1)
    2. August (3)
    3. July (4)
    4. June (13)
    5. May (15)
    6. April (15)
    7. March (11)
    8. February (20)
    9. January (12)
  2. 2018 (148)
    1. December (8)
    2. November (20)
    3. October (10)
    4. September (10)
    5. August (10)
    6. July (11)
    7. June (9)
    8. May (13)
    9. April (16)
    10. March (17)
    11. February (14)
    12. January (13)
  3. 2017 (135)
  4. 2016 (94)
  5. 2015 (85)
  6. 2014 (97)
  7. 2013 (92)
  8. 2012 (125)
  9. 2011 (117)
  10. 2010 (41)
  11. 2009 (4)
  12. 2008 (1)
  13. 2007 (1)
  14. 2005 (1)
  15. 2004 (3)