Pada tahun 1994, seorang ahli matematika menemukan cara membuat komputer kuantum melakukan sesuatu yang tidak dapat dilakukan oleh komputer klasik biasa. Penelitian ini mengungkapkan bahwa, pada prinsipnya, sebuah mesin yang didasarkan pada aturan mekanika kuantum dapat secara efisien memecah sejumlah besar faktor prima – sebuah tugas yang sangat sulit bagi komputer klasik sehingga menjadi dasar bagi sebagian besar keamanan internet saat ini.
Gelombang optimisme menyusul. Mungkin, pikir para peneliti, kita akan dapat menemukan algoritme kuantum yang dapat memecahkan sejumlah besar masalah yang berbeda.
Tapi kemajuan terhenti. "Ini lintasan yang sedikit mengecewakan," kata Ryan O'Donnel dari Universitas Carnegie Mellon. “Orang-orang seperti, 'Ini luar biasa, saya yakin kita akan mendapatkan semua jenis algoritme luar biasa lainnya.' Tidak." Para ilmuwan menemukan percepatan dramatis hanya untuk satu kelas masalah yang sempit dari dalam satu set standar disebut NP, artinya mereka memiliki solusi yang dapat diverifikasi secara efisien — seperti anjak piutang.
Begitulah yang terjadi selama hampir tiga dekade. Kemudian pada bulan April, peneliti ditemukan jenis masalah baru yang fundamental bahwa komputer kuantum harus dapat memecahkan secara eksponensial lebih cepat daripada yang klasik. Ini melibatkan penghitungan input ke proses matematika yang rumit, hanya berdasarkan output campur aduknya. Apakah masalahnya berdiri sendiri atau merupakan yang pertama di perbatasan baru dari banyak masalah lainnya belum ditentukan.
"Ada rasa senang," kata Vinod Vaikuntanathan, seorang ilmuwan komputer di Massachusetts Institute of Technology. "Banyak orang berpikir tentang apa lagi yang ada di luar sana."
Ilmuwan komputer mencoba memahami apa yang dilakukan komputer kuantum dengan lebih baik dengan mempelajari model matematika yang mewakilinya. Seringkali, mereka membayangkan model komputer kuantum atau klasik yang dipasangkan dengan mesin penghitung ideal yang disebut oracle. Oracle seperti fungsi matematika sederhana atau program komputer, mengambil input dan mengeluarkan output yang telah ditentukan. Mereka mungkin memiliki perilaku acak, mengeluarkan "ya" jika input berada dalam rentang acak tertentu (misalnya, 12 hingga 67) dan "tidak" jika tidak. Atau mereka mungkin periodik, sehingga input antara 1 hingga 10 mengembalikan "ya", 11 hingga 20 menghasilkan "tidak", 21 hingga 30 menghasilkan "ya" lagi, dan seterusnya.
Katakanlah Anda memiliki salah satu dari orakel periodik ini dan Anda tidak tahu periodenya. Yang dapat Anda lakukan hanyalah memberinya nomor dan melihat apa yang dihasilkannya. Dengan batasan tersebut, seberapa cepat komputer dapat menemukan titik? Pada tahun 1993, Daniel Simon, saat itu di Universitas Montreal, menemukan bahwa algoritme kuantum dapat menghitung jawaban untuk masalah yang terkait erat secara eksponensial lebih cepat daripada algoritme klasik mana pun.
Hasilnya memungkinkan Simon untuk menentukan salah satu petunjuk pertama di mana keunggulan dramatis untuk komputer kuantum dapat diharapkan. Tetapi ketika dia menyerahkan makalahnya ke konferensi terkemuka, itu ditolak. Namun, makalah itu menarik minat anggota junior dari komite program konferensi — Peter Shoro, yang saat itu berada di Bell Laboratories di New Jersey. Shor kemudian menemukan bahwa dia dapat mengadaptasi algoritma Simon untuk menghitung periode sebuah oracle, jika memang ada. Kemudian dia menyadari bahwa dia bisa mengadaptasi algoritme sekali lagi, untuk memecahkan persamaan yang berperilaku mirip dengan oracle periodik: persamaan yang menjelaskan pemfaktoran, yang periodik.
Hasil Shor sangat bersejarah. Algoritme kuantum yang ia temukan dapat dengan cepat mereduksi bilangan raksasa menjadi faktor prima penyusunnya, sesuatu yang tidak dapat dilakukan oleh algoritme klasik yang diketahui. Pada tahun-tahun berikutnya, para peneliti menemukan algoritma kuantum efisien lainnya. Beberapa di antaranya, seperti algoritma Shor, bahkan memberikan keuntungan eksponensial, tetapi tidak ada yang bisa membuktikan keunggulan kuantum dramatis pada masalah NP apa pun yang tidak periodik.
Kelangkaan kemajuan ini menyebabkan dua ilmuwan komputer, Scott Aaronson dari Universitas Texas, Austin, dan Andris Ambaini dari Universitas Latvia, untuk melakukan observasi. Bukti keunggulan kuantum selalu tampak bergantung pada nubuat yang memiliki semacam struktur non-acak, seperti periodisitas. Pada tahun 2009, mereka dugaan bahwa tidak mungkin ada percepatan dramatis pada masalah NP yang acak, atau tidak terstruktur. Tidak ada yang bisa menemukan pengecualian.
Dugaan mereka membatasi kekuatan komputer kuantum. Tetapi hanya dikatakan bahwa tidak ada percepatan dramatis untuk jenis masalah NP tidak terstruktur tertentu - yang memiliki jawaban ya atau tidak. Jika suatu masalah melibatkan pencarian jawaban kuantitatif yang lebih spesifik, yang dikenal sebagai masalah pencarian, dugaan itu tidak berlaku.
Dengan pemikiran itu, para peneliti Takashi Yamakawa Laboratorium Informatika Sosial NTT dan Mark Zhandri NTT Research dan Princeton University memutuskan untuk bereksperimen dengan masalah pencarian tertentu, yang diperkenalkan pada tahun 2005 oleh Regev Oded.
Bayangkan satu set baling-baling cuaca yang semuanya menunjuk ke arah yang sama. Berikan masing-masing dorongan terukur, lalu biarkan angin kencang mempengaruhi arah mereka. Regev ingin menentukan, berdasarkan arah akhir mereka, di mana mereka semua awalnya menunjuk. Masalah seperti ini kemudian disebut "belajar dengan kesalahan," karena dorongan dan angin bertindak seperti sumber kesalahan acak pada arah aslinya. Ada bukti bahwa sulit untuk memecahkan algoritma klasik dan kuantum.
Yamakawa dan Zhandry mengubah pengaturannya. Mereka memodifikasi kekuatan dorongan awal itu, membuatnya lebih dapat diprediksi. Mereka juga menyebabkan angin ditentukan oleh nubuat acak sehingga bahkan lebih acak dalam kasus-kasus tertentu tetapi benar-benar tidak aktif pada orang lain.
Dengan modifikasi ini, para peneliti menemukan bahwa algoritma kuantum dapat secara efisien menemukan arah awal. Mereka juga membuktikan bahwa setiap algoritma klasik harus lebih lambat dengan faktor eksponensial. Seperti Shor, mereka kemudian mengadaptasi algoritma mereka untuk memecahkan masalah versi dunia nyata, yang menggantikan oracle dengan persamaan matematika yang sebenarnya.
Ilmuwan komputer masih bekerja untuk memahami dan membangun masalah ini. Vaikuntanathan membandingkannya dengan yang berbeda yang muncul saat melakukan kompresi data: Saat informasi diperas, dua bit dapat secara tidak sengaja terjepit ke tempat yang sama, menimpanya. Masalah memprediksi tabrakan tersebut sebelumnya, sehingga Anda dapat menghindarinya, memiliki beberapa kemiripan. "Itu adalah kelas masalah yang pada dasarnya terlihat seperti ini," katanya. "Mungkin masalah ini dapat diselesaikan secara kuantum."
Ada harapan bahwa masalah tidak terstruktur seperti yang baru mungkin dapat dipecahkan bahkan pada komputer kuantum versi pemula saat ini, sehingga menyediakan sarana untuk mengujinya. Pemikirannya adalah bahwa masalah yang tidak terstruktur mungkin membutuhkan lebih sedikit sumber daya untuk diprogram, atau kurang sensitif terhadap kebisingan, karena mereka sudah acak. Namun sejauh ini, masalah baru masih tampak terlalu rumit untuk dipecahkan oleh komputer kuantum yang ada. “Ini masalah yang aneh. Saya tidak berpikir untuk mendefinisikannya,” kata Aaronson. "Tapi kalau dipikir-pikir, ia memiliki beberapa fitur yang sangat bagus."
Hasilnya memberikan contoh pertama keuntungan kuantum dramatis pada masalah NP tidak terstruktur. Mungkinkah ada banyak masalah lain yang mengubah dunia kuantum dari praktis tidak dapat dipecahkan menjadi dapat dipecahkan? Sekarang ada lebih banyak alasan untuk berpikir begitu.
“Ini agak menjungkirbalikkan keyakinan kami tentang jenis masalah apa yang bisa dilakukan komputer kuantum dengan baik,” kata O'Donnell.
