log in  |  register  |  feedback?  |  help  |  web accessibility
Logo
A Separation between QNC^0 and AC^0
Luke Schaeffer - MIT
ATL 3100A Computer and Space Sciences Building (CSS)
Wednesday, January 30, 2019, 11:00 am-12:15 pm Calendar
  • You are subscribed to this talk through .
  • You are watching this talk through .
  • You are subscribed to this talk. (unsubscribe, watch)
  • You are watching this talk. (unwatch, subscribe)
  • You are not subscribed to this talk. (watch, subscribe)
Abstract
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.

 

This talk is organized by Andrea F. Svejda