IQC Colloquium - Adam Bene Watts - MIT

A separation between QNC⁰ and AC⁰

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.