Marche aléatoire quantique

L'accélération quadratique de la marche quantique provient de l'interférence, et non de la probabilité. À chaque pas, la porte de Hadamard place la pièce en superposition, de sorte que l'opérateur de déplacement fait avancer l'amplitude simultanément vers la gauche et la droite. Au fil de nombreux pas, l'amplitude près du centre s'annule — les contributions se déplaçant vers la gauche et vers la droite arrivent en opposition de phase — tandis que l'amplitude près de ±N/√2 se renforce de façon constructive. C'est pourquoi la distribution culmine sur les bords plutôt qu'au centre. Le même mécanisme est à l'œuvre dans l'algorithme de recherche de Grover (une marche sur un hypercube) et dans le parcours de graphe à accélération exponentielle de Childs : les marches quantiques atteignent des nœuds éloignés bien plus vite qu'aucun processus diffusif ne le pourrait.

Une marche aléatoire n'est qu'une suite de tirages à pile ou face : pile, un pas à droite ; face, un pas à gauche. En version classique, les pas se fondent en une courbe en cloche — après 100 tirages, on dépasse rarement une dizaine de positions depuis le départ, car la dispersion croît comme √N. Remplacez la pièce par une pièce quantique et le marcheur cesse de se moyenner : il file vers l'extérieur et atteint ~70 positions après ces mêmes 100 pas. Les physiciens parlent de propagation balistique : elle croît linéairement avec N, et non comme sa racine carrée.

Une marche aléatoire classique est un processus de Markov : elle perd peu à peu la trace de son point de départ, et le nuage final seul ne permet pas de reconstituer l'origine. La marche quantique est unitaire, donc chaque pas est parfaitement réversible. Faites tourner à l'envers la séquence exacte de Hadamard et de décalage : toute cette amplitude dispersée se rassemble de nouveau en un pic unique à l'origine — aucune information n'est perdue, et la marche n'a aucune distribution d'équilibre vers laquelle relaxer. La diffusion efface l'histoire ; une marche quantique se contente de la cacher.