Ilmuwan NTT Mengatakan Mereka Memiliki Cara Baru untuk Memverifikasi Keunggulan Kuantum

Sunnyvale, California – 26 Oktober 2022 – Riset NTT mengumumkan bahwa seorang ilmuwan dari Lab Kriptografi dan Keamanan Informasi (CIS) dan seorang rekan dari Laboratorium Informatika Sosial NTT (SIL) telah menulis makalah terobosan tentang keuntungan kuantum. Makalah ini dipilih untuk dipresentasikan pada Simposium IEEE tahunan tentang Yayasan Ilmu Komputer (FOCS), yang berlangsung 31 Oktober–Nov. 3 di Denver.

Rekan penulis makalah berjudul “Keuntungan Kuantum yang Dapat Diverifikasi tanpa Struktur,” adalah Dr. Takashi Yamakawa, peneliti terkemuka di NTT SIL dan Dr. Mark Zhandry, ilmuwan senior di Penelitian NTT Laboratorium CIS. Pekerjaan itu dilakukan sebagian di Universitas Princeton, di mana Dr. Yamakawa adalah peneliti tamu dan Dr. Zhandry juga menjabat sebagai asisten profesor ilmu komputer. 

Topik keuntungan kuantum (atau percepatan kuantum) berkaitan dengan jenis masalah yang dapat diselesaikan oleh komputer kuantum lebih cepat daripada komputer klasik, atau non-kuantum, dan seberapa cepat mereka. Masalah-masalah tersebut biasanya digambarkan sebagai kelas waktu polinomial (NP) non-deterministik. Berapa banyak keuntungan yang bisa sangat bervariasi. Komputer kuantum mungkin dapat memecahkan masalah tertentu dalam satu menit atau detik yang membutuhkan komputer klasik seminggu, atau mungkin jumlah waktu yang sangat eksponensial. Dalam makalah ini, penulis membahas tantangan untuk memverifikasi keunggulan ini, dan melakukannya secara efisien. Sampai saat ini, demonstrasi keunggulan kuantum telah melibatkan "struktur" yang signifikan, atau komunikasi bolak-balik antara dua pihak atau lebih. Terobosan makalah Yamakawa dan Zhandry adalah untuk menunjukkan masalah sulit NP di mana verifikasi dimungkinkan tanpa struktur.

“Ini adalah pertama kalinya kami melihat percepatan kuantum eksponensial untuk masalah pencarian NP, yang hanya membutuhkan oracle acak,” kata Profesor Ilmu Komputer Universitas Texas di Austin Dr. Scott Aaronson, yang mengomentari versi awal makalah selama lokakarya pada 13 Juni 2022, di Institut Simons untuk Teori Komputasi. Dengan hanya membutuhkan oracle acak, yaitu kotak hitam teoretis yang menghasilkan respons acak untuk setiap kueri, Yamakawa dan Zhandry membangun masalah mereka pada asumsi komputasi yang tidak terstruktur. Dengan demikian, masalah mereka selaras lebih dekat dengan fungsi satu arah daripada yang terstruktur, seperti yang ditemukan dalam kriptografi kunci publik. Penyelarasan satu arah itu memfasilitasi verifikasi yang efisien.

“Sangat menyenangkan melihat kriptografer yang berafiliasi dengan NTT berkolaborasi dalam penelitian yang sekali lagi pantas diberi label 'terobosan,' terutama dalam makalah yang memperkaya pemahaman kita tentang komputasi kuantum, area fokus lain bagi kami di NTT Research,” kata Kazuhiro Gomi , Presiden dan CEO Riset NTT. “Selamat dan harapan terbaik untuk semua peserta dalam konferensi IEEE yang bergengsi ini.” 

Masalah pencarian NP yang dibuat Yamakawa dan Zhandry adalah masalah dua-dalam-satu yang memerlukan pencarian 1) string simbol-n yang merupakan kata kode dari kode koreksi kesalahan yang diberikan, dan 2) string simbol-n di mana masing-masing simbol dipetakan ke nol di bawah oracle acak. Setiap masalah secara terpisah itu mudah. Tetapi untuk menemukan satu string simbol yang merupakan kata sandi dan peta ke nol jauh lebih sulit, setidaknya secara klasik. “Jika Anda kuantum, Anda dapat menyelesaikan ini dalam waktu polinomial,” kata Dr. Zhandry, “tetapi jika Anda klasik, setidaknya jika Anda berada dalam model kotak hitam ini, Anda memerlukan waktu eksponensial.” Di sisi lain, jika diberikan solusi potensial, mudah untuk memverifikasinya dengan memeriksa bahwa solusi tersebut secara terpisah menyelesaikan masing-masing dari dua masalah. Perhatikan bahwa, sebagaimana layaknya makalah untuk FOCS, pekerjaan ini bersifat dasar atau mendasar. Seperti yang dikemukakan dalam ceramah Dr. Aaronson di Simons Institute (dibahas dalam Riset NTT ini artikel blog), argumen Yamakawa-Zhandry termasuk dalam kelas percepatan dapat dengan mudah diperiksa secara matematis, tetapi tidak ditunjukkan secara praktis oleh komputer kuantum aktual dalam waktu dekat. Di luar skema verifikasi terobosannya, makalah ini juga menunjukkan sesuatu yang baru mengenai tingkat percepatan kuantum.

“Sebelum pekerjaan kami, kami memiliki contoh keuntungan kuantum untuk masalah NP, seperti pemfaktoran atau, dalam pengaturan kotak hitam, menemukan titik. Tetapi ternyata algoritme kuantum yang mendasari semua contoh ini pada dasarnya adalah penemuan periode – meskipun menunjukkan bagaimana menerapkan penemuan periode pada contoh-contoh ini seringkali tidak sepele,” kata Dr. Zhandry. “Makalah kami menunjukkan setidaknya ada kasus kedua. Anda dapat dengan optimis menafsirkannya dengan mengatakan ada harapan bahwa keuntungan kuantum lebih luas daripada yang mungkin kita duga sebelumnya.

Disponsori oleh IEEE Computer Society Technical Committee on Mathematical Foundations of Computing (TCMF), FOCS adalah konferensi terkemuka di bidang ilmu komputer teoretis. Panggilan untuk makalah untuk FOCS 2022, pertemuan tahunan ke-63, mendaftarkan komputasi kuantum sebagai salah satu dari 17 bidang minat umum. Makalah Yamakawa-Zhandry dijadwalkan akan dipresentasikan pada 31 Oktober 2022, pukul 10:15 pagi MT. Untuk mempelajari lebih lanjut tentang dan mendaftar untuk acara ini, kunjungi FOKUS 2022 website.