University of Cambridge > Talks.cam > CQIF Seminar > Improving Quantum Query Complexity of Boolean Matrix Multiplication Using Graph Collision

  Browse A-Z

Log in

Googledetails Microsoftdetails

🔐 Log In

Information on

Subscribing to talksdetails Finding a talkdetails Adding a talkdetails Disseminating talksdetails Help and Documentationdetails

ℹī¸ Information

Improving Quantum Query Complexity of Boolean Matrix Multiplication Using Graph Collision

Download to your calendar using vCal

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 lists

CAPE-CIKC Advanced Technology Lectures Alison Shrubsole Room, Homerton College, Hills Road, Cambridge CB2 8PH Cambridge Judge Business School, Room W4.05

Other talks

Beyond Hubble: Studying the Earliest Galaxies with the James Webb Space Telescope Cambridge RNA Club - ONLINE The United States of America at 250: Reflections on the Past, Present and Future of Independence The role of radiation in cancer care: a spotlight on cancers of the oesophagus, head and neck Discussion I TBC
 

Š 2006-2025 Talks.cam, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity