Improved Time-Efficient Output-Sensitive Quantum Algorithms for Boolean Matrix Multiplication

Details Improved Time-Efficient Output-Sensitive Quantum Algorithms for Boolean Matrix Multiplication Improved Time-Efficient Output-Sensitive Quantum Algorithms for Boolean Matrix Multiplication

2012-01-30

arxiv.org/abs/1201.6174v1

Physics

Quantum Physics

9 pages

Scientific paper

A quantum algorithm that computes the product of two n x n Boolean matrices using O(nL^{1/2}) queries, where L is the number of non-zero entries in the product, has recently been constructed by Jeffery, Kothari and Magniez (arXiv:1112.5855). In this paper we build on these ideas to show that there exists a quantum algorithm for the same problem with time complexity O(nL^{1/2} + Ln^{1/2}). This improves the previous output-sensitive quantum algorithms for Boolean matrix multiplication in the time complexity setting by Buhrman and Spalek (SODA'06) and Le Gall (SODA'12).

Affiliated with

Also associated with

No associations

Rating

Improved Time-Efficient Output-Sensitive Quantum Algorithms for Boolean Matrix Multiplication does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Improved Time-Efficient Output-Sensitive Quantum Algorithms for Boolean Matrix Multiplication, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Improved Time-Efficient Output-Sensitive Quantum Algorithms for Boolean Matrix Multiplication will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-359363