Mengapa transformasi kuantum Fourier diperlukan dalam algoritma Shor?

8

Saat ini saya sedang mempelajari algoritma Shor dan saya bingung tentang masalah kompleksitasnya. Dari apa yang telah saya baca, algoritma Shor mengurangi masalah faktorisasi menjadi masalah pencarian-urutan atau periode urutan eksponensial modular dari beberapa $x$ acak sehingga $1 < x < N$ .

Saya tidak punya masalah tentang gagasan algoritma. Tapi saya bertanya-tanya apakah algoritma Shor menciptakan urutan seperti itu dengan kuadrat berulang (yang merupakan cara yang efisien secara klasik). Dalam pemahaman saya, istilah "efisien" berarti kompleksitas algoritme itu polinomial dalam waktu.

Mengingat bahwa ada cara efisien untuk membuat urutan secara klasik, tidak bisakah kita menambahkan sedikit centang untuk mengetahui apakah kita telah menemukan $x^{r} = 1 \ \text{mod} N$ ? Selama proses pembuatan, seharusnya tidak meningkatkan kompleksitas ke waktu eksponensial, bukan?

Mengapa repot-repot dengan transformasi kuantum Fourier sama sekali? Apakah saya salah paham dalam beberapa hal?

algorithm complexity-theory shors-algorithm quantum-fourier-transform Poramet Pathumsoot
sumber

1

Hai, Poramet. Selamat Datang di Quantum Computing SE! Tolong hanya tanyakan satu pertanyaan per posting - hanya tanyakan beberapa jika mereka terkait sangat erat sehingga tidak masuk akal untuk memisahkan mereka karena mereka tidak dapat dijawab secara terpisah. Dengan begitu, penjawab yang mungkin bisa menjawab satu pertanyaan tetapi tidak yang lain masih bisa memberikan jawaban yang bermanfaat dan lengkap untuk suatu pertanyaan. Tinjau Bagaimana menulis pertanyaan yang bagus? .

Sanchayan Dutta

1

Saya telah mengedit posting Anda untuk menghapus pertanyaan kedua (v5 masih terlihat di sini ). Silakan tanyakan itu sebagai pertanyaan terpisah jika perlu.

Sanchayan Dutta

7

Fitur penting dari masalah ini adalah bahwa sementara kedua kuantum dan algoritma klasik dapat menggunakan fungsi klasik efisien menghitung $a^k\text{ mod }N$ , masalahnya adalah berapa kali masing-masing harus mengevaluasi fungsi.

Untuk algoritma klasik Anda menyarankan, Anda akan menghitung $a\text{ mod }N$ , dan $a^2\text{ mod }N$ , dan $a^3\text{ mod }N$ , dan seterusnya, sampai Anda menekan nilai mengulangi. Anda harus melakukan evaluasi $r$ , dan $r$ bisa cukup besar. Memang, itu bisa menjadi $O(N)$ . Ini sejumlah besar pengulangan yang membunuh ide ini untuk algoritma klasik.

Sebagai perbandingan, algoritma kuantum hanya mengevaluasi pesanan satu kali . Anda kemudian memerlukan Transformasi Quantum Fourier agar dapat membandingkan semua nilai yang dihitung secara bersamaan karena Anda tidak dapat mengakses semua nilai ini sekaligus. QFT adalah apa yang melakukan semua keajaiban.

DaftWullie
sumber

O (N)

$O(N)$

N

$N$

x^{a} mod N

$x^{a} \text{mod} N$

a

$a$

O (N)

$O(N)$

1

n = \log_{2} (N)

$n=\log_2(N)$

N

$N$

n

$n$

3

$x^{r} = 1 \ \text{mod} N$

Mengapa repot-repot dengan transformasi kuantum Fourier sama sekali? Apakah saya salah paham dalam beberapa hal?

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

Transformasi Fourier diskrit klasik memiliki kompleksitas eksponensial - namun, versi kuantum dari transformasi Fourier tersebut memiliki kompleksitas polinomial. Jadi kita perlu repot dengan transformasi quantum Fourier.

Pelajar
sumber

x^{r} = 1 m o d N

$x^r = 1 mod N$

Hai, Pelajar. Selamat datang di Quantum Computing ! Saya telah mengedit ed jawaban Anda sedikit agar sesuai dengan versi saat ini (v8) dari pertanyaan.

Sanchayan Dutta

Mengapa transformasi kuantum Fourier diperlukan dalam algoritma Shor?

Jawaban: