Apakah algoritma Shor mengakhiri pencarian algoritma anjak piutang di dunia komputasi kuantum?

Dengan kata lain, apakah penelitian anjak tetap hanya di dunia klasik atau ada penelitian menarik yang sedang berlangsung di dunia kuantum terkait dengan anjak piutang?

Secara asimtotik, algoritma Shor sangat efisien. Pada dasarnya itu hanya: superposisi, eksponensial modular (langkah paling lambat), dan transformasi fourier. Eksponensial modular adalah apa yang Anda lakukan untuk benar-benar menggunakan cryptosystem RSA. Itu berarti bagi komputer kuantum, mengenkripsi / mendekripsi RSA secara sah akan memiliki kecepatan yang sama dengan menggunakan algoritma Shor untuk memecah sistem. Jadi saya skeptis bahwa akan ada perbaikan pada ide dasar.

Yang mengatakan, setiap peningkatan penambahan bilangan bulat, perkalian bilangan bulat, atau transformasi quantum fourier akan meningkatkan algoritma Shor, dan itu semua adalah subrutin yang sangat umum yang hampir pasti akan dikerjakan orang. Pencarian singkat di Google Cendekia menunjukkan banyak penelitian untuk meningkatkan sirkuit aritmatika kuantum.

Saya pikir akan ada lebih banyak penelitian tentang trade-off klasik / kuantum dalam algoritma Shor. Artinya, jika Anda memiliki komputer kuantum kecil atau berisik, dapatkah Anda memodifikasi algoritme Shor sehingga masih berfungsi, tetapi mungkin membutuhkan lebih banyak pra dan pasca pemrosesan pada komputer klasik, atau mungkin memiliki kemungkinan keberhasilan yang lebih rendah, dll? Di area ini ada Algoritma Quantum untuk Menghitung Logaritma Diskrit Pendek dan Anjak Piutang RSA . Ada juga Saringan Nomor Kuantum, sebuah pendekatan di mana komputer kuantum "kecil" (terlalu kecil untuk menggunakan algoritma Shor secara langsung) digunakan sebagai subrutin dari saringan bidang angka klasik, sedikit meningkatkan kompleksitas waktu (meskipun saya pribadi yakin bahwa koreksi kesalahan untuk ini akan memerlukan lebih banyak qubit fisik daripada algoritma vanilla Shor).

Singkatnya, saya tidak mengharapkan adanya algoritma anjak piutang kuantum baru yang radikal dan saya pikir tidak ada orang yang mengerjakannya. Tetapi ada banyak penyesuaian menarik yang harus dilakukan agar sesuai dengan kasus penggunaan khusus.

Sebagai tambahan untuk jawaban Sam:

Tidak, sebagian karena pendekatan Shor bukan satu-satunya cara menghitung angka.

Faktorisasi juga dapat ditulis sebagai masalah optimisasi .

Ini dapat diselesaikan dengan menggunakan mesin D-Wave , tetapi juga menggunakan komputer kuantum berbasis gerbang .

Sebagai pengingat, algoritma Shor diimplementasikan dalam model gerbang perhitungan.

$(N-xy)^2$$x$$y$$N$

Runtime algoritma adiabatik adalah, seperti yang saya mengerti, terkenal berubah-ubah ditentukan, didasarkan pada sifat spektral dari masalah Hamiltonian.

Meskipun simulasi numerik kadang-kadang tampak menggembirakan, saya percaya ini masih menjadi pertanyaan terbuka apakah algoritma anjakulasi adiabatik benar-benar memberikan percepatan eksponensial atas anjak piutang klasik.

Lihat lebih detail dalam tulisan ini oleh Peng, Liao, Xu, Gan Qin, Zhou, Suter, dan Du - FIG mereka. 3 simulasi runtime menunjukkan kecocokan kuadratik; namun; Saya tidak yakin apakah ada penelitian lebih lanjut untuk membuktikan kecocokan seperti itu, atau memberikan lebih banyak bukti bahkan runtuhnya polinomial, telah terjadi.