Skip to Content

Quantum advantage with shallow circuits

Abstract : We prove that constant-depth quantum circuits are more powerful than their classical counterparts. We describe a linear algebra problem which can be solved with certainty by a constant-depth quantum circuit composed of one- and two-qubit gates. In contrast, we prove that any classical probabilistic circuit composed of bounded fan-in gates that solves the problem with high probability must have depth logarithmic in the input size. Based on joint work with Sergey Bravyi and Robert Koenig. This talk is geared towards a broad audience from across computer science, physics, chemistry, and mathematics.

Bio : David Gosset is an Associate Professor in the Department of Combinatorics and Optimization and the Institute for Quantum Computing at the University of Waterloo. He received his PhD in Physics from MIT in 2011 under the supervision of Edward Farhi, held postdocs at the University of Waterloo and at Caltech, and was most recently a research staff member and manager of the theory of quantum algorithms group at the IBM T.J. Watson Research Center. He is interested in the computer science perspective on physics and its application to models of computation, the computational complexity of quantum many-body systems, and quantum algorithms. His research has recently centered around questions in algorithms and complexity which are guided by the impending availability of small quantum computers.