David Gosset, IBM TJ Watson Research Center
There is strong evidence that a sufficiently large fault-tolerant quantum computer would solve certain computational problems exponentially faster than any classical computer. How can quantum algorithms and complexity theory help guide the way forward in our current era of small and noisy quantum computers?
A quantum computer without error correction will likely be limited to implementing short depth quantum circuits. In the first part of the talk I will describe a linear algebra problem which is solved by a constant-depth quantum circuit but provably cannot be solved by any classical circuit of less than logarithmic depth. This constitutes an unconditional separation between constant depth quantum circuits and their classical counterparts.
Classical simulation algorithms can be used to verify small quantum computers and to help demarcate the classically easy and hard regimes. In the second part of the talk I will describe a classical algorithm that can be used to simulate quantum circuits over the Clifford+T gate set with mildly exponential scaling in the number of T gates.
Finally, I will discuss how quantum computer science is intimately linked with our understanding of physical systems and the complexity of simulating them. I will describe how a universal quantum computer is equivalent in computational power to a quantum many-body system consisting of indistinguishable particles which move and interact on the vertices of a graph.
Bio:
David Gosset is a research staff member and manager of the theory of quantum algorithms group at IBM’s T.J. Watson Research Center. He completed his Ph.D in physics at MIT in 2011, and before joining IBM he held postdoctoral fellowships at the University of Waterloo and at Caltech. His research has recently focused on quantum algorithms for small quantum computers and classical simulation algorithms to aid in the verification of these devices. He has also investigated the computational power and complexity of quantum many-body systems, and the application of physics-inspired tools from these areas to quantum computer science.
Coffee, tea, donuts will be served.