Spatial search by quantum walk

By Andrew M. Childs, Jeffrey Goldstone. 2003

644 citations recorded by the source corpus.

Grover's quantum search algorithm provides a way to speed up combinatorial search, but is not directly applicable to searching a physical database. Nevertheless, Aaronson and Ambainis showed that a database of N items laid out in d spatial dimensions can be searched in time of order {radical}(N) for d>2, and in time of order {radical}(N) poly(log N) for d=2. We consider an alternative search algorithm based on a continuous-time quantum walk on a graph. The case of the complete graph gives the continuous-time search algorithm of Farhi and Gutmann, and other previously known results can be used to show that {radical}(N) speedup can also be achieved on the hypercube. We show that full {radical}(N) speedup can be achieved on a d-dimensional periodic lattice for d>4. In d=4, the quantum walk search algorithm takes time of order {radical}(N) poly(log N), and in d<4, the algorithm does not provide substantial speedup.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

View Paper: https://www.semanticscholar.org/paper/be2115ecadf97f80dfb4f667c9214efdc39b0982

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 Computational Theory and Mathematics

Citations in the corpus

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”
Machine learning \& artificial intelligence in the quantum domain (2017, result): “Similar results have been achieved in a plethora of other scenarios, such as spatial search (Childs and Goldstone, 2004), search over structures (including various quantum walk-based algorithms (Kempe, 2003; Childs et al.”
Coins make quantum walks faster (2004, methodology): “Quantum walks were first applied to this problem by Childs and Goldstone [ CG03 ] who studied the search on the grid by a continous quantum walk.”
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 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].”
Quantum walks: a comprehensive review (2012, positive): “Finally, Childs and Goldstone [115] developed a continuous quantum walk algorithm to solve the search problem in a grid and discovered algorithms that would have an optimal performance of O( √ N ) in grids of 5 or more dimensions.”
On the Relationship Between Continuous- and Discrete-Time Quantum Walk (2008, methodology): “In principle, this could be done using techniques from [15, 16].”
Quantum walk algorithm for element distinctness (2003, methodology): “The algorithms by [36, 22, 8] and current paper solve different problems but all have similar structure.”
Universal quantum computation using the discrete-time quantum walk (2009, background): “lks can be regarded as computational primitives. Discrete and continuous time quantum walks are largely equivalent, one notable diﬀerence is the run-time when using the walk to search a structure. In [12] it was shown that the continuous time walk could only achieve full quadratic speed up on struct”