Physics – Quantum Physics
Scientific paper
2011-12-26
Physics
Quantum Physics
Scientific paper
The quantum query complexity of Boolean matrix multiplication is typically studied as a function of the matrix dimension, n, as well as the number of 1s in the output, \ell. We prove an upper bound of O (n\sqrt{\ell}) for all values of \ell. This is an improvement over previous algorithms for all values of \ell. On the other hand, we show that for any \eps < 1 and any \ell <= \eps n^2, there is an \Omega(n\sqrt{\ell}) lower bound for this problem, showing that our algorithm is essentially tight. We first reduce Boolean matrix multiplication to several instances of graph collision. We then provide an algorithm that takes advantage of the fact that the underlying graph in all of our instances is very dense to find all graph collisions efficiently.
Jeffery Stacey
Kothari Robin
Magniez Frederic
No associations
LandOfFree
Improving Quantum Query Complexity of Boolean Matrix Multiplication Using Graph Collision 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 Improving Quantum Query Complexity of Boolean Matrix Multiplication Using Graph Collision, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Improving Quantum Query Complexity of Boolean Matrix Multiplication Using Graph Collision will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-252821