Dalam praktiknya, banyak program yang dirancang untuk komputer klasik tidak dapat dijalankan pada komputer kuantum karena mereka tidak dapat secara selektif melupakan informasi. Algoritma multiplikasi baru menunjukkan cara mengatasi masalah ini.
Bit klasik berwarna hitam dan putih, dan bit kuantum sedikit lebih rumitKetika saya berusia 9 tahun, orang tua saya membeli komputer baru. Dalam hampir semua hal, dia lebih baik daripada yang lama, kecuali satu: ras favorit saya tidak memulai itu. Saya ingat bagaimana saya berpikir - mengapa saya perlu komputer bermodel baru jika tidak memulai program favorit saya?
Komputer kuantum memiliki masalah yang sama. Secara teori, mereka mampu melakukan segala sesuatu yang klasik mampu. Dalam praktiknya, sifat kuantum mereka membuat hampir tidak mungkin menjalankan beberapa algoritma klasik yang paling penting.
Itulah sebabnya
karya itu , yang diterbitkan pada 15 April, berisi kabar baik.
Craig Gidney , seorang ilmuwan komputer di Google AI Quantum di Santa Barbara, California, menjelaskan versi kuantum dari algoritma klasik untuk dengan cepat mengalikan angka yang sangat besar. Pada komputer klasik, algoritma ini telah berjalan cukup lama. Tetapi sebelum pekerjaan Gidney, tidak jelas apakah mungkin untuk menyesuaikannya dengan mesin kuantum.
Lebih penting lagi, algoritma multiplikasi termasuk dalam kelas algoritma ilmu komputer di mana-mana. Gidney percaya bahwa teknik barunya akan memungkinkan komputer kuantum untuk mengimplementasikan seluruh kelas dari algoritma ini, yang sejauh ini dianggap terlalu rumit untuk digunakan dalam mesin kuantum.
Algoritma multiplikasi ini mengambil keuntungan dari penemuan, yang merupakan terobosan pertama dalam multiplikasi yang dilakukan selama beberapa ribu tahun. Metode penggandaan sekolah tradisional membutuhkan n
2 langkah, di mana n adalah jumlah karakter dalam angka yang dikalikan. Selama beberapa ribu tahun, matematikawan percaya bahwa pendekatan yang lebih efisien tidak ada.
Tetapi, seperti yang baru-baru ini kami klarifikasi dalam artikel “
Matematikawan menemukan cara ideal untuk melipatgandakan angka, ” pada 1960, matematikawan Soviet Anatoly Karatsuba menemukan cara yang lebih cepat. Metodenya adalah untuk membagi angka-angka panjang menjadi yang lebih pendek. Untuk mengalikan dua angka delapan digit, misalnya, Anda harus memecahnya menjadi dua angka empat digit, kemudian memecahnya menjadi dua angka dua digit. Maka Anda perlu melakukan beberapa operasi dengan angka dua digit dan mengembalikan hasil perkalian terakhir. Untuk melipatgandakan angka yang sangat besar, metode Karatsuba mengambil langkah yang jauh lebih sedikit daripada metode sekolah.
Ketika komputer klasik berjalan pada algoritma Karatsuba, itu menghapus informasi dalam proses. Misalnya, mengembalikan nomor dua digit kembali ke yang empat digit, ia lupa nomor dua digit. Sekarang dia hanya tertarik pada angka empat digit. Versi klasik dari algoritma ini mirip dengan seorang pendaki yang mengeluarkan peralatannya saat dia naik - dia bisa bergerak lebih cepat jika dia tidak membawa semua sampah bersamanya.
Tetapi komputer kuantum tidak dapat membuang informasi.
Komputer kuantum melakukan perhitungan melalui manipulasi dengan bit kuantum, atau "qubit." Mereka saling terkait, atau bingung. Kebingungan ini memberi peluang besar bagi komputer kuantum - alih-alih menyimpan informasi dalam bit terpisah, komputer kuantum menggunakan interaksi kompleks semua qubit. Akibatnya, untuk tugas-tugas tertentu, komputer kuantum mampu menunjukkan kekuatan komputasi yang lebih besar secara eksponensial dibandingkan dengan yang klasik.
Namun, properti yang sama yang membuat komputer kuantum begitu kuat juga membuatnya rapuh. Karena qubit terjerat, tidak mungkin untuk mengubah beberapa dari mereka tanpa mempengaruhi orang lain. Ini membuat mustahil untuk secara selektif menghapus informasi yang tersedia untuk komputer klasik. Mengembalikan qubit seperti memotong bagian-bagian web - bahkan satu potongan saja dapat menghancurkan seluruh web.
Persyaratan untuk pelestarian informasi ini mempersulit pembuatan versi kuantum dari algoritma rekursif - yaitu, beralih ke diri mereka sendiri. Dalam ilmu komputer, algoritma rekursif digunakan sangat luas, namun, agar dapat bekerja dengan cara terbaik, mereka membutuhkan komputer untuk membuang informasi di setiap langkah. Tanpa ini, komputasi akan dengan cepat menjadi tidak praktis. "Jika Anda menyimpan informasi setiap kali Anda melakukan operasi, ruang yang ditempati akan bertambah dengan jumlah operasi," kata
Ashley Montanaro , seorang spesialis informasi kuantum di Universitas Bristol. Mesin praktis apa pun akan kehabisan memori dengan cepat.
Dalam sebuah karya baru, Gidney menjelaskan metode kuantum untuk mengimplementasikan perkalian Karatsuba, yang tidak memerlukan konsumsi memori yang besar. Alih-alih menghasilkan nilai-nilai perantara untuk mendapatkan hasil akhir, ia menggunakan metode "
optimasi rekursi ekor " untuk secara langsung mengubah input menjadi output. Ini memungkinkan algoritma untuk menghindari membuat informasi antara yang tidak dapat dibuang oleh komputer kuantum. "Dia menghilangkan masalah qubit tambahan tanpa menghasilkan qubit tambahan," kata
Thomas Vaughn , seorang spesialis informasi kuantum di Universitas Creiton.
Gidney percaya metodenya akan bekerja untuk mengadaptasi banyak algoritma rekursif klasik untuk komputer kuantum. Sejauh ini, komputer kuantum masih sangat muda sehingga mereka hampir tidak dapat mengatasi penggandaan satu digit. Namun, algoritma sudah siap, dan ketika skema mereka ditingkatkan, mereka akan menjadi mampu lebih banyak.