Seminar - David Gosset

Title: Algorithms and complexity for quantum advantage

Abstract:

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.