Coins make quantum walks faster

By Andris Ambainis, Julia Kempe, Alexander Rivosh. ACM-SIAM Symposium on Discrete Algorithms, 2004

358 citations recorded by the source corpus.

We show how to search N items arranged on a √N × √N grid in time O(√N log N), using a discrete time quantum walk. This result for the first time exhibits a significant difference between discrete time and continuous time walks without coin degrees of freedom. since it has been shown recently that such a continuous time walk needs time Ω(N) to perform the same task. Our result improves on a previous bound for quantum local search by Aaronson and Ambainis. We generalize our result to 3 and more dimensions where the walk yields the optimal performance of O(√N) and give several extensions of quantum walk search algorithms and generic expressions for its performance for general graphs. The coin-flip operation needs to be chosen judiciously: we show that another "natural" choice of coin gives a walk that takes Ω(N) steps. We also show that in 2 dimensions it is sufficient to have a two-dimensional coin-space to achieve the time O(√N log N).

Subfields: Artificial Intelligence, Computer Networks and Communications

View Paper: https://www.semanticscholar.org/paper/515ed8d89d1e6b5b33741a83fe90d14811843a43

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

Citations in the corpus

Quantum walks: a comprehensive review (2012, methodology): “’s quantum walk search algorithm [33], and Ambainis et al.”
On the Relationship Between Continuous- and Discrete-Time Quantum Walk (2008, methodology): “Unlike quantum algorithms for search on low-degree graphs [8, 16, 17, 52], no continuous-time analog of the element distinctness algorithm has been known: the walk takes place on a high-degree Johnson graph, and sparse Hamiltonian techniques are insufficient to implement it.”
QUANTUM WALKS AND THEIR ALGORITHMIC APPLICATIONS (2003, background): “Those algorithms can be classiﬁed into two groups: algorithms achieving exponentially faster hitting times [6, 7, 8, 9] and quantum walk search [10, 11, 12, 13].”
Universal computation by quantum walk. (2008, background): “By exploiting interference effects, quantum walks can outperform random walks at certain computational tasks: there are black-box problems for which quantum walk provides an exponential speedup over classical computation [4, 5], and many quantum walk algorithms achieve polynomial speedup over classi”
Search via quantum walk (2006, background): “Since then, in the frame work of Ambainis or Szegedy, numerous new algorithms emerged with substantially better complexity i n a variety of contexts [5, 20, 13, 19].”
Quantum Walk Based Search Algorithms (2008, methodology): “The search algorithm for the 2-dimensional grid obtained this way, and the one given in [9] have smaller complexity than what follows from Theorem 5.”
Efficient Quantum Algorithms for Simulating Sparse Hamiltonians (2005, background): “Such respresentations of Hamiltonians can arise as encodings of computational problems, such as simulations of quantum walks [6, 7, 8, 9, 10] or adiabatic quantum computations [11].”
Quantum walk algorithm for element distinctness (2003, methodology): “A large eigenvalue gap is, however, not necessary, as shown by quantum search algorithms for grids [ 8 , 37].”