[quantum-info] colloquium Institute for Quantum Computing Monday, 24 March, 2014

[Matthew Fries]

Colloquium

Institute for Quantum Computing

Monday, 24 March 2014 at 2:30PM

QNC 0101

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.