Improved Quantum Query Algorithms for Triangle Finding and Associativity Testing

Built on

A fast quantum mechanical algorithm for database search
Lov K. Grover · 1996
Earlier work this paper cites.
Algorithms for quantum computation: Discrete logarithm and factoring
P. Shor · 1997
Earlier work this paper cites.
Lower bounds on quantum query complexity
P. Høyer and R. Špalek · 2005
Earlier work this paper cites.
Negative weights make adversaries stronger
Peter Høyer, Troy Lee, and Robert Špalek · 2007
Earlier work this paper cites.
Quantum algorithms for the triangle problem
F. Magniez, M. Santha, and M. Szegedy · 2007
Earlier work this paper cites.

The quantum complexity of group testing
S. Dörn and T. Thierauf · 2008
Cited alongside, same era.
Quantum algorithm for k-distinctness with prior knowledge on the input
Original
A. Belovs and T. Lee · 2011
Cited alongside, same era.
Personal Communication, 2011
R. Kothari · 2011
Cited alongside, same era.
A learning graph based quantum query algorithm for finding constant-size subgraphs
Original
T. Lee, F. Magniez, and M. Santha · 2011
Cited alongside, same era.

Reflections for quantum query algorithms
Ben W. Reichardt · 2011
Later among the works it cites.
Quantum query complexity of subgraph containment with constant-sized certificates
Original
Y. Zhu · 2011
Later among the works it cites.
Learning-graph-based quantum algorithm for k-distinctness
A. Belovs · 2012
Closest in time.
Span programs for functions with constant-sized 1-certificates
A. Belovs · 2012
Closest in time.