#

### Volume 2017

#### Article 1

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

#### Quantum Algorithms for Matrix Products over Semirings

François Le Gall;

Kyoto University

Kyoto, Japan

`legall AT i DOT kyoto-u DOT ac DOT jp`

and

Harumichi Nishimura

Nagoya University

Nagoya, Japan

`hnishimura AT math DOT cm DOT is DOT nagoya-u DOT ac DOT jp`

*May 11,2017*
#### 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.

Volume 2016, Article 14

Volume 2017
Published articles