|COOKIES: By using this website you agree that we can place Google Analytics Cookies on your device for performance monitoring.|
Improving Quantum Query Complexity of Boolean Matrix Multiplication Using Graph Collision
If you have a question about this talk, please contact Ashley Montanaro.
Note change of time and room
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 < 1 and any l <= eps n^2, 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 talk is part of the CQIF Seminar series.
This talk is included in these lists:
Note that ex-directory lists are not shown.
Other listsCambridge Countercultural Studies Research Group Biology St John's Women's Society Talks
Other talksJaroslav and the Taste for Folkloric Performances in Socialist Mongolia: an Ideal–Type Inspired from Fictional Literature A Heisenberg Miscellany Winton 2nd Annual Symposium on Materials Discovery Shock compression of geological materials "Using computational methods to aid our understanding of ionotropic glutamate receptors at the molecular level" --