Improving the Quantum Query Complexity of Boolean Matrix Multiplication Using Graph Collision

IQC Masters student Stacey Jeffery lectures on Improving the Quantum Query Complexity of Boolean Matrix Multiplication Using Graph Collision, during the "Recent Progress in Quantum Algorithms" conference.

The event was hosted by The Institute for Quantum Computing, and The Perimeter Institute and was held in Waterloo, Ontario, April 11-13th, 2012.

Abstract: 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, L. We prove an upper bound of ~O(n\sqrt{L}) for all values of L. This is an improvement over previous algorithms for all values of L. On the other hand, we show that for any eps less then 1 and any L less then= eps*n squared, there is an Omega(n\sqrt{L}) 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.

This is joint work with Robin Kothari and Frédéric Magniez.

[Abolwafa]

sexy professor! I want to join this lecture!