Shors Algorithmus: Was tun, nachdem das QFT-Ergebnis zweimal gelesen wurde?
Ich fragte, wie man den Zeitraum identifiziert, in dem ein Fourier-Transformationsdiagramm betrachtet wird . Die Antwort scheint darin zu bestehen, die Fourier-Transformation mehrmals auszuführen und mehrere Werte zu erhalten, die den im Diagramm beschriebenen hohen Wahrscheinlichkeiten zugeordnet sind. Angenommen, ich lese immer noch dasselbe Bild und habe es zweimal gelesen und die Werte | 5> und | 11> erhalten. Dies sind die höchsten Spitzen (nach der ersten höchsten in | 0>). Wie würde ich die Periode 12 von 5 und 11 herausfinden? Können Sie ein Beispiel für die Berechnung zeigen?
Eine versuchte Lösung . Wenn wir Peter Shors Artikel (auf Seite 320) lesen, finden wir, dass seins$q$ ist $q=64$hier in unserem Beispiel. Shor sagt, wir können einen Bruchteil erhalten$d/r$ in niedrigsten Begriffen (wo $r = 12$ hier) durch Rundung $c/q$ auf den nächsten Bruch mit einem Nenner kleiner als $n=35$Hier. Unser möglich$c$ hier ist $5$ und $11$.
Lass es uns versuchen. Nach der QFT haben wir$c = 5$ und wir haben $q = 64$. Also bekommen wir$5/64 = 0.078125$ und wir wollen das auf den nächsten Bruch mit einem Nenner kleiner als runden $35$. Zum$5/64$Ich finde die fortgesetzte Fraktion $[0,12,1,4]$. (Ich habe das überprüft$5/64 = 1/(12 + 1/(1 + 1/4))$, also das ist richtig.) Aus dieser fortgesetzten Fraktion (in Listenform) erhalte ich nun die folgende Folge von Fraktionen: $1/4, 5/4, 64/5, 5/64$. (Ich bin nicht sicher, was ich tue.) Vielleicht$5$ist Pech? Aber nein, ich versuche das Gleiche mit$11$ wird auch produzieren $11/64$. Obwohl ich weiß, wie man den fortgesetzten Bruchalgorithmus berechnet, weiß ich nicht, was ich damit machen soll. Ich muss mir Hardy und Wright ansehen, Kapitel X.
Antworten
Dies ist der fortgesetzte Bruchteil des Algorithmus, Schritt 5 auf Wikipedia. Was Sie gemessen haben, ist$y$ so dass $\frac{yr}{Q}\approx c$, wo $c$ ist eine unbekannte ganze Zahl, $r$ ist die versteckte Periode (in diesem Fall 12) und $Q=64$ist die Größe der QFT. Dies bedeutet, dass$\frac{y}{Q}\approx \frac{c}{r}$. Zum$y=5$, wir haben $\frac{5}{64}\approx \frac{1}{12}$, und für $y=11$, wir haben $\frac{11}{64}\approx \frac{2}{12}$. Das ist also die Beziehung zwischen den gemessenen Werten und der Periode.
Wie finden wir den Zeitraum tatsächlich aus diesen Werten (da wir es nicht wissen? $c$ oder $r$)? Mit fortgesetzten Brüchen. Ein fortgesetzter Bruch für eine Zahl$x$ wird rekursiv definiert mit $a_0=x$, dann mit $b_n=\lfloor a_n\rfloor$, und $a_n=\frac{1}{a_{n-1}-b_{n-1}}$. Auf dieses Problem angewendet mit$x=\frac{5}{64}$, wir haben
$$ a = (\frac{5}{64},\frac{64}{5},\frac{5}{4},4,0,\dots)$$ $$ b = (0,12,1,4,0,\dots)$$
Daraus können wir Näherungen rekonstruieren, und der Nenner dieser Näherungen wird wahrscheinlich die Periode sein. Die Wikipedia-Seite zu fortgesetzten Brüchen erklärt, dass wir eine Reihe von ungefähren Brüchen erhalten$\frac{h_n}{k_n}$, wo wir einen Zähler setzen $h_n=b_nh_{n-1}+h_{n-2}$ und Nenner $k_n=b_nk_{n-1}+k_{n-2}$mit Anfangswerten $h_{-1}=1$, $h_{-2}=0$, $k_{-1}=0$, und $k_{-2}=1$. Dies ergibt zwei Sequenzen:
$$h = (0, 1, 0, 1, 1, 5)$$ $$ k = (1,0, 1, 12, 13, 64)$$
was drei ungefähre Brüche ergibt: $\frac{1}{12}$, $\frac{1}{13}$, und $\frac{5}{64}$. Der letzte ist der, mit dem wir begonnen haben und der nutzlos ist, weil 64 zu groß ist (der Zeitraum muss schließlich weniger als 35 betragen). Der erste ist der tatsächliche Zeitraum.
Ich weiß nicht viel über fortgesetzte Brüche, aber ich denke, diese Annäherungen konvergieren sehr schnell zum ursprünglichen Bruch. In der Praxis würden Sie also jeden Nenner in der Reihenfolge der ungefähren Brüche (in diesem Fall sowohl 12 als auch 13) überprüfen, da (a) es nicht so viele ungefähre Brüche geben sollte und (b) die letzten Schritte von Shor Algorithmen sind so günstig.