Improving Quantum Query Complexity of Boolean Matrix Multiplication Using Graph Collision

Built on

A quantum algorithm for finding the minimum
C. Dürr and P. Høyer · 1996
Earlier work this paper cites.
A fast quantum mechanical algorithm for database search
L. K. Grover · 1996
Earlier work this paper cites.
Strengths and weaknesses of quantum computing
C. H. Bennett, E. Bernstein, G. Brassard, and U. Vazirani · 1997
Earlier work this paper cites.
Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer
P. W. Shor · 1997
Earlier work this paper cites.
Tight bounds on quantum searching
M. Boyer, G. Brassard, P. Høyer, and A. Tapp · 1998
Earlier work this paper cites.

Quantum lower bounds by polynomials
R. Beals, H. Buhrman, R. Cleve, M. Mosca, and R. de Wolf · 2001
Cited alongside, same era.
Quantum walk algorithm for element distinctness
A. Ambainis · 2004
Cited alongside, same era.
Quantum verification of matrix products
H. Buhrman and R. Špalek · 2006
Cited alongside, same era.
Quantum query complexity of some graph problems
C. Dürr, M. Heiligman, P. Høyer, and M. Mhalla · 2006
Cited alongside, same era.
Quantum algorithms for the triangle problem
F. Magniez, M. Santha, and M. Szegedy · 2007
Cited alongside, same era.

A fast output-sensitive algorithm for Boolean matrix multiplication
A. Lingas · 2009
Later among the works it cites.
Sub-cubic equivalences between path, matrix and triangle problems
Original
V. Vassilevska Williams and R. Williams · 2010
Later among the works it cites.
Span programs for functions with constant-sized 1-certificates
Original
A. Belovs · 2011
Closest in time.
The quantum query complexity of read-many formulas
Original
A. Childs, S. Kimmel, and R. Kothari · 2011
Closest in time.
Improved output-sensitive quantum algorithms for Boolean matrix multiplication
F. Le Gall · 2012
Closest in time.