RSS icon
Twitter icon
Facebook icon
Vimeo icon
YouTube icon

A Separation between QNC^0 and AC^0

January 30, 2019 - 11:00am
Speaker: 
Luke Schaeffer
Institution: 
MIT
Previously, Bravyi, Gosset and Konig (2018) showed a separation between constant depth quantum circuits and constant depth classical circuits. We find a related problem which separates shallow classical and quantum circuits even if the classical circuit has unbounded fan-in AND gates. We will also show average-case hardness for the new problem.
 
ATL 3100A