A time-efficient output-sensitive quantum algorithm for Boolean matrix multiplication

DOI10.1007/978-3-642-35261-4_66MaRDI QIDQ4909580zbMATH OpenOpenAlexFDO

Authors François Le Gall

Publication date 21 March 2013

Published in Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1201.6174

Mathematics Subject Classification ID

Boolean and Hadamard matrices (15B34) Numerical computation of matrix norms, conditioning, scaling (65F35) Quantum algorithms and complexity in the theory of computing (68Q12)

Abstract: This paper presents a quantum algorithm that computes the product of two $nimesn$ Boolean matrices in $ildeO(nsqrtell+ellsqrtn)$ 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 $nimesn$ Boolean matrices in $O(n^{5/2-varepsilon})$ time, for some constant $varepsilon>0$.

Recommendations

• Improved output-sensitive quantum algorithms for Boolean matrix multiplication
• Quantum complexity of Boolean matrix multiplication and related problems
• Quantum algorithms for matrix products over semirings

Cited in

(6)

• Quantum complexity of Boolean matrix multiplication and related problems
• Quantum algorithms for matrix products over semirings
• Quantum algorithms for matrix products over semirings
• Improved output-sensitive quantum algorithms for Boolean matrix multiplication
• Quantum and approximation algorithms for maximum witnesses of Boolean matrix products
• Quantum and approximation algorithms for maximum witnesses of Boolean matrix products

This page was built for publication: A time-efficient output-sensitive quantum algorithm for Boolean matrix multiplication

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4909580)