Tuesday, March 19, 2019

3:00 PM -
4:00 PM

Annenberg 107

# IQI Weekly Seminar

Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits

Adam Bene Watts

*,*Massachusetts Institute of Technology*,***Abstract**:

Recently, Bravyi, Gosset, and K onig (Science, 2018) exhibited a search problem that can be solved exactly by a constant-depth quantum circuit using bounded fan-in gates (QNC^0 circuits), but cannot be solved by any constant-depth classical circuit using bounded fan-in AND, OR, and NOT gates (NC^0 circuits). I will discuss a strengthening of their result, giving a problem which can be solved exactly by a constant depth quantum circuit but cannot be solved by classical, polynomial sized, constant-depth circuits over the gate set of unbounded fan-in AND and OR gates, and NOT gates (AC^0 circuits). A focus of this talk will be on giving a description of some basic techniques for manipulating data with constant depth quantum circuits.

Event Sponsors:

For more information, please contact Bonnie Leung by email at bjleung@caltech.edu