Einmalige Quantenschlagzeiten

In der Arbeit Quantum Random Walks Hit Exponential Faster ( arXiv: quant-ph / 0205083 ) gibt Kempe eine Vorstellung von der Schlagzeit für Quantum Walks (im Hypercube), die in der Literatur zu Quantum Walks nicht sehr populär ist. Es ist wie folgt definiert:

One-Shot Quantum Hitting Time: Ein zeitdiskreter Quantum Walk hat eine One-Shot -Schlagzeit, wenn wobei der Ausgangszustand ist, der Zielzustand ist und die Trefferwahrscheinlichkeit ist.( | ≤ 0 ≤ , | ≤ f ≤ ) | ⟨ & PSgr; f | U T | Ψ 0 ⟩ | 2 ≥ p | Ψ 0 ⟩ | Ψ f ⟩ p > $(T,p)$$(|\Psi_0\rangle,|\Psi^f\rangle)$$|\langle\Psi^f|U^T|\Psi_0\rangle|^2 \geq p$$|\Psi_0\rangle$$|\Psi^f\rangle$$p>0$

Normalerweise möchten Sie das Minimum so kennen, dass . Es ist nicht möglich (korrigieren Sie mich, wenn ich mich irre), einen Begriff für die durchschnittliche Schlagzeit zu definieren, da Sie während des Gehens Messungen vornehmen müssen, die zu einem klassischen Gehen zusammenfallen würden. Deshalb haben wir den One-Shot-Begriff. In derselben Arbeit gibt es eine Anwendung auf das Quantenrouting (vgl. Abschnitt 5 ).p > $T$$p>0$

Um zu wissen, dass die Wanderung am Zielscheitelpunkt angekommen ist, müssen Sie nur an diesem Knoten eine Messung durchführen. Zum Beispiel im dimensionalen Hypercube mit Knoten, wenn Sie am Knoten und als Zielknoten zeigt das Papier, dass mit begrenzter Fehlerwahrscheinlichkeit, dh da sehr groß wird. Um also zu erkennen, dass der Fußweg zu Sie nach Schritten eine Messung durch . Dies ist eine exponentielle Beschleunigung.$n$$2^n$$|\Psi_0\rangle=|00\dots00\rangle$$|\Psi^f\rangle=|11\dots11\rangle$$T=O(n)$$p\to 1$$n$$|11\dots11\rangle$$\Omega(n)$

Fragen:

1. Um diesen Begriff der Trefferzeit für die Suche zu verwenden, müssen Sie mindestens den Abstand des Zielscheitelpunkts vom Ursprung kennen, da Sie wissen, wann Sie Ihre Messung anwenden müssen. Nehmen wir an, Sie haben einen Graphen und setzen ihn als Anfangsscheitelpunkt und möchten . Es sei auch angenommen, dass und . Nun,v 0 v f T = O ( d i s t ( v 0 , v f ) ) p ≥ 1 / 2 $G$$v_0$$v^f$$T=O(dist(v_0,v^f))$$p\geq 1/2$$T$ist offensichtlich, weil Sie mindestens so viele Schritte benötigen, um es zu erreichen. Ist es sinnvoll, diese Zeit für die Suche zu nutzen? Wenn Sie wissen, wo sich der Knoten befindet, die Suche keine Bedeutung hat, aber eine Information wie "Abstand vom Startscheitelpunkt" hat, aber nicht genau weiß, wo sich das Ziel befindet, ist dieser Begriff der Schlagzeit von Interesse (lohnt es sich zu studieren) ) Suchalgorithmus?

2. Ist die Anwendung auf das Quantenrouting sinnvoll? In dem Papier heißt es, dass es zum Weiterleiten von Paketen verwendet werden kann, aber es scheint mir, dass Sie nur 1 Bit senden können, zB ist es am Ziel angekommen oder nicht? Können Sie in diesem Rahmen tatsächlich einen Quantenzustand senden? In dem Artikel wird dieses Problem nicht angesprochen.

3. Dies ist vielleicht eine dumme Frage, aber hier geht es. Können Sie diesen Begriff der Schlagzeit für die Konstruktion eines "Generalisierten Mach-Zender-Interferometers" verwenden?

Ich bin mir bewusst , die anderen Vorstellungen von Zeiten für Quanten Wanderungen (wie das Schlagen Szegedy oder Ambainis ist ). Ich interessiere mich besonders für diese bestimmte Schlagzeit.

Update (24.09.2010): Dank Joe Fitzsimons wurden die Fragen 2 und 3 vollständig beantwortet. Obwohl die Frage Nummer 1 immer noch bleibt. Nachdem ich die von Joe und ein paar anderen empfohlene Abhandlung gelesen habe (siehe z. B. arXiv: 0802.1224 ), werde ich zunächst Frage 2 noch einmal genauer erläutern und dann ein konkretes Beispiel dafür geben, was ich vorhabe zu Frage 1.

2 '. Wenn Sie eine konkrete Nachricht senden (wie eine Folge klassischer Bits), können Sie eine kompliziertere Einheit verwenden, die diese Informationen während der Schritte des Spaziergangs kopiert. Um Quantenzustände zu senden, braucht man etwas mehr. Der Spin-Chain-Kanal verwendet eine lineare Anordnung von Qubits mit einer festen Kopplung. Sie können den Zustand (reiner Zustand, ich weiß nicht, ob er für gemischte Zustände funktioniert), den Sie übertragen möchten, an einem Ende angeben und er wird entsprechend den numerischen Ergebnissen mit hoher Wiedergabetreue an das andere Ende gesendet. Ich muss noch mehr darüber nachdenken, aber ich habe zwei Ideen: i) setze eine Kette auf jedes Glied des Graphen oder ii) mache den Gang, finde den Zielzustand, dann mache den Kanal zwischen Anfangszustand und Ziel und sende dann der Staat. Sind diese Ansätze plaussibel? Funktioniert es mit gemischten Staaten?

1 '. Betrachten Sie einen Spaziergang auf einem zweidimensionalen Gitter, das im Ursprung mit Knoten auf jeder Seite mit der Länge √ zentriert ist$n$ . Setzen Sie den Anfangszustand aufv0=(0,0)und den Zielzustand aufvf=($\sqrt{n}$$v_0=(0,0)$wobeia=0,…,$v^f=(\sqrt{n}-1,a)$. Da der Lauf symmetrisch ist, gilt für jedes Ziel an der Grenze des Gitters dieselbe Schlagzeit und dieselben Schlagwahrscheinlichkeiten, wie unten gezeigt.$a=0,\dots,\sqrt{n}-1$

Deshalb ist die Information , die wir haben , ist , dass . Wir können dies nutzen, um zu wissen, wann die Messung durchzuführen ist. Kann die einmalige Schlagzeit verwendet werden, um dieses Raster zu durchsuchen? Hier benötigen Sie diese Informationen. Ein offenes Problem bei der Suche nach einem Gitter ist, dass wir wissen, dassΩ($dist(v_0,v^f)=\Omega(\sqrt{n})$ist eine untere Grenze für die Suche, und für Gitter ist die beste obere GrenzeO($\Omega(\sqrt{n})$. Entweder können wir keinen besseren Algorithmus finden, oder die Techniken zum Nachweisen von Untergrenzen, wenn Sie sie in Gittern verwenden, ergeben eine schwache Untergrenze. Können Sie das zeigen, der einzige Weg, um unter √ zu gehen$O(\sqrt{n\log n})$ hat "eine Information" als diejenige in der Frage? Dies würde bedeuten, eine Untergrenze für Gitter zu beweisen. Macht es irgendeinen Sinn?$\sqrt{n\log n}$

Ich bin mit diesem Artikel nicht so vertraut, aber ich werde versuchen, jede Ihrer Fragen nach einem kurzen Blick grob zu beantworten.

1. Grovers Algorithmus kann in der Tat mit diesem Begriff der Schlagzeit betrachtet werden. Sie müssen entscheiden, wann das System gemessen werden soll, und obwohl T für alle Ergebnisse konstant ist, ist es dennoch wichtig zu berechnen. Hier ist T sicherlich nicht (was in diesem Fall 1 ist), sondern O ( $O(\mbox{dist}(v_0, v^f))$, daher ist Ihre Annahme, dassT=O(dist(v0,vf))ist, hier nicht gültig.$O(\sqrt{n})$$T=O(\mbox{dist}(v_0, v^f))$
2. Ich gehe davon aus, dass der Autor ein ganzes Paket nimmt, um den zufälligen Spaziergang zu machen. Offensichtlich erfordert dies eine etwas kompliziertere Einheit, aber ich sehe kein wirkliches Problem. Alternativ haben Burgarth und Bose ein sehr gutes Schema zum Codieren von Informationen über identische Graphen, das auch funktionieren würde, wenn Sie einfach ihre 1d-Ketten durch das Netzwerk Ihrer Wahl ersetzen ( quant-ph / 0406112 ).
3. Nun, Sie brauchen diese Vorstellung von Zeit nicht ganz. Hypercubes haben eine perfekte Zustandsübertragung (siehe z. B. quant-ph / 0309131 und quant-ph / 0411020 ), sodass Sie den Transport auf einem Hypercube als Interferometer mit dem Mach-Zender-Interferometer anzeigen können, das dem 2d-Fall entspricht.

UPDATE: (Zur Beantwortung der aktualisierten Frage zu zufälligen Gängen auf einem Gitter oder einem anderen Gitter)

Ein Ansatz für das Messproblem, das Sie bei der räumlichen Suche hervorheben, besteht darin, bei jedem Zeitschritt einfach eine Messung durchzuführen, sodass 1 zurückgegeben wird, wenn der Scheitelpunkt, an dem sich der Wanderer gerade befindet (z. B. ), gleich v f und der aktuelle Zeitschritt ist t ist die Schlagzeit für diesen Scheitelpunkt. Dies sollte das Problem des Kollabierens der Wellenfunktion vermeiden, da die Messung nur für jeden Scheitelpunkt durchgeführt wird, sobald der Treffzeitpunkt erreicht ist, und es werden nur Kollabierungen an einer Stelle registriert, wenn diese Stelle das richtige Ergebnis ist.$v_t$$v^f$

In Bezug auf Frage 1 kann die Kenntnis der Entfernung zwischen dem unbekannten Zielscheitelpunkt und einem bekannten Ursprungsscheitelpunkt auf dem Hypercube den Suchprozess unterstützen. Der Wert der Entfernung selbst bestimmt jedoch, wie hilfreich diese Informationen sind.

Typische Quantum-Walk-Algorithmen sind normalerweise Variationen / Approximationen der Grover-Suche: Sie umfassen eine ungefähre Rotation des Zustandsvektors in einem 2-d-Unterraum des gesamten Hilbert-Raums.

Mit diesen Algorithmen können Sie effizient eine annähernd gleichmäßige Überlagerung aller Scheitelpunkte in einem bestimmten Abstand vom Ursprung erstellen. Dann können Sie Ihren Zielscheitelpunkt in dieser Überlagerung mit der Quanten- oder der klassischen Suche (Monte Carlo) suchen: Bei der klassischen Suche müssen Sie nur die Überlagerung vorbereiten und auf der Scheitelpunktbasis messen und wiederholen, bis Sie das Ziel gefunden haben. Für die Quantensuche wird die Überlagerungsvorbereitungsprozedur (und ihre Inverse) zu einer Subroutine, die die Hadamard-Transformation in der Grover-Iteration ersetzt.

$n$$d$$\binom{n}{d}$$\approx \frac{2^n}{\sqrt{\frac{\pi}{2}n}}$$\approx n/2$