# A Time-Efficient Output-Sensitive Quantum Algorithm for Boolean Matrix Multiplication

Preprint · François Le Gall

- Archive id: arxiv:1201.6174
- Published: 2012-01-30
- Venue: Proceedings of the 23rd International Symposium on Algorithms and Computation (ISAAC 2012), LNCS 7676, pp. 639-648, 2012
- DOI: https://doi.org/10.1007/978-3-642-35261-4\_66
- arXiv: https://arxiv.org/abs/1201.6174
- Source URL: https://arxiv.org/abs/1201.6174
- PDF: https://arxiv.org/pdf/1201.6174
- Provenance: arxiv

## Abstract

This paper presents a quantum algorithm that computes the product of two $n\\times n$ Boolean matrices in $\\tilde O(n\\sqrt{\\ell}+\\ell\\sqrt{n})$ time, where $\\ell$ is the number of non-zero entries in the product. This improves the previous output-sensitive quantum algorithms for Boolean matrix multiplication in the time complexity setting by Buhrman and Špalek (SODA'06) and Le Gall (SODA'12). We also show that our approach cannot be further improved unless a breakthrough is made: we prove that any significant improvement would imply the existence of an algorithm based on quantum search that multiplies two $n\\times n$ Boolean matrices in $O(n^{5/2-\\varepsilon})$ time, for some constant $\\varepsilon\>0$.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.