Wednesday, February 1, 2012

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

No comments:

Post a Comment