Quantum Information and Computation · 2015 · 18 citations · 8 references
ComputingComputer SciencePhysicsAlgorithmsQuantum ComputingQuantum MechanicsComputational Quantum MechanicsQuantum AlgorithmsQuantum ComputationQuantum SimulationGridsOperatorsQuantum Algorithm Complexity AnalysisQuantum Search AlgorithmsQuantum Simulation AlgorithmsQuantum Walk AlgorithmsQuantum WalksSpatial Search
We study quantum algorithms for spatial search on finite dimensional grids. Patel \textit{et al.}~and Falk have proposed algorithms based on a quantum walk without a coin, with different operators applied at even and odd steps. Until now, such algorithms have been studied only using numerical simulations. In this paper, we present the first rigorous analysis for an algorithm of this type, showing that the optimal number of steps is $O(\sqrt{N\log N})$ and the success probability is $O(1/\log N)$, where $N$ is the number of vertices. This matches the performance achieved by algorithms that use other forms of quantum walks.
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
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
Coins make quantum walks faster
Andris Ambainis, Julia Kempe, Alexander Rivosh · 2005 · 259 citations
Faster quantum-walk algorithm for the two-dimensional spatial search
Avatar Tulsi · Physical Review A · 2008 · 187 citations · Full text
Computing, Computer Science, Physics +11
Quantum random walks do not need a coin toss
Apoorva Patel, K. S. Raghunathan, Pranaw Rungta · Physical Review A · 2005 · 70 citations · Full text