2008

Quantum walk based search algorithms

Santha, Miklos

Understand

In this survey paper we give an intuitive treatment of the discrete time quantization of classical Markov chains.

Grover search and the quantum walk based search algorithms of Ambainis, Szegedy and Magniez et al.
will be stated as quantum analogues of classical search procedures.
We present a rather detailed description of a somewhat simplified version of the MNRS algorithm.

Built on

D. Knuth. Sorting and Searching
1973
Earlier work this paper cites.
P. Halmos. Finite-dimensional vector spaces
1974
Earlier work this paper cites.
In Proc. of the 20th Symposium on Foundations of Computer Science
R. Aleliunas, R. Karp, R. Lipton, L. Lovász, and C. Rackoff. Random Walks, Universal Traversal Sequences, and the Complexity of Maze Problems · 1979
Earlier work this paper cites.
A fast quantum mechanical algorithm for database search
L. Grover · 1996
Earlier work this paper cites.
Quantum measurements and the abelian stabilizer problem
A. Kitaev · 1996
Earlier work this paper cites.
From quantum cellular automata to quantum lattice gases
D. Meyer · 1996
Earlier work this paper cites.
On the abscence of homogeneous scalar unitary cellular automata
D. Meyer · 1996
Earlier work this paper cites.
Strengths and weaknesses of quantum computing
C. Bennett, E. Bernstein, G. Brassard, and U. Vazirani · 1997
Earlier work this paper cites.
Quantum algorithms revisited
R. Cleve, A. Ekert, C. Macchiavello, and M. Mosca · 1998
Earlier work this paper cites.
On the power of quantum computation
U. Vazirani · 1998
Earlier work this paper cites.
Quantum walk on the line
A. Nayak and A. Vishwanath · 2000
Earlier work this paper cites.
I. Pak. Testing commutativity of a group and the power of randomization. Electronic version at http://www-math.mit.edu/ pak/research.html, 2000
2000
Earlier work this paper cites.
Quantum walks on graphs
D. Aharonov, A. Ambainis, J. Kempe, and U. Vazirani · 2001
Earlier work this paper cites.

Similar

One-dimensional quantum walks
A. Ambanis, E. Bach, A. Nayak, A. Vishwanath, and J. Watrous · 2001
Cited alongside, same era.
T. Cormen, C. Leiserson, R. Rivest, and C. Stein. Introduction to Algorithms
2001
Cited alongside, same era.
Quantum simulations of classical random walks and undirected graph connectivity
J. Watrous · 2001
Cited alongside, same era.
Quantum amplitude amplification and estimation
G. Brassard, P. Høyer, M. Mosca, and A. Tapp · 2002
Cited alongside, same era.
C. Moore, and Alexander Russell. Quantum Walks on the Hypercube. In Proc. of the 6th International Workshop on Randomization and Approximation Techniques in Computer Science
2002
Cited alongside, same era.
U. Schöning. A Probabilistic Algorithm for k -SAT Based on Limited Local Search and Restart. Algorithmica
2002
Cited alongside, same era.
A. Ambainis. Quantum walks and their algorithmic applications. International Journal of Quantum Information
2003
Cited alongside, same era.
Quantum search on bounded-error inputs
P. Høyer, M. Mosca, and R. de Wolf · 2003
Cited alongside, same era.
J. Kempe. Discrete Quantum Walks Hit Exponentially Faster. In Proc. of the International Workshop on Randomization and Approximation Techniques in Computer Science
2003
Cited alongside, same era.
J. Kempe. Quantum random walks – an introductory survey, Contemporary Physics
2003
Cited alongside, same era.
Quantum random-walk search algorithm
N. Shenvi, J. Kempe, and K.B. Whaley · 2003
Cited alongside, same era.
Quantum lower bounds for the collision and the element distinctness problems
S. Aaronson and Y. Shi · 2004
Cited alongside, same era.

Then

A. Ambainis. Quantum search algorithms. SIGACT News
2004
Later among the works it cites.
Quantum Speed-Up of Markov Chain Based Algorithms
M. Szegedy · 2004
Later among the works it cites.
Quantum search of spatial regions
S. Aaronson and A. Ambainis · 2005
Later among the works it cites.
Coins make quantum walks faster
A. Ambainis, J. Kempe, and A. Rivosh · 2005
Later among the works it cites.
Quantum verification of matrix products
H. Buhrman and R. Spalek · 2006
Later among the works it cites.
Quantum Walk Algorithm for Element Distinctness. SIAM Journal on Computing
A. Ambainis · 2007
Later among the works it cites.
S. Dörn, and T. Thierauf. The Quantum Query Complexity of Algebraic Properties. In Proc. of the 16th International Symposium on Fundamentals of Computation Theory
2007
Later among the works it cites.
Quantum complexity of testing group commutativity. Algorithmica
F. Magniez and A. Nayak · 2007
Later among the works it cites.
In Proc. of the 39th ACM Symposium on Theory of Computing
F. Magniez, A. Nayak, J. Roland, and M. Santha. Search via quantum walk · 2007
Later among the works it cites.
Quantum Algorithms for the Triangle Problem
F. Magniez, M. Santha, and M. Szegedy · 2007
Later among the works it cites.
Almost uniform sampling via quantum walks
P. Richter · 2007
Later among the works it cites.
F. Magniez and A. Nayak. Personal communication, 2008
2008
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…