{
  "id": "1310.3898",
  "version": "v1",
  "published": "2013-10-15T01:57:28.000Z",
  "updated": "2013-10-15T01:57:28.000Z",
  "title": "Quantum Algorithms for Matrix Products over Semirings",
  "authors": [
    "François Le Gall",
    "Harumichi Nishimura"
  ],
  "comment": "19 pages",
  "categories": [
    "quant-ph",
    "cs.DS"
  ],
  "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 $\\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 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}).",
  "revisions": [
    {
      "version": "v1",
      "updated": "2013-10-15T01:57:28.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "classical algorithm",
      "quantum algorithm computing",
      "time complexity",
      "boolean matrix product",
      "distance matrix product"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 19,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2013arXiv1310.3898L"
    }
  }
}