Versi aslinya dari cerita ini muncul di majalah Quanta.
Bagi para ilmuwan komputer, memecahkan masalah sedikit seperti mendaki gunung. Pertama -tama mereka harus memilih masalah untuk dipecahkan – mencari untuk mengidentifikasi puncak untuk memanjat – dan kemudian mereka harus mengembangkan strategi untuk menyelesaikannya. Peneliti klasik dan kuantum bersaing menggunakan strategi yang berbeda, dengan persaingan yang sehat di antara keduanya. Peneliti Quantum melaporkan cara cepat untuk memecahkan masalah – sering dengan menskalakan puncak yang tidak ada yang layak dipanjat – kemudian tim klasik berlomba untuk melihat apakah mereka dapat menemukan cara yang lebih baik.
Kontes ini hampir selalu berakhir sebagai dasi virtual: Ketika para peneliti berpikir mereka telah menyusun algoritma kuantum yang bekerja lebih cepat atau lebih baik dari apa pun, para peneliti klasik biasanya datang dengan yang sama dengan itu. Baru minggu lalu, speedup kuantum yang diakui, yang diterbitkan dalam jurnal Science, disambut dengan skeptisisme langsung dari dua kelompok terpisah yang menunjukkan bagaimana melakukan perhitungan serupa pada mesin klasik.
Tetapi dalam sebuah makalah yang diposting di situs preprint ilmiah Arxiv.org tahun lalu, para peneliti menggambarkan apa yang tampak seperti percepatan kuantum yang meyakinkan dan bermanfaat. Para peneliti menggambarkan algoritma kuantum baru yang bekerja lebih cepat daripada semua yang diketahui klasik dalam menemukan solusi yang baik untuk kelas masalah optimisasi yang luas (yang mencari solusi terbaik di antara sejumlah besar pilihan).
Sejauh ini, tidak ada algoritma klasik yang mencopot algoritma baru, yang dikenal sebagai interferometri kuantum yang didekodekan (DQI). Ini adalah “terobosan dalam algoritma kuantum,” kata Gil Kalai, seorang matematikawan di Universitas Reichman dan skeptis terkemuka komputasi kuantum. Laporan algoritma kuantum membuat para peneliti bersemangat, sebagian karena mereka dapat menerangi ide -ide baru tentang masalah yang sulit, dan sebagian karena, untuk semua buzz di sekitar mesin kuantum, tidak jelas masalah mana yang benar -benar akan mendapat manfaat darinya. Algoritma kuantum yang mengungguli semua yang diketahui klasik pada tugas optimasi akan mewakili langkah besar ke depan dalam memanfaatkan potensi komputer kuantum.
“Saya antusias tentang hal itu,” kata Ronald de Wolf, seorang ilmuwan komputer teoretis di CWI, Institut Penelitian Nasional untuk Matematika dan Ilmu Komputer di Belanda, yang tidak terlibat dengan algoritma baru. Tetapi pada saat yang sama, ia mengingatkan bahwa masih sangat mungkin para peneliti pada akhirnya akan menemukan algoritma klasik yang juga berhasil. Dan karena kurangnya perangkat keras kuantum, masih akan lama sebelum mereka dapat menguji algoritma baru secara empiris.
Algoritma ini mungkin menginspirasi karya baru di sisi klasik, menurut Ewin Tang, seorang ilmuwan komputer di University of California, Berkeley, yang menjadi terkenal sebagai seorang remaja dengan menciptakan algoritma klasik yang cocok dengan yang kuantum. Klaim baru “cukup menarik sehingga saya akan memberi tahu orang-orang algoritma klasik, 'Hei, Anda harus melihat makalah ini dan mengerjakan masalah ini,'” katanya.
Cara terbaik ke depan?
Ketika algoritma klasik dan kuantum bersaing, mereka sering melakukannya di medan perang optimasi, sebuah bidang yang berfokus pada menemukan opsi terbaik untuk memecahkan masalah yang sulit. Para peneliti biasanya fokus pada masalah di mana jumlah solusi yang mungkin meledak saat masalah menjadi lebih besar. Apa cara terbaik bagi truk pengiriman untuk mengunjungi 10 kota dalam tiga hari? Bagaimana Anda harus mengemas parsel di belakang? Metode klasik untuk memecahkan masalah ini, yang sering melibatkan pengadukan melalui kemungkinan solusi dengan cara yang cerdas, dengan cepat menjadi tidak dapat dipertahankan.
Masalah optimasi spesifik yang ditangani DQI kira -kira ini: Anda diberi kumpulan poin pada selembar kertas. Anda perlu menghasilkan fungsi matematika yang melewati poin -poin ini. Secara khusus, fungsi Anda harus menjadi polinomial-kombinasi variabel yang diangkat menjadi eksponen seluruh nomor dan dikalikan dengan koefisien. Tapi itu tidak bisa terlalu rumit, artinya kekuatan tidak bisa terlalu tinggi. Ini memberi Anda garis melengkung yang bergoyang naik dan turun saat bergerak melintasi halaman. Tugas Anda adalah menemukan garis wiggly yang menyentuh poin terbanyak.
Variasi masalah ini muncul dalam berbagai bentuk di seluruh ilmu komputer, terutama dalam pengkodean kesalahan dan kriptografi – bidang yang difokuskan pada data pengkodean dengan aman dan akurat seperti yang ditransmisikan. Para peneliti DQI mengakui, pada dasarnya, bahwa merencanakan garis yang lebih baik sama dengan menggeser pesan yang dikodekan lebih dekat dengan maknanya yang akurat.
