MilestoneTheory & algorithmsConfirmed

Ambainis uses a quantum walk to find duplicates optimally

Nov 1, 2003

Andris Ambainis uses quantum walks to find two equal items among N with about N^(2/3) queries, compared with about N for classical methods. This matches a known lower bound, so no quantum algorithm can do better in this setting.

Why it matters

It turned quantum walks into a general tool for designing quantum search algorithms with polynomial speedups.

Andris Ambainis

See it on the timeline

Related

• A quantum walk gives an exponential speedup for a black-box problem (Sep 24, 2002)
• Childs shows quantum walks can implement universal quantum computation (Jun 12, 2008)
• Lov Grover finds a quantum algorithm for faster unstructured search (May 1996)