Versi aslinya dari cerita ini muncul di Berapa banyak majalah.
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, diterbitkan di jurnal Sainsbertemu dengan skeptisisme langsung dari dua kelompok terpisah yang menunjukkan bagaimana melakukan serupa perhitungan pada mesin klasik.
Tetapi dalam sebuah makalah yang diposting di situs preprint ilmiah arxiv.org tahun lalu, para peneliti menggambarkan seperti apa bentuknya Speedup 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 “terobosan dalam algoritma kuantum,” kata Kampusseorang ahli matematika 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 Wolfseorang ilmuwan komputer teoritis 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 Tangseorang ilmuwan komputer di University of California, Berkeley, yang menjadi terkenal saat remaja membuat 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.
Tapi semua itu datang kemudian. Ketika para peneliti di belakang DQI mulai mengerjakan algoritma mereka, mereka bahkan tidak memiliki masalah ini dalam pikiran.
Masalah yang didekodekan
“Akan sepenuhnya masuk akal bagi peneliti yang berorientasi pada tujuan untuk memulai dengan menyatakan masalah dan kemudian menyelidiki apakah algoritma kuantum dapat menyelesaikannya lebih cepat daripada algoritma klasik,” kata Stephen Jordanseorang fisikawan di Google Quantum AI dan salah satu arsitek utama DQI. “Tentu saja, bagi kami, bukan itu yang terjadi. Kami menemukannya dengan rute yang terbelakang dan berputar.”
Stephen Jordan membantu menghasilkan pendekatan kuantum untuk masalah -masalah tertentu yang bekerja lebih baik daripada pendekatan klasik apa pun – begitu jauh.
Jordan memulai rute itu pada tahun 2023, ketika dia bergabung dengan Google dan mengetahui bahwa dia akan bekerja dengannya Eddie Farhiseorang fisikawan di Google yang pekerjaannya telah lama berfokus pada algoritma kuantum yang mengungguli yang klasik. ; Untuk Farhi, optimasi energi yang terhubung dengan fisika kuantum.
Tapi Jordan ingin melakukan sesuatu yang berbeda. Dia beralih ke konsep lain yang dibangun ke dalam fisika kuantum – mengidentifikasi segala sesuatu sebagai gelombang. Menggunakan alat matematika yang disebut Transformasi Fourier Quantum, Jordan menemukan cara untuk menerjemahkan semua jawaban potensial untuk kelas masalah optimasi yang terkenal menjadi gelombang kuantum. Dengan melakukan itu, ia dapat memanipulasi sistem kuantum sehingga gelombang yang lebih besar (dalam bentuk amplitudo kuantum yang lebih tinggi) sesuai dengan solusi yang lebih baik.
Tetapi masih ada tantangan besar yang harus diatasi. Dalam sistem kuantum, menanyakan “apa amplitudo terbesar?” tidak sesederhana mengenali gelombang terbesar di pantai. Lansekap kuantum sangat kompleks, dan tidak jelas bagaimana mengidentifikasi amplitudo kuantum yang akan sesuai dengan solusi terbaik.
Setelah banyak awal yang salah, Jordan membuat terobosan: proses pemilihan solusi terbaik ternyata mirip dengan proses penyiangan kesalahan dalam pesan kode, yang dikenal sebagai decoding. Ini adalah bidang ilmu komputer yang dipelajari dengan baik, penuh dengan teknik yang bisa dijelajahi Jordan. Dengan menerjemahkan masalah optimasi ke dalam kuantum, dan kemudian menerapkan lensa decoding ke sana, ia telah tersandung ke cara baru untuk mengembangkan algoritma kuantum.
Ilustrasi: Daniel Garcia untuk Berapa banyak majalah
Bersama Nuh Shuttyjuga di Google, Jordan mulai menguji skema decoding, melihat bagaimana mereka bernasib melawan algoritma klasik pada berbagai masalah optimasi. Mereka membutuhkan pendekatan yang tepat dan masalah di mana ia bekerja. “Ternyata algoritma klasik sulit dikalahkan,” kata Jordan. “Setelah beberapa bulan mencoba, kami masih belum meraih kemenangan untuk kuantum.”
Tetapi akhirnya, pasangan ini mendarat dengan algoritma decoding yang pertama kali diperkenalkan pada 1960 -an untuk menemukan dan memperbaiki kesalahan individu dalam pesan yang dikodekan. Menemukan masalah itu adalah kuncinya. “Ketika kami menyelidiki, kami tampaknya segera mencapai kesuksesan,” kata Jordan. Akhirnya, mereka telah menemukan masalah dan pendekatan yang, bersama -sama, tampak seperti percepatan kuantum.
Tentu saja, itu tidak berarti itu anti peluru. “Mungkin ada beberapa metode klasik yang dapat secara efisien mereplikasi seluruh pendekatan Anda,” kata Jordan. “Dequanisasi seperti itu tidak selalu jelas.”
Mendapatkan kepercayaan diri
Untuk meredakan ketakutan itu, mereka berkonsultasi dengan Mary Woottersseorang ahli teori pengkodean (dan mantan penasihat doktoral Shutty di Stanford University). Dia dengan hati -hati mencari algoritma klasik yang diketahui yang mungkin cocok dengan speedup kuantum mereka. Keuntungan diadakan. Cek tim juga menyarankan agar itu akan terus bertahan. “Mereka melakukan uji tuntas,” kata Tang.
Didukung oleh analisis ini, mereka melihat lebih hati -hati pada masalah optimasi yang mereka selesaikan. Jordan khawatir bahwa itu mungkin terlalu niche, tanpa aplikasi yang lebih luas, tetapi Shutty mengakui bahwa masalah decoding ini adalah variasi dari masalah yang terkenal dan bermanfaat dalam enkripsi dan bidang lainnya.
Jordan mengakui bahwa tanpa mesin kuantum yang cukup besar, DQI akan tetap menjadi terobosan teoretis. “DQI tidak dapat berjalan di komputer kuantum saat ini,” katanya. Tapi mereka masih bergerak maju. Sejak grup memposting pekerjaan mereka Agustus lalu, mereka telah memperluas aplikasi DQI di luar masalah asli ke kelas masalah optimasi yang lebih luas, yang mencakup lebih banyak kasus masalah “jalur terbaik” ini.
Sejauh ini, kata Jordan, ia berharap bahwa DQI dapat mengalahkan algoritma klasik dalam masalah -masalah itu juga.
Untuk saat ini, komunitas kuantum tetap gembira. “Menemukan algoritma kuantum yang menunjukkan keunggulan dibandingkan algoritma klasik adalah upaya yang sangat menarik dari tiga dekade terakhir, dan jumlah algoritma pasti yang menunjukkan keuntungan seperti itu tidak besar,” kata Kalai. “Oleh karena itu, setiap algoritma baru adalah alasan untuk perayaan.”
Cerita asli dicetak ulang dengan izin dari Berapa banyak majalahpublikasi editorial independen dari Yayasan Simons yang misinya adalah untuk meningkatkan pemahaman publik tentang sains dengan meliput perkembangan penelitian dan tren matematika dan ilmu fisik dan kehidupan.
