Fetching the paper…
Reading the bibliography…
We present new quantum algorithms for Triangle Finding improving its best previously known quantum query complexities for both dense and spare instances.For dense graphs on $n$ vertices, we get a query complexity of $O(n^{5/4})$ without any of the extra logarithmic factors present in the previous algorithm of Le Gall [FOCS'14].
Crew prams and decision trees
N. Nisan · 1991
Earlier work this paper cites.
A fast quantum mechanical algorithm for database search
L. Grover · 1996
Earlier work this paper cites.
Algorithms for quantum computation: Discrete logarithm and factoring
P. Shor · 1997
Earlier work this paper cites.
Quantum lower bounds by polynomials
R. Beals, H. Buhrman, R. Cleve, M. Mosca, and R. de Wolf · 2001
Earlier work this paper cites.
Quantum algorithms for element distinctness
H. Buhrman, C. Dürr, M. Heiligman, P. Høyer, F. Magniez, M. Santha, and R. de Wolf · 2005
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
P. Høyer, T. Lee, and R. Š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.
Quantum search with variable times
A. Ambainis · 2010
Cited alongside, same era.
Quantum algorithm for k-distinctness with prior knowledge on the input
A. Belovs and T. Lee · 2011
Cited alongside, same era.
Quantum query complexity of state conversion
T. Lee, R. Mittal, B. Reichardt, R. Špalek, and M. Szegedy · 2011
Cited alongside, same era.
Search via quantum walk
F. Magniez, A. Nayak, J. Roland, and M. Santha · 2011
Cited alongside, same era.
Reflections for quantum query algorithms
B. Reichardt · 2011
Cited alongside, same era.
Learning-graph-based quantum algorithm for k-distinctness
A. Belovs · 2012
Cited alongside, same era.
Time-efficient quantum walks for 3-distinctness
A. Belovs, A. Childs, S. Jeffery, R. Kothari, and F. Magniez · 2013
Later among the works it cites.
On the power of non-adaptive learning graphs
A. Belovs and A. Rosmanis · 2013
Later among the works it cites.
Improved quantum algorithm for triangle finding via combinatorial arguments
F. Le Gall · 2014
Later among the works it cites.
Quantum algorithm for triangle finding in sparse graphs
F. Le Gall and S. Nakajima · 2015
Later among the works it cites.
Improved quantum query algorithms for triangle finding and associativity testing
T. Lee, F. Magniez, and M. Santha · 2015
Later among the works it cites.
Separations in query complexity using cheat sheets
S. Aaronson, S. Ben-David, and R. Kothari · 2016
Closest in time.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Span programs for functions with constant-sized 1-certificates
A. Belovs · 2012
Cited alongside, same era.
Separations in query complexity based on pointer functions
A. Ambainis, K. Balodis, A. Belovs, T. Lee, M. Santha, and J. Smotrovs · 2016
Closest in time.