Exponential algorithmic speedup by a quantum walk

We construct a black box graph traversal problem that can be solved exponentially faster on a quantum computer than on a classical computer. The quantum algorithm is based on a continuous time quantum walk, and thus employs a different technique from previous quantum algorithms based on quantum Fourier transforms. We show how to implement the quantum walk efficiently in our black box setting. We then show how this quantum walk solves our problem by rapidly traversing a graph. Finally, we prove that no classical algorithm can solve the problem in subexponential time.

• NS
  National Science Foundation

  Award: 0112487
• UD
  U.S. Department of Energy

  Awards: DE-FC02-94ER40818, FC02-94ER40818
• AP
  Alfred P. Sloan Foundation
• HF
  Hertz Foundation
• NS
  National Security Agency
• AN
  Agenția Națională pentru Cercetare și Dezvoltare
• DA
  Deutscher Akademischer Austauschdienst
• IN
  Istituto Nazionale di Fisica Nucleare
• NS
  Natural Sciences and Engineering Research Council of Canada
• AR
  Army Research Office