Fetching the paper…
Reading the bibliography…
We present a quantum algorithm solving the $k$-distinctness problem in $O(n^{1-2^{k-2}/(2^k-1)})$ queries with a bounded error.
Tight bounds on quantum searching
M. Boyer, G. Brassard, P. Høyer, and A. Tapp · 1998
Earlier work this paper cites.
Quantum counting
G. Brassard, P. Høyer, and A. Tapp · 1998
Earlier work this paper cites.
Quantum lower bounds by quantum arguments
A. Ambainis · 2002
Earlier work this paper cites.
Complexity measures and decision tree complexity: a survey
H. Buhrman and R. de Wolf · 2002
Earlier work this paper cites.
Quantum lower bounds for the collision and the element distinctness problems
S. Aaronson and Y. Shi · 2004
Earlier work this paper cites.
Quantum speed-up of markov chain based algorithms
M. Szegedy · 2004
Earlier work this paper cites.
Polynomial degree and lower bounds in quantum complexity: Collision and element distinctness with small range
A. Ambainis · 2005
Earlier work this paper cites.
Quantum algorithms for subset finding
A. Childs and J. Eisenberg · 2005
Earlier work this paper cites.
Quantum lower bound for the collision problem with small range
S. Kutin · 2005
Earlier work this paper cites.
Quantum verification of matrix products
H. Buhrman and R. Špalek · 2006
Cited alongside, same era.
Quantum walk algorithm for element distinctness
A. Ambainis · 2007
Cited alongside, same era.
The quantum query complexity of algebraic properties
S. Dörn and T. Thierauf · 2007
Cited alongside, same era.
Negative weights make adversaries stronger
P. Høyer, T. Lee, and R. Špalek · 2007
Cited alongside, same era.
Search via quantum walk
F. Magniez, A. Nayak, J. Roland, and M. Santha · 2007
Cited alongside, same era.
Quantum algorithms for the triangle problem
F. Magniez, M. Santha, and M. Szegedy · 2007
Cited alongside, same era.
A learning graph based quantum query algorithm for finding constant-size subgraphs
T. Lee, F. Magniez, and M. Santha · 2011
Later among the works it cites.
Quantum query complexity of the state conversion problem
T. Lee, R. Mittal, B. Reichardt, R. Špalek, and M. Szegedy · 2011
Later among the works it cites.
Reflections for quantum query algorithms
B. Reichardt · 2011
Later among the works it cites.
Quantum query complexity of subgraph containment with constant-sized certificates
Y. Zhu · 2011
Later among the works it cites.
Span programs for functions with constant-sized 1-certificates
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
A. Ambainis · 2011
Cited alongside, same era.
Quantum algorithm for k k -distinctness with prior knowledge on the input
A. Belovs and T. Lee · 2011
Cited alongside, same era.
Personal communication, 2011
R. Kothari · 2011
Cited alongside, same era.
A. Belovs · 2012
Closest in time.
Span programs and quantum algorithms for s t st -connectivity and claw detection
A. Belovs and B. Reichardt · 2012
Closest in time.
Adversary lower bound for the k k -sum problem
A. Belovs and R. Špalek · 2012
Closest in time.
Improving quantum query complexity of boolean matrix multiplication using graph collision
S. Jeffery, R. Kothari, and F. Magniez · 2012
Closest in time.