Apakah ada algoritma NC kuantum untuk menghitung GCD?

14

Dari komentar di salah satu pertanyaan saya di MathOverflow saya mendapatkan perasaan bahwa pertanyaan mengenai GCD berada di vs P ini mirip dengan pertanyaan mengenai Integer faktorisasi berada di P vs N P .NCPPNP

Apakah ada sesuatu seperti "kuantum " algoritma untuk GCD karena ada kuantum polinomial waktu ( B Q P ) algoritma untuk Integer faktorisasi?NCBQP

Pertanyaan terkait: kompleksitas pembagi umum terbesar (gcd)

cc.complexity-theory quantum-computing dc.parallel-comp nt.number-theory comp-number-theory T ....
sumber
5
ketika Anda melakukan posting silang lebih baik untuk menulis pertanyaan lagi.
Alessandro Cosentino

Jawaban:

14

Pertama-tama, ada definisi formal "kuantum-NC", lihat QNC di kebun binatang.

GCD memang merupakan kandidat yang baik untuk masalah yang dapat ditunjukkan berada di QNC, tetapi tidak diketahui berada di NC. Namun, menemukan algoritma QNC untuk GCD masih merupakan masalah terbuka.

Perasaan yang diyakini benar ini berasal dari fakta bahwa Quantum Fourier Transform dapat dilakukan di QNC.

Referensi: Bagian kesimpulan "R. Cleve dan J. Watrous, Sirkuit paralel cepat untuk transformasi Fourier kuantum", arXiv: quant-ph / 0006004

Alessandro Cosentino
sumber
6
Alangkah baiknya jika Anda bisa menjelaskan hubungan antara transformasi quantum Fourier dan GCD.
Kaveh
Saya setuju dengan Kaveh. Akan menyenangkan untuk menyediakan relasi.
T ....
2
Saya tidak berpikir ada hubungan langsung. Yang ingin saya katakan adalah bahwa kami menduga QNC lebih kuat daripada NC, karena kami dapat melakukan QFT di QNC. Jadi kami bertanya apakah ada beberapa masalah alami yang ada di QNC juga, dan salah satu masalah alami paling sederhana yang kami tidak tahu bagaimana melakukannya di NC adalah GCD. Pada beberapa titik saya menduga bahwa ada hubungan antara dua masalah yang datang dari fakta bahwa QFT dan GCD keduanya digunakan sebagai sub-rutin dalam algoritma pencarian-periode, tetapi saya tidak dapat membuat ini formal. Mungkin pengguna lain dapat mencerahkan kami lebih banyak.
Alessandro Cosentino
Hai Alessandro: Apakah Anda tahu jika Polynomial GCD ada di NC?
T ....
1
@ Arul: ya, benar. Lihat von zur Gathen, Algoritma paralel untuk masalah aljabar. dx.doi.org/10.1145/800061.808728
Alessandro Cosentino