Physical Review A · 2008 · 187 citations · 8 references
ComputingComputer SciencePhysicsAlgorithmsQuantum ComputingQuantum MechanicsComputational ComplexityQuantum AlgorithmsQuantum BitsQuantum ComputationQuantum Algorithm Complexity AnalysisQuantum Search AlgorithmsQuantum Walk AlgorithmsQuantum Walks
We consider the problem of finding a desired item out of $N$ items arranged on the sites of a two-dimensional lattice of size $\sqrt{N}\ifmmode\times\else\texttimes\fi{}\sqrt{N}$. The previous quantum-walk based algorithms take $O(\sqrt{N}\text{ }\text{ln}\text{ }N)$ steps to solve this problem, and it is an open question whether the performance can be improved. We present an algorithm which solves the problem in $O(\sqrt{N\text{ }\text{ln}\text{ }N})$ steps, thus giving an $O(\sqrt{\text{ln}\text{ }N})$ improvement over the known algorithms. The improvement is achieved by controlling the quantum walk on the lattice using an ancilla qubit.
8
Quantum Mechanics Helps in Searching for a Needle in a Haystack
Lov K. Grover · Physical Review Letters · 1997 · 4.4K citations · Full text
Computing, Computer Science, Physics +11
Strengths and Weaknesses of Quantum Computing
Charles H. Bennett, Ethan Bernstein, Gilles Brassard et al. · SIAM Journal on Computing · 1997 · 1.5K citations · Full text
Quantum random-walk search algorithm
Neil Shenvi, Julia Kempe, K. Birgitta Whaley · Physical Review A · 2003 · 1.2K citations · Full text
Computing, Computer Science, Physics +11
Spatial search by quantum walk
Andrew M. Childs, Jeffrey Goldstone · Physical Review A · 2004 · 738 citations · Full text
Computing, Computer Science, Physics +13