Quanten-Zufallsspaziergang

Klassisch vs. Quanten: gleicher Spaziergang, völlig andere Ausbreitung

Rechenbeispiel — Quanten-Zufallsspaziergang

Quanten/Klassisch-Verhältnis	2.0775×
Quanten-Maximum	0.2816

Das sind die Werte, die der Rechner beim Öffnen der Seite anzeigt. Ändere oben eine Eingabe, um sie neu zu berechnen.

Interaktive Simulation wird geladen...

Von Zufallsspaziergängen zur Quantensuche 🖖

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.

Diffusion gegen ballistischen Sprint 🖖

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.

eine Quantenirrfahrt vergisst nie 🖖

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.

Aufgabe vollständig gelöst

Ausbreitungen für 2 Walker über 10 Schritte 9 Schritte
10 Schritte, 2 Wanderer. Einer wirft bei jedem Schritt eine faire Münze und bewegt sich um ±1. Der andere startet im Münzzustand |0⟩; auf seine Münze wird vor jedem Schritt das Hadamard-Gatter angewendet. Berechnen Sie beide Streuungen exakt und geben Sie dann an, wie viele Schritte der klassische Wanderer benötigt, um die gleiche Distanz abzudecken.
1. Klassische Schritte sind unabhängig und jeder trägt eine Varianz von genau 1 bei, sodass sich die Varianzen addieren. Diese eine Zeile ist bereits die gesamte klassische Antwort — und sie ist der Grund, warum das Feld oben eine Quadratwurzel anstelle einer Simulation ausgibt.
  
  $σ_{c}^{2} = 10 1 + 1 + \dots + 1 = 10 ⟹ σ_{c} = 10 = 3.1623$
2. Der Quantenwanderer wählt nie einen Pfad. Führen Sie an jedem Ort 2 Amplituden mit, eine pro Münzwert; das Hadamard-Gatter ersetzt diese durch ihre Summe und ihre Differenz, woraufhin sich die |0⟩-Hälfte nach links und die |1⟩-Hälfte nach rechts bewegt. Ein Ort kann Beiträge von beiden Nachbarn empfangen, sodass sich Amplituden addieren — und eine Differenz 0 ergeben kann.
  
  $(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. Beginnen Sie am Ursprung mit (1, 0) und führen Sie 2 Schritte aus. Klammern Sie bei jedem Schritt den Faktor 1/√2 aus, damit die Amplituden ganze Zahlen bleiben; nach Schritt n sind die unten stehenden Paare somit alle durch 2^n/2 geteilt.
  
  $n = 1 : (1, 0)_{- 1}, (0, 1)_{+ 1} n = 2 : (1, 0)_{- 2}, (1, 1)_{0}, (0, - 1)_{+ 2}$
4. In Schritt 3 bricht die Symmetrie. Der Ort am Ursprung enthält (1, 1): Er sendet 1 + 1 = 2 nach links und 1 − 1 = 0 nach rechts. Das Minuszeichen in der untersten Zeile des Hadamard-Gatters hat den gesamten nach rechts gerichteten Beitrag dieses Orts ausgelöscht, und auf x = −1 entfällt nun die 5-fache Wahrscheinlichkeit von 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. Führen Sie die Berechnung bis Schritt 10 fort. Die Amplituden sind weiterhin ganze Zahlen geteilt durch 2⁵, sodass jede Wahrscheinlichkeit eine ganze Zahl geteilt durch 1024 ist — die 11 unten stehenden Zähler sind exakt und summieren sich zu 1024.
  
  $n = 10 : 1024 p (x) = 1, 82, 449, 64, 100, 72, 52, 64, 89, 50, 1 (x = - 10, - 8, \dots, + 10)$
6. Lesen Sie den größten Zähler direkt aus der Liste ab. Er beträgt 449 und liegt bei x = −6, weit entfernt sowohl vom Ursprung als auch vom äußeren Rand.
  
  $x max p_{q} (x) = p_{q} (- 6) = \frac{449}{1024} = 0.4385$
7. Der Mittelwert ist nicht 0. |0⟩ ist diejenige Hälfte der Münze, die sich nach links bewegt, und Schritt 3 hat bereits gezeigt, dass sie den größeren Anteil erhält, sodass sich die gesamte Verteilung dorthin neigt.
  
  $μ = x \sum x p (x) = - \frac{2512}{1024} = - 2.4531$
8. Die Varianz ist das mittlere Quadrat minus das Quadrat des Mittelwerts, und beide Summen stammen aus denselben 11 Zählern — es werden keine neuen Informationen benötigt.
  
  $σ_{q}^{2} = x \sum x^{2} p (x) - μ^{2} = \frac{30672}{1024} - 6.0177 = 23.935 ⟹ σ_{q} = 4.8924$
9. Dividieren Sie durch die klassische Streuung aus Schritt 1.
  
  $\frac{σ _{q}}{σ _{c}} = \frac{4.8924}{3.1623} = 1.5471$
Antwort

σ_q = 4,8924 gegenüber σ_c = 3,1623 — ein Verhältnis von 1,5471 — mit dem Quanten-Peak bei p_q(−6) = 0,4385. Fassen Sie diese Varianz nun als Schrittzahl auf. Die Streuung eines klassischen Wanderers beträgt √M; um 4,8924 zu erreichen, benötigt man also M = σ_q² = 23,9, gerundet 24 Schritte: das 2,4-Fache des Aufwands für dieselbe Reichweite nach 10. Die klassische Schrittzahl ist das Quadrat des Streuungsverhältnisses, und das ist die entscheidende Erkenntnis — ein 2× Vorteil bei der Streuung ist ein 4× Vorteil bei den Schritten.

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

Quellen (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.

Vom 42Math-Team · Aktualisiert 2026-05-22

Anhand veröffentlichter Quellen geprüft. Korrekturen willkommen. Redaktionsrichtlinie · Korrekturen

Alle Lektionen: Informatik →

Beispielaufgaben

10 Schritte - 10 Schritte — asymmetrische Doppelspitzen bereits sichtbar
30 Schritte - 30 Schritte — die Quantenverteilung ist deutlich breiter als die klassische
50 Schritte - 50 Schritte — Quantenverteilung mit O(N) gegenüber klassischem O(√N)
Balancierte Münze - 20 Schritte, fairer Münzwurf — symmetrische Verteilung mit zwei Spitzen