Saya telah melihat lebih banyak hype tentang komputer kuantum di X baru-baru ini, jadi saya pikir saya akan membuat posting panjang tentang mereka. Ringkasan eksekutif: Saya tidak percaya komputasi kuantum akan datang dalam waktu dekat. Saya pikir ini karena tidak ada kemajuan yang dibuat selama bertahun-tahun pada masalah paling mudah yang dapat digunakan komputer kuantum, yaitu anjak piutang. Catatan anjak piutang kuantum telah berada di sekitar angka 15 (ya, 15, 3 x 5!) selama satu dekade sekarang, dan tidak ada kemajuan yang jelas yang terjadi akhir-akhir ini. Alasan saya ada di bawah ini. Saya akan menguraikan hal-hal untuk orang-orang yang tidak tahu banyak matematika atau ilmu komputer, tetapi ini mungkin masih menakut-nakuti orang-orang dengan fobia matematika. Memfaktorkan angka besar menarik karena beberapa algoritma kriptografi penting bergantung pada fakta bahwa dibutuhkan waktu yang sangat lama untuk memfaktorkan angka yang cukup besar ke dalam faktor primanya menggunakan komputer konvensional. Anda dapat memfaktorkan angka kecil (katakanlah 21) dengan tangan dengan sangat cepat, coba saja membaginya dengan angka yang dimulai dengan 2 lalu 3 dan seterusnya, dan Anda akan segera menemukan bahwa 21 adalah 3 x 7. Namun, ini tidak berhasil untuk angka yang sangat besar karena ruang semua angka yang perlu Anda coba menjadi terlalu besar. Jika Anda dapat memfaktorkan angka dengan panjang sekitar 1200 digit desimal (bukan angka 1200, yang memiliki empat digit, angka dengan 1200 digit!) Anda dapat merusak banyak sistem kriptografi yang dipedulikan orang, tetapi tidak ada yang tahu bagaimana melakukannya dengan cukup cepat di komputer biasa. (Cukup cepat berarti "sebelum semua bintang di langit terbakar.") Beberapa tahun yang lalu, Peter Shor menunjukkan bahwa Anda dapat (setidaknya secara teori) memfaktorkan angka dengan sangat cepat menggunakan komputer kuantum. Pemfaktoran menggunakan Algoritma Shor adalah, menurut saya, tolok ukur yang paling jelas untuk komputasi kuantum. Pada tahun 2016, angka 15 (bukan angka 15 digit, angka 15!) untuk pertama kalinya diperhitungkan (jelas menjadi 3 x 5) dalam demonstrasi Algoritma Shor yang bersih dan tidak dicurangi. Ini adalah angka yang kecil, tetapi itu adalah permulaan. (Ada beberapa argumen tentang apakah angka 21 juga telah diperhitungkan dalam demonstrasi algoritma Shor yang tidak dicurangi atau tidak.) Tapi sekali lagi, 15 adalah angka dua digit. Kami ingin memfaktorkan angka dalam ribuan digit untuk dapat mematahkan sistem kriptografi. Namun, sejak 2016, tidak ada angka yang lebih besar yang diperhitungkan dalam demonstrasi bersih algoritma Shor. (Beberapa orang mengklaim bahwa mereka telah memfaktorkan angka yang lebih besar menggunakan Algoritma Shor, tetapi mereka selalu menggunakan trik yang mengharuskan mereka sudah mengetahui faktor-faktor untuk melakukannya dan menyiapkan komputer kuantum dengan apa yang berarti pra-pengetahuan tentang jawabannya, yang sebenarnya bukan intinya. Saya mencari demonstrasi *tidak dicurangi*.) Kami telah menunggu lama bagi seseorang untuk mendemonstrasikan pemfaktoran bahkan angka yang sedikit lebih besar dari 15. Anda akan berharap mungkin ada kemajuan yang stabil dalam hal ini, dengan seseorang memfaktorkan (katakanlah) angka seperti 77 (7 x 11), dan kemudian satu seperti 323 (17 x 19), lalu sesuatu yang ribuan, dan seterusnya. Namun, tidak ada yang menunjukkan mesin yang dapat melakukan sesuatu yang lebih baik daripada angka 15 (yang dapat diperhitungkan oleh seorang anak di kepala mereka menjadi 3 dan 5 dalam beberapa saat) dan rekor itu telah bertahan untuk waktu yang sangat lama. Jadi, setidaknya pada masalah ini, yang sangat mendasar yang mudah dijelaskan, belum ada kemajuan yang stabil dalam komputasi kuantum. Kami memiliki banyak hype, banyak orang memamerkan komputer kuantum yang seharusnya menjalankan algoritme yang tidak cukup jelas demonstrasi bersih, tetapi kami tidak melihat apa-apa dalam waktu yang lama tentang pemfaktoran. Saya akan percaya ada kemajuan nyata dalam komputasi kuantum ketika kita mulai melihat angka yang lebih besar diperhitungkan dalam demonstrasi Algoritma Shor yang bersih dan tidak dicurangi. Saya akan percaya bahwa kita telah membuat kemajuan nyata ketika kita dapat melakukan empat angka digit desimal, yaitu, angka dalam ribuan. Bahkan demonstrasi sesuatu yang dapat melakukan angka dua digit yang jauh lebih besar dari 15 akan disambut baik. Namun, tidak ada mesin yang dapat melakukan itu benar-benar berada di cakrawala jangka pendek. Sekarang, mampu memecahkan kode membutuhkan mesin yang dapat menangani angka dengan *ribuan* digit, tetapi kita bahkan belum memiliki tiga digit angka yang terlihat (atau bahkan sebagian besar angka dua digit). Jadi, tolok ukur pribadi saya adalah melihat sedikit kemajuan dalam hal ini. Hubungi saya kembali ketika kita memiliki komputer kuantum yang dapat memfaktorkan (katakanlah) 323 dengan sukses, dalam demo Algoritma Shor yang bersih dan tidak dipasang yang akan menangani angka komposit dengan ukuran yang sama. Sampai saat itu, saya pikir tidak ada banyak minat yang terjadi, setidaknya tidak bagi saya.

(BTW, saya tidak ingin memberi kesan bahwa saya pikir komputasi kuantum tidak mungkin atau apa pun. Saya hanya mengatakan bahwa dari posisi saya, kemajuan baru-baru ini belum jelas dan kita masih jauh dari memecahkan masalah langsung seperti memfaktorkan angka dengannya.)

Omong-omong, ini juga tidak berarti bahwa perusahaan seperti Google bodoh karena mengejar penelitian murni tentang komputasi kuantum. Saya pikir itu layak untuk dikerjakan. Ini hanya bukan aplikasi praktis yang akan segera terjadi. Mungkin juga bahwa NSA atau organisasi semacam itu telah membuat kemajuan yang lebih signifikan dalam masalah ini daripada yang dimiliki dunia penelitian terbuka, tetapi jelas, itu bukan informasi yang akan saya ketahui. Terakhir, ini tidak berarti bahwa penelitian tentang algoritme kriptografi postquantum adalah ide yang buruk.

Dalam posting asli saya di atas, saya menghindari menyebutkan betapa sulitnya masalah penskalaan. Sebagian besar saya hanya berkonsentrasi pada fakta bahwa tidak ada penskalaan yang benar-benar terjadi. Dan yang pasti, pada titik tertentu, sangat mungkin bahwa hal-hal koreksi kesalahan akan mulai muncul. Tapi, penskalaan untuk memfaktorkan angka yang serius tidak akan terjadi sehari setelah itu.

@defendtheworld Jadi bagaimanapun, sekali lagi: Saya akan mulai percaya ketika saya melihat teknologi bergerak dari faktor 15. Dan ya, itu berarti bahwa sejumlah besar pekerjaan telah dilakukan, tetapi juga akan menyisakan banyak pekerjaan yang masih harus dilakukan.