Marche aléatoire quantique

Classique vs quantique : même marche, propagation radicalement différente

Exemple résolu — Marche aléatoire quantique

Ratio quantique/classique	2.0775×
Pic quantique	0.2816

Ce sont les valeurs affichées par le calculateur à l’ouverture de la page. Modifiez une entrée ci-dessus pour les recalculer.

Chargement de la simulation interactive...

Des marches aléatoires à la recherche 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.

diffusion contre sprint balistique 🖖

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 quantique n'oublie jamais 🖖

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.

Problème entièrement résolu

Dispersions pour 2 marcheurs sur 10 pas 9 étapes
10 pas, 2 marcheurs. L'un lance une pièce équilibrée à chaque pas et se déplace de ±1. L'autre commence dans l'état de pièce |0⟩ et subit la porte de Hadamard sur sa pièce avant chaque déplacement. Calculez exactement l'écart-type de chacun, puis indiquez le nombre de pas nécessaires au marcheur classique pour couvrir la même distance.
1. Les pas classiques sont indépendants, et chacun apporte une variance d'exactement 1, de sorte que les variances s'additionnent. Cette seule ligne constitue toute la réponse classique — et c'est la raison pour laquelle le panneau ci-dessus affiche une racine carrée plutôt qu'une simulation.
  
  $σ_{c}^{2} = 10 1 + 1 + \dots + 1 = 10 ⟹ σ_{c} = 10 = 3.1623$
2. Le marcheur quantique ne choisit jamais une branche. Conservez 2 amplitudes à chaque site, une par valeur de pièce ; la porte de Hadamard les remplace par leur somme et leur différence, puis la moitié |0⟩ se déplace vers la gauche tandis que la moitié |1⟩ se déplace vers la droite. Un site peut recevoir de ses deux voisins, ainsi les amplitudes s'additionnent — et une différence peut valoir 0.
  
  $(a_{0}, a_{1})_{x} ⟶ \frac{a _{0} + a _{1}}{2} (1, 0)_{x - 1} + \frac{a _{0} - a _{1}}{2} (0, 1)_{x + 1}$
3. Partez de l'origine avec (1, 0) et effectuez 2 pas. Extrayez le facteur 1/√2 de chaque pas pour que les amplitudes restent des entiers ; ainsi, après le pas n, les paires ci-dessous sont toutes divisées par 2^n/2.
  
  $n = 1 : (1, 0)_{- 1}, (0, 1)_{+ 1} n = 2 : (1, 0)_{- 2}, (1, 1)_{0}, (0, - 1)_{+ 2}$
4. C'est au pas 3 que la symétrie s'effondre. Le site à l'origine contient (1, 1) : il envoie 1 + 1 = 2 vers la gauche et 1 − 1 = 0 vers la droite. Le signe moins de la ligne inférieure de Hadamard a effacé toute la contribution de ce site vers la droite, et x = −1 porte désormais 5 fois la probabilité de x = +1.
  
  $n = 3 : (1, 0)_{- 3}, (2, 1)_{- 1}, (- 1, 0)_{+ 1}, (0, 1)_{+ 3} ⟹ p (- 1) = \frac{5}{8}, p (+ 1) = \frac{1}{8}$
5. Poursuivez jusqu'au pas 10. Les amplitudes sont toujours des entiers sur 2⁵, de sorte que chaque probabilité est un entier sur 1024 — les 11 numérateurs ci-dessous sont exacts, et leur somme vaut 1024.
  
  $n = 10 : 1024 p (x) = 1, 82, 449, 64, 100, 72, 52, 64, 89, 50, 1 (x = - 10, - 8, \dots, + 10)$
6. Lisez le plus grand numérateur directement dans la liste. Il vaut 449 et se situe en x = −6, bien à l'écart de l'origine et du bord opposé.
  
  $x max p_{q} (x) = p_{q} (- 6) = \frac{449}{1024} = 0.4385$
7. La moyenne n'est pas 0. |0⟩ est la moitié de la pièce qui se déplace vers la gauche, et le pas 3 a déjà montré qu'elle prenait la plus grande part, si bien que l'ensemble de la distribution penche de ce côté.
  
  $μ = x \sum x p (x) = - \frac{2512}{1024} = - 2.4531$
8. La variance est la moyenne des carrés moins le carré de la moyenne, et les deux sommes proviennent des 11 mêmes numérateurs — aucune nouvelle information n'est nécessaire.
  
  $σ_{q}^{2} = x \sum x^{2} p (x) - μ^{2} = \frac{30672}{1024} - 6.0177 = 23.935 ⟹ σ_{q} = 4.8924$
9. Divisez par l'écart-type classique du pas 1.
  
  $\frac{σ _{q}}{σ _{c}} = \frac{4.8924}{3.1623} = 1.5471$
Réponse

σ_q = 4,8924 contre σ_c = 3,1623 — soit un rapport de 1,5471 — avec le pic quantique en p_q(−6) = 0,4385. Interprétez maintenant cette variance comme un nombre de pas. L'écart-type d'un marcheur classique est √M, donc égaler 4,8924 nécessite M = σ_q² = 23,9, disons 24 pas : 2,4 fois plus de travail pour obtenir la même portée après 10. Le nombre de pas classique est le carré du rapport des écarts-types, et c'est ce qu'il convient de retenir — un avantage de 2× sur l'écart-type représente un avantage de 4× sur le nombre de pas.

$M = σ_{q}^{2} = 23.9 \approx 24, \frac{M}{N} = (\frac{σ _{q}}{σ _{c}})^{2} = 1.547 1^{2} = 2.394$

Références (2)

Insight block 1 — the coined walk this tool steps through: Y. Aharonov, L. Davidovich and N. Zagury, "Quantum random walks." Physical Review A 48(2), 1687–1690, 1993.
And the exponential separation block 1 names: A. M. Childs, R. Cleve, E. Deotto, E. Farhi, S. Gutmann and D. A. Spielman, "Exponential algorithmic speedup by a quantum walk." Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 59–68, 2003.

Par l’équipe 42Math · Mis à jour 2026-05-22

Vérifié sur des sources publiées. Corrections bienvenues. Politique éditoriale · Corrections

Toutes les leçons : Informatique →

Exemples de problèmes

10 pas - 10 pas — doubles pics asymétriques déjà visibles
30 pas - 30 pas — dispersion quantique nettement plus large que la classique
50 pas - 50 pas — dispersion quantique en O(N) contre O(√N) pour le cas classique
Pièce équilibrée - 20 pas, pièce équilibrée — distribution symétrique à deux pics