Apa lonjakan menarik dalam grafik setelah QFT ini (halaman 241) dari Pemrograman Komputer Kuantum?

Question

Saya membaca Programming Quantum Computers mencoba memahami algoritma Shor. Saya belajar di sana bahwa kami mempersiapkan negara$|x^i \bmod N\rangle$, lalu terapkan QFT ke status ini. QFT mengubah amplitudo dari superposisi seragam menjadi amplitudo besar yang diberi jarak secara merata pada periode$x^i \bmod N$. Misalnya, berikut adalah grafik amplitudo setelah menerapkan QFT dengan$N = 35$. Itu ada di halaman 241.

Buku itu mengatakan ada 12 paku yang berjarak sama. Saya melihat lebih dari 12 paku dengan jarak yang sama. Haruskah saya hanya menghitung yang tertinggi dan berhenti ketika saya telah menghitung 12? Tapi bukankah itu subjektif? Bagaimana saya mengetahui bahwa bilangan tersebut benar-benar 12 hanya dengan melihat grafik ini tanpa mengetahui jawaban yang benar? (Dengan kata lain, bagaimana cara mendapatkan 12 dari ini?)

Answer 1

Melihat grafik yang Anda buat ulang, grafik kiri menunjukkan evaluasi $2^x\bmod 35$ untuk $x\in\{0,\dots 63\}$ sedangkan grafik kanan menggambarkan amplitudo dari transformasi Fourier diskrit untuk $\hat{x}\in\{0,\dots 63\}$. Komentar bahwa ada "12 paku yang berjarak sama" menunjukkan bahwa maksima lokal dari grafik kanan berulang setiap$64/12=5.33$ nilai-nilai.

Anda benar, Anda tidak memiliki akses ke $\hat{x}$ dengan cara yang memungkinkan Anda mengamati periodisitas ini dalam $\hat{x}$segera; Namun, apa yang Anda lakukan memiliki akses ke adalah cara untuk sampel$\hat{x}_i$ untuk beberapa $i$ dengan cara yang kembali $\hat{x}_i$ dengan probabilitas yang diberikan oleh (kuadrat) tinggi masing-masing $\hat{x}_i$.

Misalnya, jika Anda menjalankan eksponensial modular (grafik kiri) diikuti oleh QFT (grafik kanan), dan mencicipi register pertama, Anda kemungkinan besar akan mendapatkan nilai seperti $0$ dengan probabilitas lebih tinggi dari $5$, dengan probabilitas lebih tinggi dari $32$, dengan probabilitas lebih tinggi dari $11$, dengan probabilitas lebih tinggi dari $6$, dll.

Dari masing-masing sampel $\hat{x}_i$, Anda dapat menjalankan bagian klasik (bagian pecahan lanjutan) dari algoritme Shor untuk menyimpulkan bahwa, memang, ada 12 paku yang berjarak sama di $\hat{x}$, memberi Anda periode $12$ di $2^x\bmod 35$. Ada banyak detail yang saya lupa tetapi intinya adalah Anda menggunakan sampel dari QFT Anda sebagai input untuk bagian klasik ini.