MilestoneTheory & algorithmsConfirmed

A quantum walk gives an exponential speedup for a black-box problem

Sep 24, 2002

Andrew Childs and colleagues construct a graph-traversal problem that a quantum walk solves exponentially faster than any classical algorithm in the same black-box model. The result is a theoretical separation, not a demonstrated practical advantage.

Why it matters

Quantum walks add a route to exponential algorithmic speedups beyond the Fourier transforms used in algorithms such as Shor's.

Andrew M. Childs · Richard Cleve · Enrico Deotto · Edward Farhi · Sam Gutmann · Daniel A. Spielman

See it on the timeline

Related

• Peter Shor shows a quantum computer could factor large numbers quickly (Nov 1994)
• Lov Grover finds a quantum algorithm for faster unstructured search (May 1996)