Kecepatan Algoritma Shor

Saya seorang sarjana ilmu komputer yang masih muda, dan saya diminta untuk menulis makalah yang melibatkan faktorisasi bilangan bulat. Akibatnya, saya harus melihat algoritma Shor pada komputer kuantum.

Untuk algoritma lain, saya dapat menemukan persamaan khusus untuk menghitung jumlah instruksi algoritma untuk ukuran input yang diberikan (dari mana saya dapat menghitung waktu yang diperlukan untuk menghitung pada mesin dengan kecepatan yang diberikan). Namun, untuk algoritma Shor, yang paling saya dapat menemukan adalah kompleksitas: O( (log N)^3 ).

Apakah ada beberapa cara saya dapat menemukan kecepatan / kompleksitas aktual dari Notasi Big-O? Jika tidak, adakah seseorang yang bisa memberi tahu saya apa yang saya inginkan, atau bagaimana cara menemukannya?

Perkiraan terbaik yang saya tahu dapat ditemukan di jaringan Efisien untuk anjak kuantum , oleh David Beckman, Amalavoyal N. Chari, Srikrishna Devabhaktuni, dan John Preskill, yang memberikan$72 (\log N)^3$.

Karena itu, perbandingan langsung jumlah langkah pada komputer kuantum versus jumlah langkah pada komputer klasik bermasalah karena berbagai alasan. Pertama, seperti jawaban DW katakan, jumlah langkah tergantung pada arsitektur yang tepat dari komputer kuantum, yang kita tidak akan memiliki sampai satu dibangun. Kedua, waktu yang diperlukan untuk satu langkah pada komputer kuantum cenderung sedikit lebih lambat daripada satu langkah pada komputer klasik. ¹ Sekali lagi, kita tidak akan tahu seberapa lambat sampai komputer kuantum ada.

¹ Jika lebih cepat, Anda bisa menggunakan arsitektur yang sama untuk membangun komputer klasik yang setidaknya akan secepat, dan mungkin lebih cepat karena untuk komputer klasik, Anda tidak perlu khawatir tentang mempertahankan koherensi kuantum.

Apa yang Anda minta tidak ada, untuk alasan yang baik.

Saat ini tidak ada komputer yang ada yang dapat menjalankan algoritma Shor. Untuk menjalankan algoritma Shor, Anda memerlukan komputer kuantum, yang belum ada. Oleh karena itu, Anda tidak boleh mengharapkan perkiraan kecepatan atau waktu berjalan yang tepat, karena itu akan tergantung pada detail komputer tempat algoritme dijalankan - dan kami tidak dapat mengetahui detail tersebut hingga kami berhasil membuatnya. .