Abstract: Quantum computing is at an exciting moment in its history, with some high-profile experimental successes in building programmable quantum devices.  That said, these quantum devices (at least in the near term) will be restricted in several ways, raising questions about their power relative to classical computers. In this talk, I will present three results which give us a better understanding of these near-term quantum devices, revealing key features which make them superior to their classical counterparts.

First, I will show that constant-depth quantum circuits can solve problems that cannot be solved by any constant-depth classical circuit consisting of AND, OR, NOT, and PARITY gates---giving the largest-known unconditional separation between natural classes of quantum and classical circuits.  Second, I will show that these quantum circuits can nevertheless be simulated quickly by classical algorithms that have no depth restriction, emphasizing the role that depth plays in provable quantum advantage.  Finally, I will address some of the experimental challenges in implementing linear optical quantum computers, and I will prove that they outperform classical computers using standard conjectures but in more practical experimental regimes.

Bio: Daniel is a postdoctoral researcher at the Institute for Quantum Computing at the University of Waterloo.  He received his PhD in Computer Science at MIT, where he was advised by Scott Aaronson and was supported by an NSF Graduate Research Fellowship. His research lies at the intersection of complexity theory and quantum computing, with a particular focus on the power of near-term quantum computing devices.