Le Gall: Quantum Complexity of Matrix Multiplication

Francois Le Gall, The University of Tokyo

In this talk I will describe recent progresses in the development of quantum algorithms for matrix multiplication. I will start with the case of Boolean matrices, and discuss the time complexity and query complexity of Boolean matrix multiplication in the quantum setting. I will then focus on other kinds of matrix products, in particular matrix products over algebraic structures known as "semirings" (such as the distance matrix product or the max-min matrix product), and describe new quantum algorithms, which are faster than the best known classical algorithms, for some of these products. Finally I will present several open problems related to the complexity of matrix multiplication.