|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'500'096
Articles rated: 2609
19 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Quantum Algorithms for Matrix Products over Semirings | | François Le Gall
; Harumichi Nishimura
; | | Date: |
15 Oct 2013 | | 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 x 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,
has complexity O(n^{2.687}). As an application, we obtain a O(n^{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
O(n^{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 O(2^{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 O(2^{L}n^{2.69}). Our techniques lead to further improvements for
classical algorithms as well, reducing the classical complexity to
O(2^{0.96L}n^{2.69}), which gives a sublinear dependency on 2^L.
The above two algorithms are the first quantum algorithms that perform better
than the $ ilde 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
O(n^{1.686...}) non-zero entries, then our algorithm has time complexity
O(n^{2.277}), while the best classical algorithm has complexity O(n^{2.373}). | | Source: | arXiv, 1310.3898 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser claudebot
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER