Warum ist im Shor-Algorithmus eine Quanten-Fourier-Transformation erforderlich?

Ich studiere gerade den Shor-Algorithmus und bin verwirrt über die Komplexität. Nach dem, was ich gelesen habe, reduziert der Shor-Algorithmus das Faktorisierungsproblem auf das Ordnungsfindungsproblem oder die Periode der modularen Exponentiationssequenz eines zufälligen$x$ so dass .$1 < x < N$

Ich habe kein Problem mit der Idee des Algorithmus. Aber ich frage mich, ob Shors Algorithmus eine solche Sequenz durch wiederholtes Quadrieren erzeugt (was klassisch ein effizienter Weg ist). Nach meinem Verständnis bedeutet der Begriff "effizient", dass die Komplexität des Algorithmus zeitlich polynomisch ist.

Können wir angesichts der Tatsache, dass es eine effiziente Möglichkeit gibt, die Sequenz klassisch zu erstellen, nicht einfach eine kleine Überprüfung hinzufügen, ob wir auf gestoßen sind ? Während des Erstellungsprozesses sollte die Komplexität nicht auf Exponentialzeit erhöht werden, oder?$x^{r} = 1 \ \text{mod} N$

Warum sich überhaupt mit der Quanten-Fourier-Transformation beschäftigen? Habe ich es irgendwie falsch verstanden?

Das wesentliche Merkmal dieses Problems ist, dass sowohl der Quanten- als auch der klassische Algorithmus die effiziente klassische Funktion der Berechnung , die Frage jedoch ist, wie oft jeder die Funktion bewerten muss.$a^k\text{ mod }N$

Für den klassischen Algorithmus, den Sie vorschlagen, würden Sie und und usw. berechnen , bis Sie drücken ein sich wiederholender Wert. Sie müssen Auswertungen durchführen, und kann ziemlich groß sein. In der Tat könnte es . Es ist diese große Anzahl von Wiederholungen, die diese Idee für den klassischen Algorithmus zunichte macht.$a\text{ mod }N$$a^2\text{ mod }N$$a^3\text{ mod }N$$r$$r$$O(N)$

Im Vergleich dazu wertet der Quantenalgorithmus die Reihenfolge nur einmal aus . Sie benötigen dann die Quanten-Fourier-Transformation, um alle gleichzeitig berechneten Werte vergleichen zu können, da Sie nicht auf alle diese Werte gleichzeitig zugreifen können. Die QFT macht die ganze Magie aus.

Können wir angesichts der Tatsache, dass es eine effiziente Möglichkeit gibt, die Sequenz klassisch zu erstellen, nicht einfach eine kleine Überprüfung hinzufügen, ob wir auf $x^{r} = 1 \ \text{mod} N$ gestoßen sind ? Während des Erstellungsprozesses sollte die Komplexität nicht auf Exponentialzeit erhöht werden, oder?

Warum sich überhaupt mit der Quanten-Fourier-Transformation beschäftigen? Habe ich es irgendwie falsch verstanden?

$x = 2^r_{1} \ \text{mod} N$

Die klassische diskrete Fourier-Transformation weist eine exponentielle Komplexität auf - die Quantenversion dieser Fourier-Transformation weist jedoch eine polynomielle Komplexität auf. Wir müssen uns also mit der Quanten-Fourier-Transformation beschäftigen.