Le Gall, François; Nishimura, Harumichi Quantum algorithms for matrix products over semirings. (English) Zbl 1375.68056 Chic. J. Theor. Comput. Sci. 2017, Article No. 1, 25 p. (2017). Summary: 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. \(\bullet\) 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 R. Duan and S. Pettie [“Fast algorithms for (max, min)-matrix multiplication and bottleneck shortest paths”, in: Proceedings of the 20th annual ACM-SIAM symposium on discrete algorithms, SODA’09. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 384–391 (2009; doi:10.1137/1.9781611973068.43)], has complexity \(O(n^{2.687})\). \(\bullet\) 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 V. Vassilevska and R. Williams [in: Proceedings of the 38th annual ACM symposium on theory of computing, STOC’06. New York, NY: ACM Press. 225–231 (2006; Zbl 1301.05342)] and R. Yuster [“Efficient algorithms on sets of permutations, dominance, and real-weighted APSP”, in: Proceedings of the 20th annual ACM-SIAM symposium on discrete algorithms, SODA’09. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 950–957 (2009; doi:10.1137/1.9781611973068.103)], 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. Cited in 1 Document MSC: 68Q12 Quantum algorithms and complexity in the theory of computing 15B33 Matrices over special rings (quaternions, finite fields, etc.) 15B34 Boolean and Hadamard matrices Keywords:quantum algorithms; matrix multiplication; semirings Citations:Zbl 1301.05342 PDFBibTeX XMLCite \textit{F. Le Gall} and \textit{H. Nishimura}, Chic. J. Theor. Comput. Sci. 2017, Article No. 1, 25 p. (2017; Zbl 1375.68056) Full Text: DOI