×

Quantum algorithms for matrix products over semirings. (English) Zbl 1375.68056

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.

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

Citations:

Zbl 1301.05342
PDFBibTeX XMLCite
Full Text: DOI