Quantenwanderungen auf Graphen

Wir legen die Grundlagen für eine Theorie der Quantenwanderungen auf Graphen – die Generalisierung von Zufallswanderungen auf endlichen Graphen in die Quantenwelt. Solche Quantenwanderungen konvergieren nicht zu einer stationären Verteilung, da sie unitär und umkehrbar sind. Durch geeignete Lockerung der Definition können wir jedoch ein Maß dafür erhalten, wie schnell sich die Quantenwanderung ausbreitet oder wie sehr die Quantenwanderung in einer kleinen Nachbarschaft bleibt. Wir geben Definitionen von Mischzeit, Füllzeit und Dispersionzeit. Wir zeigen, dass in all diesen Maßzahlen die Quantenwanderung im Zyklus fast quadratisch schneller ist als ihr klassischer Gegenpart. Andererseits geben wir eine untere Grenze für die mögliche Beschleunigung durch Quantenwanderungen für allgemeine Graphen an, die zeigt, dass Quantenwanderungen höchstens polynomial schneller sein können als ihre klassischen Gegenstücke.