1201.6174 (François Le Gall)

Improved Time-Efficient Output-Sensitive Quantum Algorithms for Boolean
Matrix Multiplication    [PDF]

François Le Gall

A quantum algorithm that computes the product of two n x n Boolean matrices
using O(nL^{1/2}) queries, where L is the number of non-zero entries in the
product, has recently been constructed by Jeffery, Kothari and Magniez
(arXiv:1112.5855). In this paper we build on these ideas to show that there
exists a quantum algorithm for the same problem with time complexity O(nL^{1/2}
+ Ln^{1/2}). This improves the previous output-sensitive quantum algorithms for
Boolean matrix multiplication in the time complexity setting by Buhrman and
Spalek (SODA'06) and Le Gall (SODA'12).

View original: http://arxiv.org/abs/1201.6174