Einfachster Algorithmus zur intuitiven Demonstration der Quantenbeschleunigung?

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 .

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 $\Delta 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 $\Delta p$ , die richtige Antwort$\sqrt{\Delta p}$ oder ein Polynom davon und nicht so etwas wie die Anzahl der Ziffern von$p$,$O(\log p)$.

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(\log p)$ gesteuerte Rotationen (eine pro jedes Eingangsbit) implementiert werden .

$O(\log p)$$O(\sqrt{\Delta p})$$p$$O(\sqrt{p})$

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)\oplus f(1)$

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).