Chicago Journal of Theoretical Computer Science

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


Harumichi Nishimura
Nagoya University
Nagoya, Japan
hnishimura AT math DOT cm DOT is DOT nagoya-u DOT ac DOT jp

May 11,2017


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.

Submitted July 24, 2015, revised May 15, 2016, published May 11, 2016.

DOI: 10.4086/cjtcs.2017.001

[] Volume 2016, Article 14 [] Article 2
[back] Volume 2017 [back] Published articles
[CJCTS home]