Semesta tugas yang diperiksa komputer telah tumbuh. Berkat bahan rahasia yang mana ini terjadi? Karena keterikatan kuantum.
Bayangkan seseorang datang kepada Anda dan berkata bahwa ia memiliki oracle yang dapat mengungkapkan rahasia rahasia alam semesta. Anda mungkin tertarik pada ini, tetapi akan sulit bagi Anda untuk memercayainya. Anda ingin menemukan cara untuk mengonfirmasi bahwa oracle mengatakan yang sebenarnya.
Ini adalah masalah utama ilmu komputer. Beberapa tugas terlalu sulit untuk diselesaikan dalam jumlah waktu yang wajar. Tapi keputusan mereka mudah diverifikasi. Mengingat hal ini, para ilmuwan komputer ingin tahu: seberapa kompleks suatu tugas, solusinya masih dapat diverifikasi?
Ternyata jawaban untuk pertanyaan ini adalah: hampir tak terbayangkan rumit.
Dalam sebuah
makalah yang muncul pada bulan April 2019, dua spesialis ilmu komputer secara radikal meningkatkan jumlah tugas yang masuk dalam kategori "sulit untuk dipecahkan, mudah diverifikasi." Mereka menggambarkan metode yang memungkinkan seseorang untuk memverifikasi solusi untuk masalah kompleksitas yang hampir tidak dapat dipahami. "Kedengarannya gila," kata Thomas Widick, spesialis IT di California Institute of Technology yang tidak terlibat dalam pekerjaan ini.
Studi ini berlaku untuk komputer kuantum yang melakukan perhitungan sesuai dengan aturan non-intuitif mekanika kuantum. Komputer kuantum jarang muncul, tetapi di masa depan mereka memiliki potensi untuk merevolusi komputasi.
Pekerjaan baru, pada kenyataannya, memberi kita pengaruh atas nubuat yang maha kuasa itu. Bahkan jika oracle berjanji untuk memberikan solusi siap pakai untuk masalah yang kemungkinan solusinya jauh di luar kemampuan Anda, masih ada cara untuk memeriksa apakah oracle mengatakan yang sebenarnya.
Sampai akhir jagat raya
Ketika masalah sulit dipecahkan, tetapi mudah diverifikasi, menemukan solusi membutuhkan waktu lama, tetapi memeriksa kebenaran solusi tertentu tidak. Sebagai contoh, misalkan seseorang menunjukkan kepada Anda grafik - satu set titik (simpul) yang dihubungkan oleh garis (tepi). Seseorang bertanya apakah mungkin untuk mewarnai simpul grafik dengan tiga warna sehingga tidak ada dua simpul yang terhubung memiliki warna yang sama.
Tugas tiga warna sulit untuk dipecahkan. Dalam kasus umum, waktu yang diperlukan untuk mencari pewarnaan simpul (atau menentukan bahwa pewarnaan tersebut tidak ada) meningkat secara eksponensial dengan meningkatnya ukuran grafik. Jika, misalnya, mencari solusi untuk grafik dengan 20 simpul membutuhkan 3
20 ns - yaitu, beberapa detik, maka untuk grafik dengan 60 simpul akan membutuhkan 3
60 ns, yang 100 kali usia alam semesta saat ini.
Tapi katakanlah seseorang mengklaim telah melukis hitungan dengan tiga warna. Verifikasi aplikasi ini tidak akan memakan banyak waktu. Anda hanya perlu berkeliling semua simpul satu per satu, mempelajari simpul yang terkait dengannya. Ketika ukuran grafik meningkat, waktu pemeriksaan ini meningkat secara perlahan - seperti
polinomial . Akibatnya, komputer tidak perlu waktu lebih lama untuk memeriksa pewarnaan grafik dari 60 simpul daripada untuk memeriksa grafik 20 simpul.
"Dengan warna yang tepat dalam tiga warna, mudah untuk menguji kinerjanya," kata
John Wright , fisikawan di Massachusetts Institute of Technology, yang menulis karya ini bersama dengan
Anand Natarajan dari Caltech.
Pada 1970-an, ilmuwan komputer menentukan kelas tugas yang mudah diverifikasi, bahkan jika beberapa di antaranya sulit untuk dipecahkan. Mereka menyebut NP kelas ini,
waktu polinom non-deterministik . Sejak itu, dalam ilmu komputer, kelas NP telah dipelajari lebih dari yang lain. Secara khusus, ilmuwan komputer ingin tahu bagaimana perubahan kelas ini ketika algoritma pengujian menerima cara-cara baru untuk memverifikasi kebenaran solusi.
Pertanyaan yang tepat
Sebelum pekerjaan Natarajan dan Wright, kekuatan inspeksi meningkat dalam dua lompatan besar.
Untuk memahami yang pertama, bayangkan Anda tidak membedakan antara warna. Seseorang menempatkan dua kubus di atas meja di depan Anda, dan bertanya apakah warnanya sama atau berbeda. Tugas ini tidak mungkin bagi Anda. Selain itu, Anda tidak dapat mengkonfirmasi kebenaran solusi orang lain untuk masalah ini.
Namun, Anda diizinkan untuk mengajukan pertanyaan kepada orang yang membuktikan ini. Misalkan pepatah memberi tahu Anda bahwa kubus memiliki warna yang berbeda. Anda memanggil salah satu dari mereka "Cube A" dan yang lainnya "Cube B". Kemudian Anda menyembunyikannya di belakang, dan secara tidak sengaja bertukar tempat di antara mereka. Kemudian Anda membuka kubus dan meminta pepatah untuk menemukan mati A.
Jika kubus memiliki warna yang berbeda, ini adalah pertanyaan yang sangat sederhana. Prover akan mengenali Cube A, jika ini, katakanlah, kubus merah, dan akan menentukannya dengan benar setiap waktu.
Namun, jika kubus memiliki warna yang sama - dan pepatah keliru menyebut mereka berbeda - pepatah hanya bisa menebak mana yang mana. Oleh karena itu, ia akan dapat menentukan dengan benar Cube A hanya dalam 50% kasus. Dengan terus-menerus mempertanyakan prover tentang keputusannya, Anda dapat mengonfirmasi apakah itu benar.
Anand Natarajan dan John Wright"Penguji dapat mengirim pertanyaan ke pepatah," kata Wright, "dan mungkin di akhir pembicaraan, penguji akan lebih yakin akan jawabannya."
Pada tahun 1985, tiga ilmuwan komputer membuktikan bahwa bukti interaktif tersebut dapat digunakan untuk mengkonfirmasi solusi untuk masalah yang lebih kompleks daripada masalah dari NP. Pekerjaan mereka menciptakan kelas tugas baru, IP, "waktu polinom interaktif." Metode yang digunakan untuk mengkonfirmasi warna kubus dapat digunakan untuk mengkonfirmasi jawaban untuk pertanyaan yang jauh lebih kompleks.
Terobosan kedua terjadi pada dekade yang sama. Sepertinya logika investigasi polisi. Jika Anda memiliki dua tersangka yang melakukan kejahatan, menurut Anda, Anda tidak akan menginterogasi mereka bersama. Anda akan menginterogasinya di ruangan yang berbeda, dan Anda akan membandingkan jawaban satu dengan yang lainnya. Dengan mewawancarai mereka secara individu, Anda dapat mengungkapkan lebih banyak kebenaran daripada jika Anda memiliki satu tersangka.
"Kedua tersangka tidak akan dapat membuat cerita yang konsisten didistribusikan, karena mereka tidak tahu apa jawaban yang lain," kata Wright.
Pada tahun 1988, empat ilmuwan komputer membuktikan bahwa jika Anda meminta dua komputer untuk memecahkan masalah yang sama secara terpisah dan kemudian mempertanyakannya secara terpisah, Anda dapat mengonfirmasi kelas masalah yang bahkan lebih besar dari IP: kelas MIP, bukti interaktif dengan banyak bukti.
Dengan menggunakan pendekatan ini, dimungkinkan, misalnya, untuk mengkonfirmasi kebenaran pewarnaan grafik dalam tiga warna untuk urutan grafik yang meningkatkan ukuran jauh lebih cepat daripada grafik dari NP. Dalam NP, ukuran grafik meningkat secara linear - jumlah simpul dapat tumbuh dari 1 menjadi 2, hingga 3, hingga 4, dan seterusnya - sehingga ukuran grafik tidak lebih besar secara proporsional daripada jumlah waktu yang diperlukan untuk memeriksa pewarnaan. Tetapi dalam MIP, jumlah simpul grafik tumbuh secara eksponensial dari 2
1 menjadi 2
2 , 2
3 , 2
4 , dan seterusnya.
Akibatnya, grafik berubah menjadi terlalu besar bahkan untuk muat di memori komputer, yang harus melalui daftar simpul dan memeriksa pewarnaan. Namun, pewarnaan masih bisa diperiksa dengan menanyakan dua prover yang berbeda, tetapi terkait pertanyaan.
Dalam MIP, tester memiliki memori yang cukup untuk menjalankan program yang memungkinkan kita untuk menentukan apakah dua simpul grafik terhubung oleh tepi - dan dia dapat memverifikasi jawaban penguji untuk memastikan pewarnaannya benar.
Memperluas daftar tugas yang sulit diselesaikan, tetapi mudah diverifikasi, dari komputer klasik ke NP ke IP dan MIP. Tetapi komputer kuantum bekerja sangat berbeda. Dan selama beberapa dekade tidak jelas bagaimana penggunaannya mengubah gambar ini - apakah lebih mudah atau lebih sulit untuk memverifikasi solusi dengan bantuan mereka?
Karya baru Natarajan dan Wright memiliki jawaban untuk pertanyaan ini.
Trik kuantum
Komputer kuantum melakukan perhitungan menggunakan bit kuantum, atau qubit. Mereka memiliki properti seperti
keterikatan satu sama lain. Dan ketika dua qubit - atau bahkan sistem qubit besar - bingung, ini berarti bahwa sifat fisik mereka dengan cara tertentu saling mempengaruhi.
Dalam karya baru mereka, Natarajan dan Wright mempertimbangkan skenario yang mencakup dua komputer kuantum yang berbeda, dengan qubit satu bingung dengan qubit yang lain.
Tampaknya pengaturan seperti itu memperburuk kualitas verifikasi respons. Kekuatan penuh bukti interaktif dengan banyak prover berasal justru dari fakta bahwa Anda dapat mewawancarai dua prover secara terpisah dan memverifikasi jawaban mereka. Jika jawaban para pembacanya sama, maka kemungkinan besar jawabannya benar. Tetapi jika keadaan kuantum dari dua prover bingung, mereka tampaknya memiliki lebih banyak kesempatan untuk secara konsisten menuntut kebenaran jawaban yang salah.
Memang, ketika skenario dengan dua komputer kuantum terjerat pertama kali
diluncurkan pada tahun 2003, ilmuwan komputer menyarankan bahwa keterjeratan akan mengurangi kemungkinan verifikasi. "Reaksi yang jelas dari semua orang, termasuk saya, adalah bahwa prover dalam kasus ini memiliki lebih banyak peluang," kata Vidik. "Mereka dapat menggunakan kebingungan untuk menghubungkan jawaban mereka."
Tetapi, meskipun ada pesimisme awal, Vidik menghabiskan beberapa tahun mencoba membuktikan sebaliknya. Pada 2012, ia dan
Tsuyoshi Ito membuktikan bahwa kemampuan untuk menguji semua tugas di MIP menggunakan komputer kuantum kusut ada.
Sekarang, Natarajan dan Wright telah membuktikan bahwa situasinya bahkan lebih baik: dengan bantuan kerumitan, orang dapat membuktikan kelas masalah yang lebih besar daripada tanpanya. Dimungkinkan untuk membalikkan koneksi antara komputer kuantum terjerat untuk kepentingan verifikasi.
Untuk memahami bagaimana melakukan ini, ingat prosedur dari MIP untuk memeriksa pewarnaan grafik yang ukurannya tumbuh secara eksponensial. Penguji tidak memiliki cukup memori untuk menyimpan seluruh grafik, tetapi ia memiliki cukup memori untuk menentukan dua simpul yang terhubung, dan untuk mengajukan pertanyaan kepada penguji tentang warna simpul tersebut.
Di kelas masalah yang dipertimbangkan oleh Natarajan dan Wright - disebut NEEXP, waktu nondeterministik dua kali eksponensial - ukuran grafik tumbuh lebih cepat daripada di MIP. Grafik dalam NEEXP tumbuh pada "tingkat eksponensial ganda." Alih-alih bertambah dua derajat - 2
1 , 2
2 , 2
3 , 2
4 , dan seterusnya - jumlah simpul dalam grafik bertambah dua derajat - 2
2 1 , 2
2 2 , 2
2 3 , 2
2 4 , dan seterusnya. Akibatnya, grafik dengan cepat berubah menjadi sangat besar sehingga inspektur bahkan tidak lagi dapat menemukan sepasang simpul yang terhubung.
“Untuk mengidentifikasi simpul, diperlukan 2
n bit, yang secara eksponensial lebih besar dari yang dimiliki verifier dalam memori,” kata Natarajan. Namun, Natarajan dan Wright membuktikan bahwa adalah mungkin untuk memeriksa pewarnaan grafik eksponensial ganda dalam tiga warna, bahkan tanpa kemampuan untuk menentukan simpul mana yang perlu dimintai bukti. Faktanya adalah bahwa Anda dapat membuat prover itu sendiri memilih pertanyaan yang tepat.
Gagasan mendapatkan komputer untuk menginterogasi diri mereka sendiri tentang keputusan mereka sendiri terdengar masuk akal bagi para ilmuwan komputer seperti meminta tersangka penjahat untuk menginterogasi diri mereka sendiri jelas merupakan proposisi bodoh. Itu hanya Natarajan dan Wright membuktikan bahwa ini tidak benar. Dan alasan untuk ini adalah kebingungan.
"Negara terjerat adalah sumber daya bersama," kata Wright. "Seluruh protokol kami adalah untuk memahami cara menggunakan sumber daya bersama ini untuk membuat masalah yang saling berhubungan."
Jika komputer kuantum bingung, maka pilihan simpul mereka akan berkorelasi, dan memberikan serangkaian pertanyaan yang tepat untuk memeriksa pewarnaan dalam tiga warna.
Pada saat yang sama, inspektur tidak perlu dua komputer kuantum untuk terjalin sehingga jawaban mereka untuk pertanyaan-pertanyaan ini berkorelasi satu sama lain (ini akan mirip dengan bagaimana dua tersangka penjahat menghubungkan alibi palsu mereka). Fitur kuantum aneh lain berkaitan dengan masalah ini. Dalam mekanika kuantum,
prinsip ketidakpastian melarang kita untuk mengetahui lokasi dan momen partikel secara bersamaan - jika Anda mengukur satu properti, Anda menghancurkan informasi tentang yang lain. Prinsip ketidakpastian sangat membatasi pengetahuan Anda tentang dua sifat "pelengkap" dari sistem kuantum.
Natarajan dan Wright menggunakan ini dalam pekerjaan mereka. Untuk menghitung warna titik, mereka memaksa dua komputer kuantum untuk melakukan pengukuran yang saling melengkapi. Setiap komputer menghitung warna dari simpulnya sendiri, dan dengan demikian menghancurkan semua informasi tentang yang lain. Dengan kata lain, kebingungan memungkinkan komputer memberikan pertanyaan korelatif, tetapi prinsip ketidakpastian melarang mereka berkonspirasi untuk menjawabnya.
“Kita perlu membuat para prover lupa, dan ini adalah hal utama yang Natarajan dan Wright lakukan dalam pekerjaan mereka,” kata Vidik. "Mereka memaksa pepatah untuk menghapus informasi melalui pengukuran."
Konsekuensi dari pekerjaan mereka dapat disebut hampir eksistensial. Sebelum karya itu dirilis, batasan pengetahuan yang bisa kita peroleh dengan penuh keyakinan jauh lebih sedikit. Jika kita diberi jawaban untuk masalah dari set NEEXP, kita hanya harus menerimanya dengan iman. Tapi Natarajan dan Wright keluar dari batas-batas ini, dan memungkinkan untuk mengkonfirmasi jawaban dari dunia yang jauh lebih besar dari masalah komputasi.
Dan sekarang setelah mereka melakukan ini, tidak jelas di mana batas pembuktian selanjutnya berada. "Itu bisa lebih jauh," kata Lance Fortnau, seorang spesialis IT di Institut Teknologi Georgia. "Mereka membiarkan peluang terbuka untuk mengambil langkah selanjutnya."