Urmila Mahadev menghabiskan delapan tahun di magistrasi untuk mencari jawaban atas salah satu pertanyaan paling mendasar dari komputasi kuantum: bagaimana kita tahu bahwa komputer kuantum setidaknya melakukan sesuatu pada level kuantum?
Pada musim semi 2017, Urmila Mahadev berada di posisi yang baik, dari sudut pandang sebagian besar mahasiswa pascasarjana. Dia baru saja memecahkan masalah penting komputasi kuantum - bidang ilmu komputer, mengambil kemampuannya dari hukum fisika kuantum yang aneh. Bersama dengan karya-karya sebelumnya, hasil baru oleh Mahadev menggambarkan apa yang disebut "Komputasi buta," membuatnya "jelas bahwa dia adalah bintang yang sedang naik daun," kata
Scott Aaronson , seorang spesialis IT di University of Texas di Austin.
Mahadev, yang pada waktu itu berusia 28 tahun, sudah memasuki tahun ketujuh di sekolah pascasarjana di University of California di Berkeley - jauh lebih lama daripada waktu yang dibutuhkan sebagian besar siswa untuk kehilangan kesabaran dan ingin menyelesaikan sekolah. Dan kemudian, akhirnya, ia dapat menulis "disertasi doktoral yang luar biasa," kata
Umesh Vazirani , kuratornya di Berkeley.
Tetapi Mahadev tidak selesai belajar tahun itu. Dia bahkan tidak mempertimbangkan masalah ini. Dia belum selesai.
Selama lebih dari lima tahun, dia bekerja dengan tugas penelitian lain, yang disebut Aaronson "salah satu pertanyaan paling mendasar yang dapat ditanyakan di bidang komputasi kuantum." Yaitu: jika Anda meminta komputer kuantum untuk membuat perhitungan untuk Anda, bagaimana Anda tahu jika itu mengikuti instruksi Anda, dan memang, apakah ia melakukan sesuatu pada tingkat kuantum?
Pertanyaan ini mungkin segera berhenti menjadi murni akademis. Para peneliti berharap bahwa tidak banyak tahun akan berlalu, dan komputer kuantum akan dapat menawarkan akselerasi eksponensial dalam menyelesaikan banyak masalah, dari memodelkan situasi di dekat lubang hitam hingga mensimulasikan lipatan protein besar.
Tetapi begitu komputer kuantum dapat melakukan perhitungan yang tidak mampu dilakukan oleh komputer klasik, bagaimana kita tahu bahwa komputer itu menjalankannya dengan benar? Jika Anda tidak percaya komputer biasa, secara teori Anda bisa mempelajari sendiri setiap langkah perhitungannya sendiri. Tetapi komputer kuantum secara inheren menolak pemeriksaan semacam itu. Untuk memulainya, pekerjaan mereka sangat rumit: untuk merekam deskripsi keadaan internal komputer, yang hanya terdiri dari beberapa ratus bit kuantum, atau qubit, Anda akan memerlukan hard disk yang lebih besar daripada Semesta yang diamati.
Dan bahkan jika Anda memiliki tempat untuk menulis deskripsi ini, itu tidak dapat dipisahkan. Keadaan internal komputer kuantum biasanya merupakan superposisi dari banyak bukan kuantum, tetapi keadaan klasik (seperti kucing Schrödinger, yang hidup dan mati). Tetapi segera setelah Anda mengukur keadaan kuantum, itu segera runtuh menjadi salah satu yang klasik. Lihatlah di dalam komputer kuantum dengan 300 qubit - dan Anda hanya akan melihat 300 bit klasik, nol dan satu, dengan sopan membalas Anda dengan tersenyum.
"Komputer kuantum kuat, tetapi misterius," kata Vazirani.
Mengingat keterbatasan ini, para ilmuwan komputer telah lama berpikir tentang apakah komputer kuantum dapat memberikan jaminan yang benar-benar dapat diandalkan bahwa ia benar-benar melakukan apa yang diklaimnya. "Akankah interaksi antara dunia kuantum dan klasik cukup kuat untuk memungkinkan dialog semacam itu?" Tanya
Dorit Akharonova , seorang ilmuwan komputer di Hebrew University of Jerusalem.
Pada tahun kedua hakim, Mahadev ditangkap oleh tugas ini, dan dia bahkan tidak sepenuhnya mengerti mengapa. Pada tahun-tahun berikutnya, dia mencoba menggunakan satu pendekatan kepadanya, kemudian yang lain. "Saya memiliki banyak momen seperti ketika saya merasa melakukan segala sesuatu dengan benar, dan kemudian semuanya hancur - sangat cepat, atau setelah satu tahun," katanya.
Tetapi dia menolak untuk menyerah. Mahadev menunjukkan tingkat tekad yang tidak berubah sehingga Vazirani belum pernah bertemu sebelumnya. "Dalam hal ini, Urmila benar-benar luar biasa," katanya.
Dan sekarang, setelah delapan tahun studi pascasarjana, Mahadev berhasil. Dia menciptakan protokol interaktif yang dengannya pengguna yang tidak memiliki kemampuan kuantum dapat menggunakan kriptografi untuk mengekang komputer kuantum dan mengarahkannya ke mana saja, dengan keyakinan penuh bahwa komputer kuantum mematuhi perintah. Pendekatan Mahadev, kata Vazirani, memberi pengguna "tuas tekanan yang tidak bisa dihilangkan komputer."
"Ini benar-benar mencengangkan," bahwa seorang mahasiswa pascasarjana dapat mencapai hasil ini sendirian, kata Aaronson.
Mahadev, sekarang menjadi postdoc penelitian di Berkeley, mempresentasikan protokolnya pada Oktober 2018 di
Simposium tahunan
Ilmu Komputer , salah satu konferensi komputer terbesar yang diadakan tahun ini di Paris. Penonton memberi penghargaan karyanya dengan hadiah "karya terbaik" dan "karya siswa terbaik" - penghargaan langka untuk seorang spesialis dalam ilmu komputer teoretis.
Dalam sebuah posting blog,
Thomas Widick , seorang spesialis TI di California Institute of Technology, yang telah bekerja dengan Mahadev di masa lalu, menggambarkan hasilnya sebagai "salah satu ide paling luar biasa yang muncul di persimpangan komputasi kuantum dan informatika teoretis dalam beberapa tahun terakhir."
Para peneliti di bidang ilmu komputer tidak hanya senang dengan kemampuan protokol Mahadev, tetapi juga dengan pendekatan baru yang secara radikal membantu mengatasi masalah ini. Penggunaan kriptografi klasik di bidang kuantum adalah "ide yang benar-benar inovatif," tulis Vidik. "Saya pikir banyak hasil lain akan tumbuh pada ide-ide ini."
Jauh
Mahadev tumbuh di Los Angeles, di keluarga dokter, dan belajar di University of Southern California, di mana dia pindah dari satu daerah ke daerah lain, awalnya hanya yakin bahwa dia sendiri tidak ingin menjadi dokter. Kemudian dia menjadi sangat tertarik dalam kursus ilmu komputer teoretis, yang diajarkan oleh Leonard Aidleman, salah satu pencipta algoritma enkripsi RSA yang terkenal. Dia memasuki sekolah pascasarjana di Berkeley, menunjukkan dalam catatan penjelasan bahwa dia tertarik pada semua aspek ilmu komputer teoretis - kecuali komputasi kuantum.
"Itu adalah sesuatu yang benar-benar asing di mana aku paling tidak tahu," katanya.
Tetapi, begitu sampai di Berkeley, ia segera berubah pikiran di bawah pengaruh penjelasan Wazirani yang tersedia. Dia memperkenalkannya pada pencarian protokol untuk mengkonfirmasi komputasi kuantum, dan tugas ini "benar-benar membuat imajinasinya bekerja," kata Vazirani.
"Protokolnya seperti teka-teki," Mahadev menjelaskan. "Ini lebih mudah bagi saya daripada dengan pertanyaan lain, karena di sini Anda dapat segera mulai memikirkan protokol, memecahnya menjadi berkeping-keping, dan menonton bagaimana mereka bekerja." Dia memilih tugas ini untuk doktornya, memulai "sangat jauh," seperti yang dikatakan Vazirani.
Jika komputer kuantum dapat memecahkan masalah yang tidak mampu dilakukan oleh komputer klasik, ini tidak secara otomatis berarti bahwa solusinya akan sulit untuk diverifikasi. Ambil, misalnya, masalah memfaktorkan sejumlah besar - diyakini bahwa komputer kuantum besar dapat menyelesaikannya secara efisien, tetapi pada saat yang sama tetap berada di luar kemampuan komputer klasik mana pun. Tetapi bahkan jika komputer klasik tidak dapat memperhitungkan faktor angka, ia dapat dengan mudah memeriksa apakah hasil kuantum benar - hanya perlu mengalikan semua faktor dan melihat apakah mereka memberikan jawaban yang benar.
Namun, para ilmuwan komputer percaya (dan baru-baru ini mengambil langkah menuju pembuktian) bahwa banyak tugas yang dapat diselesaikan oleh komputer kuantum tanpa fitur seperti itu. Dengan kata lain, komputer klasik tidak hanya tidak dapat menyelesaikannya, bahkan tidak dapat mengenali apakah solusi yang diajukan akan benar. Akibatnya, pada 2004,
Daniel Gottsman , seorang ahli fisika teoretis di Waterloo Perimeter Institute, bertanya apakah mungkin untuk membuat protokol apa pun yang memungkinkan komputer kuantum membuktikan kepada pengamat non-kuantum bahwa ia benar-benar mencapai apa yang ia klaim.
Selama empat tahun, para peneliti komputasi kuantum telah menemukan jawaban parsial. Dua tim yang berbeda
menunjukkan bahwa komputer kuantum dapat membuktikan perhitungannya, tetapi tidak ke verifier murni klasik, tetapi ke satu yang memiliki akses ke komputer kuantum yang sangat kecil. Para peneliti kemudian meningkatkan pendekatan ini dengan menunjukkan bahwa tester hanya membutuhkan kemampuan untuk mengukur keadaan satu qubit pada suatu waktu.
Dan pada tahun 2012, tim peneliti, termasuk Vazirani, menunjukkan bahwa verifier klasik sepenuhnya dapat memverifikasi perhitungan kuantum jika dilakukan oleh sepasang komputer kuantum yang tidak saling berkomunikasi. Namun, pendekatan mereka secara khusus dirancang untuk skenario seperti itu, dan tugas itu tampaknya menemui jalan buntu, kata Gottsman. "Saya pikir mungkin ada orang yang berpikir bahwa tidak ada cara untuk melangkah lebih jauh."
Sekitar waktu ini, Mahadev dihadapkan dengan masalah konfirmasi. Pada awalnya, ia mencoba untuk menghasilkan hasil "tanpa syarat", tanpa menentukan apa yang dapat dan tidak bisa dilakukan oleh komputer kuantum. Tetapi, setelah dia mengerjakan tugas untuk beberapa waktu tanpa hasil, Vazirani malah mengusulkan kemungkinan menggunakan kriptografi "post-quantum" - yaitu, kriptografi, pemecahannya, menurut para peneliti, berada di luar kemampuan bahkan komputer kuantum, walaupun pasti mereka tidak tahu. (Metode seperti algoritma RSA yang digunakan untuk mengenkripsi transfer online bukan post-kuantum - komputer kuantum besar dapat memecahkannya, karena keamanannya didasarkan pada kesulitan memfaktorkan jumlah besar).
Pada 2016, saat mengerjakan tugas yang berbeda, Mahadev dan Vazirani membuat terobosan, yang akan terbukti menentukan di masa depan. Bersama dengan
Paul Cristiano , seorang spesialis IT di OpenAI, sebuah perusahaan yang berbasis di San Francisco, mereka menemukan cara untuk menggunakan kriptografi untuk membuat komputer kuantum masuk ke "keadaan rahasia" —sebuah negara yang dideskripsikan dengan verifier klasik, tetapi tidak oleh komputer kuantum itu sendiri .
Prosedur mereka didasarkan pada fungsi "jebakan" - yang mudah dijalankan, tetapi sulit untuk dibalik, kecuali Anda memiliki kunci kriptografi rahasia. (Pada saat itu, para peneliti belum tahu bagaimana membuat jebakan yang cocok - ini terjadi kemudian). Fungsi juga harus memiliki properti "dua menjadi satu", yang berarti bahwa untuk setiap set data output ada dua set data input yang berbeda. Sebagai contoh, kita dapat membayangkan fungsi angka kuadrat - selain angka 0, untuk setiap hasil (misalnya, 9) ada dua angka input yang sesuai (3 dan -3).
Berbekal fungsi serupa, Anda dapat membuat komputer kuantum masuk ke keadaan rahasia sebagai berikut. Pertama, Anda meminta komputer tugas membangun superposisi dari semua data input yang mungkin dari fungsi (ini mungkin tampak seperti tugas yang sulit bagi komputer, tetapi sebenarnya itu sederhana). Kemudian Anda memberi tahu komputer untuk menerapkan fungsi pada superposisi raksasa ini, menciptakan keadaan baru yang merupakan superposisi dari semua kemungkinan output fungsi. Superposisi input dan output akan membingungkan, yang berarti bahwa mengukur salah satu dari mereka akan langsung mempengaruhi yang lain.
Kemudian Anda memesan komputer untuk mengukur kondisi akhir dan melaporkan hasilnya. Suatu pengukuran menciutkan keadaan menjadi salah satu set data keluaran yang mungkin, dan keadaan masukan runtuh agar sesuai dengannya, karena mereka bingung - misalnya, jika kita menggunakan fungsi kuadrat, maka jika keadaan keluaran adalah 9, maka input akan runtuh ke superposisi 3 dan -3.
Tapi ingat bahwa kami menggunakan fungsi perangkap. Kami memiliki kunci rahasia untuk jebakan, sehingga kami dapat dengan mudah mengetahui dua status yang membentuk superposisi input. Komputer kuantum tidak bisa. Dan dia tidak bisa begitu saja mengukur superposisi input untuk mencari tahu apa yang terkandung di dalamnya, karena pengukuran seperti itu akan menghancurkannya lebih jauh, meninggalkan komputer satu dari dua opsi, tanpa kemampuan untuk menghitung yang lain.
Pada 2017, Mahadev memahami cara membuat fungsi trap yang menjadi dasar metode state rahasia menggunakan kriptografi yang disebut
Learning with Errors (LWE). Dengan menggunakan fungsi perangkap ini, ia dapat membuat versi kuantum komputasi "buta", yang dengannya pengguna sistem komputasi awan dapat menyembunyikan data mereka sehingga komputer cloud tidak dapat membacanya, bahkan jika mereka melakukan perhitungan dengan mereka. Tak lama kemudian, Mahadev, Wazirani dan Cristiano bekerja sama dengan Vidik dan
Zwika Brackerski (dari Weizmann Institute di Israel) untuk lebih meningkatkan kualitas fungsi-fungsi ini dan menggunakan metode rahasia untuk mengembangkan cara yang dijamin bahwa komputer kuantum dapat menghasilkan
angka acak yang dapat
dibuktikan .
Mahadev sudah bisa mendapatkan gelar berdasarkan hasil seperti itu, tetapi dia bermaksud untuk terus bekerja sampai dia menyelesaikan masalah konfirmasi. "Saya tidak pernah memikirkan rilis karena tujuan saya sama sekali bukan rilis," katanya.
Terkadang ketidakpastian dalam kemampuan untuk menyelesaikan masalah ini menekannya. Tetapi, dia berkata, "Saya menghabiskan waktu mempelajari hal-hal yang menarik minat saya, sehingga hiburan ini tidak bisa disebut sia-sia."
Diukir di batu
Mahadev mencoba menggunakan pendekatan berbeda untuk metode rahasia negara untuk mengatur protokol konfirmasi, tetapi untuk beberapa waktu ini tidak mengarah pada apa pun. Dan kemudian sebuah ide muncul di benaknya: para peneliti telah menunjukkan bahwa tester dapat memeriksa komputer kuantum jika ia memiliki kemampuan untuk mengukur bit kuantum. Menurut definisi, verifikator klasik tidak memiliki kesempatan seperti itu. Tetapi bagaimana jika seorang penguji klasik dapat membuat komputer kuantum melakukan pengukuran sendiri dan dengan jujur melaporkan hasilnya?
Kesulitannya adalah bagaimana Mahadev memahami untuk membuat komputer kuantum berjanji untuk membuat pengukuran spesifik sebelum dia mengetahui pengukuran yang akan diminta oleh inspektur - jika tidak, akan sangat sederhana bagi komputer untuk menipu dia. Di sinilah metode rahasia negara berperan. Protokol Mahadev membutuhkan komputer kuantum untuk membuat keadaan rahasia terlebih dahulu, dan kemudian membingungkannya dengan keadaan yang harus diukur. Dan baru saat itulah komputer tahu pengukuran apa yang perlu dilakukan.
Karena komputer tidak mengetahui detail internal negara rahasia yang diketahui oleh inspektur, Mahadev menunjukkan bahwa komputer kuantum tidak dapat menipu dengan cara apa pun, tanpa meninggalkan keraguan tentang hal itu. Bahkan, Vidik menulis, qubit yang perlu diukur oleh sebuah komputer "diukir di atas batu kriptografi." Oleh karena itu, jika hasil pengukuran terlihat seperti bukti yang benar, maka inspektur dapat memastikan hal itu.
“Ini ide yang luar biasa! - tulis Vidik. "Dia memukulku setiap kali Urmila menjelaskannya."
Protokol konfirmasi Mahadev - bersama dengan generator angka acak dan enkripsi buta - bergantung pada asumsi bahwa komputer kuantum tidak dapat memecahkan LWE. Sejauh ini, LWE secara luas dianggap sebagai kandidat utama untuk kriptografi pasca-kuantum, dan segera Lembaga Standar dan Teknologi Nasional dapat menyetujuinya sebagai standar kriptografi baru, untuk menggantikan yang cenderung retak dengan komputer kuantum. Tetapi ini tidak menjamin bahwa itu sebenarnya aman terhadap komputer kuantum, Gottsman memperingatkan. "Tapi sejauh ini semuanya jelas," katanya. "Belum ada yang menemukan bukti kemungkinan untuk menghancurkannya."
Bagaimanapun, kepercayaan protokol pada LWE membuat Mahadev menjadi pemenang dalam hal apa pun, tulis Vidik. Satu-satunya cara komputer kuantum dapat mengelabui protokol adalah jika seseorang dari dunia komputasi kuantum menemukan cara meretas LWE, yang dengan sendirinya akan menjadi prestasi luar biasa.
Protokol Mahadev tidak mungkin diimplementasikan pada komputer kuantum nyata di masa mendatang.
Sejauh ini, ia membutuhkan terlalu banyak daya komputasi dari sudut pandang praktis. Tetapi di masa depan ini dapat berubah seiring pertumbuhan komputer kuantum, dan para peneliti merampingkan protokol ini.Protokol tidak mungkin muncul dalam, katakanlah, lima tahun ke depan, tetapi "itu bukan fiksi ilmiah," kata Aaronson. "Pada topik ini sudah mungkin untuk mulai berpikir, jika semuanya berjalan sebagaimana mestinya, pada tahap selanjutnya dalam pengembangan komputer kuantum."Dan, mengingat seberapa cepat daerah ini berkembang, tahap ini mungkin dimulai lebih awal dari yang diharapkan. Lagi pula, hanya lima tahun yang lalu, kata Vidik, para peneliti percaya bahwa sampai komputer kuantum tidak dapat menyelesaikan masalah yang tidak mampu dimiliki komputer klasik, bertahun-tahun lagi akan berlalu. "Dan sekarang," katanya, "orang-orang percaya bahwa ini akan terjadi dalam satu atau dua tahun."Makhadev, setelah menyelesaikan masalah favoritnya, tetap dalam keadaan agak bingung. Mahadev mengatakan bahwa dia ingin memahami apa sebenarnya yang membuat masalah ini begitu cocok untuknya. "Sekarang aku perlu mencari beberapa pertanyaan lain, jadi akan menyenangkan untuk mengetahuinya." Tetapi para ahli di bidang informatika teoretis tidak mempertimbangkan kombinasi komputasi kuantum dan kriptografi yang Mahadev berhasil menjadi akhir sejarah, tetapi hanya permulaan studi tentang apa yang mungkin menjadi sumber kaya ide-ide baru."Sepertinya saya bahwa banyak ide turunan akan mengikuti," kata Aaronson. "Saya menantikan hasil baru dari Urmila."