Quantum Algorithms for Matrix Products over Semirings

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 x n matrices over the (max,min) semiring with time complexity On^2.473. In comparison, the best known classical algorithm for the same problem, by Duan and Pettie, has complexity On^2.687. As an application, we obtain a On^2.473-time quantum algorithm for computing the all-pairs bottleneck paths of a graph with n vertices, while classically the best upper bound for this task is On^2.687, again by Duan and Pettie. We construct a quantum algorithm computing the L most significant bits of each entry of the distance product of two n x n matrices in time O2^0.64L n^2.46. In comparison, prior to the present work, the best known classical algorithm for the same problem, by Vassilevska and Williams and Yuster, had complexity O2^Ln^2.69. Our techniques lead to further improvements for classical algorithms as well, reducing the classical complexity to O2^0.96Ln^2.69, which gives a sublinear dependency on 2^L. The above two algorithms are the first quantum algorithms that perform better than the 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 x n Boolean matrices that outperforms the best known classical algorithms for sparse matrices. For instance, if the input matrices have On^1.686... non-zero entries, then our algorithm has time complexity On^2.277, while the best classical algorithm has complexity On^2.373.