Quanten-Zufallsspaziergang

Die quadratische Beschleunigung des Quanten-Spaziergangs kommt aus Interferenz, nicht aus Wahrscheinlichkeit. Bei jedem Schritt versetzt die Hadamard-Operation die Münze in eine Superposition, sodass der Verschiebungsoperator die Amplitude gleichzeitig nach links und rechts bewegt. Über viele Schritte hinweg löscht sich die Amplitude nahe der Mitte aus — links- und rechtslaufende Beiträge treffen mit entgegengesetzter Phase aufeinander —, während sich die Amplitude nahe ±N/√2 konstruktiv verstärkt. Deshalb liegen die Maxima der Verteilung an den Rändern statt in der Mitte. Derselbe Mechanismus treibt Grovers Suchalgorithmus (ein Walk auf einem Hyperwürfel) sowie Childs' Graphdurchlauf mit exponentieller Beschleunigung an: Quanten-Walks erreichen entfernte Knoten weit schneller als jeder diffusive Prozess.

Ein Random Walk ist nichts weiter als wiederholtes Münzwerfen: Kopf ein Schritt nach rechts, Zahl nach links. Klassisch verschwimmen die Schritte zu einer Glockenkurve — nach 100 Würfen landet man selten mehr als etwa 10 Positionen vom Start entfernt, denn die Streuung wächst wie √N. Ersetzt man die Münze durch eine Quantenmünze, mittelt sich nichts mehr weg: Der Läufer schießt nach außen und erreicht nach denselben 100 Schritten schon ~70 Positionen. Physiker nennen das ballistische Ausbreitung — sie wächst linear mit N statt mit dessen Wurzel.

Ein klassischer Random Walk ist ein Markow-Prozess: Er verliert stetig die Erinnerung an seinen Startpunkt, und aus der Endverteilung allein lässt sich der Ausgangsort nicht rekonstruieren. Der Quantenwalk ist unitär und damit in jedem Schritt exakt umkehrbar. Lässt man die genaue Abfolge aus Hadamard und Verschiebung rückwärts laufen, sammelt sich die verstreute Amplitude wieder zu einem einzigen Peak am Ursprung — nichts geht verloren, und es gibt keine Gleichgewichtsverteilung, in die der Walk zerfließen könnte. Diffusion löscht die Vergangenheit; eine Quantenirrfahrt verbirgt sie nur.