Algoritma Shor: apa yang harus dilakukan setelah membaca hasil QFT dua kali?
Saya bertanya tentang bagaimana mengidentifikasi periode dengan melihat plot transformasi Fourier . Jawabannya adalah menjalankan transformasi fourier beberapa kali mendapatkan beberapa nilai yang terkait dengan probabilitas tinggi yang dijelaskan oleh grafik. Jadi masih menggunakan gambar yang sama, misalkan saya membacanya dua kali dan saya mendapatkan nilai | 5> dan | 11>. Ini adalah lonjakan tertinggi (setelah tertinggi pertama di | 0>.) Bagaimana saya mengetahui periode 12 dari 5 dan 11? Bisakah Anda menunjukkan contoh penghitungan?
Solusi yang dicoba . Membaca makalah Peter Shor (di halaman 320), kami menemukan bahwa makalahnya$q$ aku s $q=64$di sini, di contoh kami. Shor mengatakan kita bisa mendapatkan pecahan$d/r$ dalam istilah terendah (di mana $r = 12$ di sini) dengan pembulatan $c/q$ ke pecahan terdekat yang memiliki penyebut lebih kecil dari $n=35$sini. Kemungkinan kami$c$ disini adalah $5$ dan $11$.
Mari kita coba. Setelah QFT, kami mendapat$c = 5$ dan kita mempunyai $q = 64$. Jadi kami mendapatkan$5/64 = 0.078125$ dan kami ingin membulatkannya ke pecahan terdekat yang memiliki penyebut lebih kecil dari $35$. Untuk$5/64$, Saya menemukan pecahan lanjutan $[0,12,1,4]$. (Aku sudah memeriksanya$5/64 = 1/(12 + 1/(1 + 1/4))$, jadi itu benar.) Sekarang, dari pecahan lanjutan ini (dalam bentuk daftar) saya mendapatkan urutan pecahan berikut: $1/4, 5/4, 64/5, 5/64$. (Saya tidak yakin apa yang saya lakukan.) Mungkin$5$apakah nasib buruk? Tapi, tidak, mencoba hal yang sama dengan$11$ juga akan menghasilkan $11/64$. Jadi meskipun saya tahu cara menghitung algoritma pecahan lanjutan, saya tidak tahu apa yang harus saya lakukan dengannya. Aku harus melihat Hardy dan Wright, Bab X.
Jawaban
Ini adalah bagian pecahan lanjutan dari algoritme, langkah 5 di Wikipedia. Apa yang telah Anda ukur adalah$y$ seperti yang $\frac{yr}{Q}\approx c$, dimana $c$ adalah beberapa bilangan bulat yang tidak diketahui, $r$ is the hidden period (in this case 12), and $Q=64$ is the size of the QFT. This means that $\frac{y}{Q}\approx \frac{c}{r}$. For $y=5$, we have $\frac{5}{64}\approx \frac{1}{12}$, and for $y=11$, we have $\frac{11}{64}\approx \frac{2}{12}$. So that's the relation between the measured values and the period.
How do we actually find the period from those values, though (since we don't know $c$ or $r$)? With continued fractions. A continued fraction for a number $x$ is defined recursively, with $a_0=x$, then with $b_n=\lfloor a_n\rfloor$, and $a_n=\frac{1}{a_{n-1}-b_{n-1}}$. Applied to this problem with $x=\frac{5}{64}$, we have
$$ a = (\frac{5}{64},\frac{64}{5},\frac{5}{4},4,0,\dots)$$ $$ b = (0,12,1,4,0,\dots)$$
From this, we can reconstruct approximations, and the denominator of these approximations will likely be the period. The wikipedia page on continued fractions explains that we get a series of approximate fractions $\frac{h_n}{k_n}$, where we set a numerator $h_n=b_nh_{n-1}+h_{n-2}$ and denominator $k_n=b_nk_{n-1}+k_{n-2}$, with initial values $h_{-1}=1$, $h_{-2}=0$, $k_{-1}=0$, and $k_{-2}=1$. This gives two sequences:
$$h = (0, 1, 0, 1, 1, 5)$$ $$ k = (1,0, 1, 12, 13, 64)$$
which gives three approximate fractions: $\frac{1}{12}$, $\frac{1}{13}$, and $\frac{5}{64}$. The last one is what we started with and is useless because 64 is too big (the period must be less than 35, after all). The first one is the actual period.
I don't know much about continued fractions but I think these approximations converge very quickly to the original fraction. So in practice, I think you would just check each denominator in the sequence of approximate fractions (in this case, both 12 and 13) since (a) there should not be that many approximate fractions, and (b) the final steps of Shor's algorithm are so inexpensive.