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

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 \v{S}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-\epsilon })$ time, for some constant $\epsilon >0$.