Quantum Lunch: Solving linear systems of equations in logarithmic space: quantum versus classical algorithms

Speaker: Francois Le Gall from Kyoto University

Title:
Solving linear systems of equations in logarithmic space: quantum versus classical algorithms

Abstract:
In this talk I will discuss the space complexity of solving linear systems of equations. While all known deterministic or randomized algorithms solving a square system of n linear equations in n variables require Ω((log n)^2) space, Ta-Shma (STOC 2013) recently showed that on a quantum computer an approximate solution can be computed in logarithmic space, giving the first explicit computational task for which quantum computation seems to outperform classical computation with respect to space complexity. In this talk, after surveying known results about space-bounded quantum computation and then briefly describing Ta-Shma's quantum algorithm, I will present a recent result showing that for an important class of systems of linear equations, logarithmic space complexity can actually be achieved by a classical algorithm.

This talk is partly based on the preprint ArXiv:1608.01426 and further joint work with Dean Doron and Amnon Ta-Shma.