Was sind die interessanten Spitzen in diesem After-QFT-Diagramm (Seite 241) zum Programmieren von Quantencomputern?

Question

Ich lese Programmieren von Quantencomputern und versuche, Shors Algorithmus zu verstehen. Ich habe dort gelernt, dass wir einen Staat vorbereiten$|x^i \bmod N\rangle$Wenden Sie dann die QFT auf diesen Status an. Die QFT ändert die Amplituden von einer gleichmäßigen Überlagerung zu großen Amplituden, die durch die Periode von gleichmäßig verteilt sind$x^i \bmod N$. Hier ist zum Beispiel ein Diagramm der Amplituden nach dem Anwenden der QFT mit$N = 35$. Das ist auf Seite 241.

Das Buch sagt, dass es 12 Spikes gibt, die gleichmäßig verteilt sind. Ich sehe viel mehr als 12 gleichmäßig verteilte Spitzen. Soll ich nur die höchsten zählen und aufhören, wenn ich 12 gezählt habe? Aber ist das nicht subjektiv? Wie würde ich herausfinden, dass die Zahl wirklich 12 ist, wenn ich nur diese Grafik betrachte, ohne die richtige Antwort zu kennen? (Mit anderen Worten, wie bekomme ich 12 davon?)

Answer 1

Wenn Sie sich die Grafiken ansehen, die Sie reproduziert haben, zeigt die linke Grafik die Auswertung von $2^x\bmod 35$ zum $x\in\{0,\dots 63\}$ während der rechte Graph die Amplitude der diskreten Fourier-Transformation für darstellt $\hat{x}\in\{0,\dots 63\}$. Der Kommentar, dass es "12 gleichmäßig verteilte Spitzen" gibt, zeigt an, dass sich die lokalen Maxima des rechten Graphen alle wiederholen$64/12=5.33$ Werte.

Sie haben Recht, Sie haben keinen Zugriff auf $\hat{x}$ auf eine Weise, mit der Sie diese Periodizität in beobachten können $\hat{x}$sofort; Sie haben jedoch Zugriff auf eine Möglichkeit zum Probieren$\hat{x}_i$ für mehrere $i$ auf eine Weise, die zurückkehrt $\hat{x}_i$ mit der Wahrscheinlichkeit, die durch das (Quadrat der) Höhe des jeweiligen gegeben ist $\hat{x}_i$.

Wenn Sie beispielsweise die modulare Exponentiation (linkes Diagramm) gefolgt von der QFT (rechtes Diagramm) ausführen und das erste Register abtasten, erhalten Sie wahrscheinlich einen Wert wie z $0$ mit höherer Wahrscheinlichkeit als $5$mit höherer Wahrscheinlichkeit als $32$mit höherer Wahrscheinlichkeit als $11$mit höherer Wahrscheinlichkeit als $6$, usw.

Aus diesen jeweiligen Probenahmen von $\hat{x}_i$Sie können die klassischen Teile (den fortgesetzten Bruchteil) von Shors Algorithmus ausführen, um daraus zu schließen, dass tatsächlich 12 gleichmäßig verteilte Spitzen vorhanden waren $\hat{x}$und geben Ihnen die Periode von $12$ im $2^x\bmod 35$. Es gibt viele Details, die ich vergesse, aber der Punkt ist, dass Sie die Samples aus Ihrer QFT als Eingaben für diesen klassischen Teil verwenden.