Algorithmes quantiques

Rentrons maintenant dans le cœur de la création d'algorithmes quantiques. La possibilité pour plusieurs valeurs d'être en superposition est certes à l'origine de l'accélération quantique, mais ce qui différencie la superposition d'un simple mélange statistique classique est avant tout la possibilité qu'ont les amplitudes d'être négatives. Afin d'exploiter cette possibilité, un algorithme quantique est souvent constitué de trois phases :
1. création d'une superposition de tous les chemins de calculs potentiellement utiles ;
2. calcul proprement dit sur chacun de ces chemins ;
3. interférences destructives des chemins ne menant pas à une solution satisfaisante pour ne garder que les chemins utiles.
La dernière étape constitue le savoir-faire de l'algorithmicien quantique. Pourquoi ne pas s'arrêter avant ? Comme nous l'avons vu dans le cas du générateur aléatoire quantique, observer un chemin de calcul ne permet pas de sélectionner ce chemin. En conséquence, nous n'aurions rien fait de plus qu'exécuter un chemin de calcul au hasard, soit une tâche très classique. C'est la troisième étape, qui utilise la nature même de la parallélisation quantique afin de tenter de filtrer les bons chemins avant l'observation.

..., dès qu'il est observé, ou mesuré, le bit quantique change de réalité et devient classique. Cette transformation est probabiliste et non déterminée avant l'observation.