Monday, June 17, 2019 2:30 pm
-
2:30 pm
EDT (GMT -04:00)
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.