Spatial search by quantum walk

Andrew M. Childs and Jeffrey Goldstone
Phys. Rev. A 70, 022314 – Published 23 August 2004

Abstract

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 N for d>2, and in time of order Npoly(logN) 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 N speedup can also be achieved on the hypercube. We show that full 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 Npoly(logN), and in d<4, the algorithm does not provide substantial speedup.

  • Figure
  • Figure
  • Figure
  • Figure
  • Received 16 June 2003

DOI:https://doi.org/10.1103/PhysRevA.70.022314

©2004 American Physical Society

Authors & Affiliations

Andrew M. Childs* and Jeffrey Goldstone

  • Center for Theoretical Physics, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139, USA

  • *Electronic address: amchilds@mit.edu
  • Electronic address: goldston@mit.edu

Article Text (Subscription Required)

Click to Expand

References (Subscription Required)

Click to Expand
Issue

Vol. 70, Iss. 2 — August 2004

Reuse & Permissions
Access Options
Author publication services for translation and copyediting assistance advertisement

Authorization Required


×
×

Images

×

Sign up to receive regular email alerts from Physical Review A

Log In

Cancel
×

Search


Article Lookup

Paste a citation or DOI

Enter a citation
×