Einfachster Algorithmus zur intuitiven Demonstration der Quantenbeschleunigung?

8

Was ist der einfachste Algorithmus (wie der Deutsch-Algorithmus und der Grover-Algorithmus ), um die Quantenbeschleunigung intuitiv zu demonstrieren? Und kann dieser Algorithmus intuitiv erklärt werden?

Im Idealfall würde dies auch deutlich machen, wie Quanteninterferenz verwendet wird und warum es nicht möglich oder nützlich ist, nur Interferenz klassischer Wellen zu verwenden .

Steven Sagona
quelle
Welche Art von Beschleunigung (Polynom gegen Exponential) und welche Art von Vorteil (bedingungslos gegen Orakel)?
glS
Macht nichts, solange es klar ist. Exponentielle Beschleunigung könnte jedoch schön zu sehen sein.
Steven Sagona
Die einfachsten Beispiele funktionieren auch mit klassischen Wellen. Tatsächlich können (und müssen) alle Beispiele mit Ausnahme der klassischen Wellen exponentiell viele Pfade in der Anzahl der beteiligten Qubits nehmen.
Norbert Schuch

Antworten:

6

Ich möchte vorschlagen, dass die Periodenfindung (eine Unterroutine des berühmten Shor-Algorithmus, wenn Sie möchten) eine sehr intuitive, exponentielle Beschleunigung zeigt: Es sollte intuitiv klar sein, dass etwas in der Größenordnung von (der Quadratwurzel der Unsicherheit) liegt Δp ) der Periode p der Funktionsauswertungen erforderlich ist klassisch eine unbekannte Periode zu finden p eine Funktion , die in ihren ganzzahligen Eingangswerts seinen periodischen gewährleistet ist. Ich habe absichtlich die geklam- mert so platziert , dass ihr Inhalt den Menschen intuitiv sein wird , die tief in das Geburtstagsparadoxon noch tief verwurzelt sind, für einen superpolynomielle Speedup demonstrieren, ist es ausreichend , intuitiv zu verstehen , dass es irgendwo in der Nähe ist Δp , die richtige AntwortΔp oder ein Polynom davon und nicht so etwas wie die Anzahl der Ziffern vonp,O(logp).

Der Quantenalgorithmus zur Periodenfindung, wie er vom Shor-Algorithmus verwendet wird, nimmt einfach die Quanten-Fourier-Transformation der periodischen Funktion, die auf die gleiche Überlagerung aller Zustände angewendet wird. Natürlich können dann nur ganzzahlige Vielfache der Periode eine Wahrscheinlichkeitsamplitude ungleich Null haben. Wenn Sie dies (normalerweise) zweimal tun, können Sie den gemeinsamen Faktor schnell als größten gemeinsamen Nenner extrahieren. Eine Quanten-Fourier-Transformation kann jedoch trivial durch O(logp) gesteuerte Rotationen (eine pro jedes Eingangsbit) implementiert werden .

O(logp)O(Δp)pO(p)

Pyramiden
quelle
4

Die Schwierigkeit bei der Frage ist das Wort intuitiv . Die Intuition spiegelt im Wesentlichen unser Verständnis der Welt um uns herum wider, das von der klassischen Physik beschrieben wird. Die Quantenmechanik ist genau das Regime, in dem unsere Intuition zusammenbricht, weil sie ganz anders funktioniert als die Welt unserer alltäglichen Erfahrung. Wie Terry Pratchett sagte:

Es ist sehr schwer, Quanten mit einer Sprache zu sprechen, die ursprünglich entwickelt wurde, um anderen Affen zu sagen, wo sich die reifen Früchte befinden.

Genau diesen Unterschied nutzen wir, um die Rechengeschwindigkeit zu erhöhen.

Es gibt eine Reihe von Standardalgorithmen, die die meisten Quantencomputertexte durchlaufen: Deutschs Algorithmus, Deutsch-Jozsa , Simon / Bernstein-Vazirani. Diese werden ausgewählt, weil sie am einfachsten zu verstehen sind. Sie haben alle im Großen und Ganzen die gleiche Struktur, aber eine zunehmende Komplexität mit einem entsprechenden Gewinn an Rechengeschwindigkeit (wobei Simon exponentiell beschleunigt). Sie werden sie nicht intuitiv verstehen. Du musst rechnen. Ich denke, am nächsten kommen Sie durch die folgende Erklärung des deutschen Algorithmus:

f(x)f(0)=f(1)f(0)f(1)f(0)f(1)

DaftWullie
quelle
2
"Die Schwierigkeit bei der Frage ist das Wort intuitiv. Die Intuition spiegelt im Wesentlichen unser Verständnis der Welt um uns herum wider, das von der klassischen Physik beschrieben wird." Dieses Wort wird in der Mathematik häufig verwendet und bedeutet oft nicht "analog zur klassischen Physik". "" Was ich unter Intuition verstehe (und oft meine), ist ein / Verständnis / eines Mechanismus innerhalb eines Rahmens. Es ist einfach, jemandem beizubringen, Formeln einzufügen, um eine Antwort zu erhalten, aber ihn dazu zu bringen, den Rahmen und die Logik grundlegend / zu verstehen / zu verstehen, ist das, worum es in dieser Standarddefinition von Intuition geht.
Steven Sagona
1
@StevenSagona „Verständnis für einen Mechanismus innerhalb eines Frameworks“. Ja, ich stimme zu. Wenn Sie einige Mechanismen innerhalb eines Frameworks kennen, können Sie einen neuen verstehen, ohne alle Details zu lösen, da Sie über einen Kontext verfügen, der durch das vorhandene Wissen bereitgestellt wird. Und wenn Sie etwas verstehen, sollten Sie in der Lage sein, mit etwas Arbeit die mathematischen Details zu rekonstruieren. Sie können den ersten Mechanismus in einem völlig neuen Framework jedoch nicht intuitiv verstehen. Viele interessierte, aber unerfahrene Menschen versuchen dies, z. B. durch klassische Analoga, und sie scheitern, glauben aber möglicherweise, dass sie Erfolg haben.
DaftWullie
2

Es gibt ein schönes Beispiel in der Microsoft-Vorlesung . Angenommen, Sie haben eine klassische Blackbox mit 1 Eingang und 1 Ausgang. Wie viele Abfragen benötigen Sie, um festzustellen, ob die Ausgabe konstant oder variabel ist? Offensichtlich benötigen Sie 2 Abfragen; zuerst geben Sie 0 ein, zweitens geben Sie 1 ein; Wenn beide Ausgänge identisch sind, haben Sie eine konstante, ansonsten variable. Es stellt sich heraus, dass Sie nach der Konvertierung der klassischen Black Box in eine Quanten-Blackbox eine Schaltung erstellen können, die nur eine einzige Abfrage benötigt (in der Vorlesung wird erklärt, wie das geht).

kludg
quelle
3
Sonst bekannt als Deutschs Algorithmus.
DaftWullie
1
Wenn Sie mehr über das Deutsch-Jozsa-Problem erfahren möchten, empfehlen wir Ihnen einen Blick auf die Quantum Katas . Die Deutsch-Jozsa-Kata geht die Konzepte durch, die als eine Reihe von Übungen im eigenen Tempo benötigt werden, und kann eine gute Möglichkeit zum Lernen sein.
Chris Granade
Beachten Sie, dass dies nur dann zu einer Quantenbeschleunigung führt, wenn Sie eine Antwort mit Sicherheit wünschen. Wenn Sie die Antwort mit einiger Sicherheit wünschen, ist eine konstante Anzahl von Abfragen erforderlich, auch wenn die Problemgröße zunimmt (wie bei Deutsch-Jozsa)
Nippon