Published by the Department of Computer Science, The University of Chicago.

Abstract

In this paper we construct quantum algorithms for matrix products over several algebraic structures called semirings, including the (max,min)-matrix product, the distance matrix product and the Boolean matrix product. In particular, we obtain the following results.

• We construct a quantum algorithm computing the product of two $n\times n$ matrices over the (max,min) semiring with time complexity $O(n^{2.473})$. In comparison, the best known classical algorithm for the same problem, by Duan and Pettie (SODA'09), has complexity $O(n^{2.687})$.
• We construct a quantum algorithm computing the $\ell$ most significant bits of each entry of the distance product of two $n\times n$ matrices in time $O(2^{0.64\ell} n^{2.46})$. In comparison, the best known classical algorithm for the same problem, by Vassilevska and Williams (STOC'06) and Yuster (SODA'09), has complexity $O(2^{\ell}n^{2.69})$.
• The above two algorithms are the first quantum algorithms that perform better than the $\tilde O(n^{5/2})$-time straightforward quantum algorithm based on quantum search for matrix multiplication over these semirings. We also consider the Boolean semiring, and construct a quantum algorithm computing the product of two $n\times n$ Boolean matrices that outperforms the best known classical algorithms for sparse matrices.

• The article: PDF (338 KB)
• Source material: ZIP (445 KB)
• BibTeX entry for this article (297 bytes)

Submitted July 24, 2015, revised May 15, 2016, published May 11, 2016.

© 2017 François Le Gall, Harumichi Nishimura
Licensed under a Creative Commons Attribution License

Volume 2016, Article 14

Article 2

Volume 2017

Published articles