[quantum-info] colloquium Institute for Quantum Computing Monday, 24 March, 2014
Matthew Fries
mfries at uwaterloo.ca
Mon Mar 24 01:51:03 EDT 2014
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.
More information about the quantum-info
mailing list