Fetching the paper…
Reading the bibliography…
In this paper we present a quantum algorithm solving the triangle finding problem in unweighted graphs with query complexity $\tilde O(n^{5/4})$, where $n$ denotes the number of vertices in the graph.
Finding a minimum circuit in a graph
Itai, A., and Rodeh, M · 1978
Earlier work this paper cites.
A fast quantum mechanical algorithm for database search
Grover, L. K · 1996
Earlier work this paper cites.
Quantum counting
Brassard, G., Høyer, P., and Tapp, A · 1998
Earlier work this paper cites.
Almost optimal (on the average) combinatorial algorithms for Boolean matrix product witnesses, computing the diameter (extended abstract)
Schnorr, C.-P., and Subramanian, C. R · 1998
Earlier work this paper cites.
Quantum amplitude amplification and estimation
Brassard, G., Høyer, P., Mosca, M., and Tapp, A · 2002
Earlier work this paper cites.
Complexity measures and decision tree complexity: a survey
Buhrman, H., and de Wolf, R · 2002
Earlier work this paper cites.
Quantum search on bounded-error inputs
Høyer, P., Mosca, M., and de Wolf, R · 2003
Earlier work this paper cites.
On the quantum query complexity of detecting triangles in graphs
Szegedy, M · 2003
Earlier work this paper cites.
Quantum speed-up of markov chain based algorithms
Szegedy, M · 2004
Earlier work this paper cites.
Quantum algorithms for element distinctness
Buhrman, H., Dürr, C., Heiligman, M., Høyer, P., Magniez, F., Santha, M., and de Wolf, R · 2005
Earlier work this paper cites.
Quantum walk algorithm for element distinctness
Ambainis, A · 2007
Cited alongside, same era.
Negative weights make adversaries stronger
Høyer, P., Lee, T., and Spalek, R · 2007
Cited alongside, same era.
Quantum algorithms for the triangle problem
Magniez, F., Santha, M., and Szegedy, M · 2007
Cited alongside, same era.
Finding a heaviest vertex-weighted triangle is not harder than matrix multiplication
Czumaj, A., and Lingas, A · 2009
Cited alongside, same era.
Span programs and quantum query complexity: The general adversary bound is nearly tight for every Boolean function
Reichardt, B · 2009
Cited alongside, same era.
Quantum search with variable times
Ambainis, A · 2010
Cited alongside, same era.
Learning-graph-based quantum algorithm for k k -distinctness
Belovs, A · 2012
Later among the works it cites.
Span programs for functions with constant-sized 1-certificates: extended abstract
Belovs, A · 2012
Later among the works it cites.
Multiplying matrices faster than Coppersmith-Winograd
Vassilevska Williams, V · 2012
Later among the works it cites.
Time-efficient quantum walks for 3-distinctness
Belovs, A., Childs, A. M., Jeffery, S., Kothari, R., and Magniez, F · 2013
Later among the works it cites.
On the power of non-adaptive learning graphs
Belovs, A., and Rosmanis, A · 2013
Later among the works it cites.
Nested quantum walks with quantum data structures
Jeffery, S., Kothari, R., and Magniez, F · 2013
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Towards polynomial lower bounds for dynamic problems
Patrascu, M · 2010
Cited alongside, same era.
Subcubic equivalences between path, matrix and triangle problems
Vassilevska Williams, V., and Williams, R · 2010
Cited alongside, same era.
Search via quantum walk
Magniez, F., Nayak, A., Roland, J., and Santha, M · 2011
Cited alongside, same era.
Regularity lemmas and combinatorial algorithms
Bansal, N., and Williams, R · 2012
Cited alongside, same era.
Improved quantum query algorithms for triangle finding and associativity testing
Lee, T., Magniez, F., and Santha, M · 2013
Later among the works it cites.
Finding, minimizing, and counting weighted subgraphs
Vassilevska Williams, V., and Williams, R · 2013
Later among the works it cites.
Powers of tensors and fast matrix multiplication
Le Gall, F · 2014
Closest in time.
Faster all-pairs shortest paths via circuit complexity
Williams, R · 2014
Closest in time.