1201.6174 (François Le Gall)
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
No comments:
Post a Comment