Grover
Le Vendredi 14 Avril 2000 à 16h00
(Bell Labs, Murray Hill, USA)
Quantum search and extensions
Résumé/Abstract :
The quantum search algorithm is a technique for searching a
structure of size N in only N½ steps by using the inbuilt
parallelism of quantum mechanics. This was a surprising result and of
great interest to both physicists & computer scientists and has
inspired considerable research. Broadly speaking, there are three
main ideas:
- the original N½ step search algorithm,
- a generalization that enabled the search algorithm to work with
arbitrary quantum operations,
- an extension that enabled the synthesis of arbitrary
superpositions.
This talk will introduce quantum search and briefly describe the
three main ideas.