Yuvin Tan yang berusia 18 tahun membuktikan bahwa komputer klasik dapat menyelesaikan "masalah rekomendasi" hampir secepat komputer kuantum. Hasil ini membatalkan salah satu contoh terbaik percepatan perhitungan kuantum.
Seorang remaja Texas mengepung perkembangan komputasi kuantum. Dalam sebuah artikel yang diterbitkan bulan ini di Internet
, Yuvin Tan yang berusia 18 tahun membuktikan bahwa komputer biasa dapat memecahkan masalah komputasi yang penting dengan kecepatan yang
berpotensi sebanding dengan komputer kuantum.
Dalam bentuknya yang paling praktis, masalah rekomendasi terkait dengan bagaimana layanan seperti Amazon dan Netflix menentukan produk mana yang Anda sukai. Ilmuwan komputer menganggapnya sebagai
salah satu contoh tugas terbaik yang akan diselesaikan secara eksponensial lebih cepat pada komputer kuantum - yang menekankan
kemampuan potensial
dari mesin-mesin futuristik ini. Dan sekarang Tan membantah pendapat ini.
"Itu adalah salah satu contoh yang menentukan percepatan kuantum - dan sekarang telah menghilang," kata Tang, yang lulus dari University of Texas di Austin pada musim semi dan memulai studi PhD musim gugur di Washington University.
Pada tahun 2014, pada usia 14, Tang melompati kelas 4, 5, dan 6, dan memasuki Universitas Texas, di mana ia lulus dalam matematika dan ilmu komputer. Pada musim semi 2017, Tan mengambil kursus informasi kuantum, yang diajarkan oleh
Scott Aaronson , seorang peneliti terkenal di bidang komputasi kuantum. Aaronson mengenali seorang siswa berbakat luar biasa di Tan dan mengundangnya untuk menjadi penasihatnya dalam proyek penelitian independen. Aaronson memberi Tan beberapa tugas untuk dipilih, termasuk masalah rekomendasi. Tan memilihnya dengan agak enggan.
"Saya ragu-ragu karena sepertinya agak rumit, tetapi itu adalah tugas yang paling sederhana yang dia usulkan kepada saya," kata Tan.
Tujuan dari rekomendasi ini adalah untuk memberikan rekomendasi pada produk yang mungkin disukai pengguna. Pertimbangkan Netflix. Dia tahu film apa yang kamu tonton. Dia tahu apa yang ditonton jutaan penggunanya. Dengan informasi ini, apakah mungkin untuk mengetahui apa yang ingin Anda lihat lebih jauh?
Data ini dapat direpresentasikan dalam bentuk grid besar, atau matriks, di atasnya semua film terdaftar, di samping semua adalah pengguna, dan di dalamnya ada nilai-nilai yang mengukur seberapa besar masing-masing pengguna menyukai setiap film. Algoritma yang baik akan menghasilkan daftar rekomendasi, dengan cepat dan akurat mendeteksi kesamaan antara film dan pengguna, dan mengisi sel-sel kosong dari matriks.
Pada 2016, ilmuwan komputer
Iordanis Kerenidis dan
Anupam Prakash menerbitkan
algoritma kuantum yang memecahkan masalah rekomendasi secara eksponensial lebih cepat daripada algoritma klasik yang dikenal. Mereka menerima percepatan kuantum seperti itu, khususnya, karena penyederhanaan masalah. Alih-alih mengisi seluruh matriks dan menentukan satu-satunya produk terbaik untuk direkomendasikan, mereka datang dengan cara untuk memecah pengguna menjadi sejumlah kecil kategori - apakah mereka suka blockbuster atau bioskop independen? - dan memproses data yang ada sedemikian rupa untuk memberikan rekomendasi yang cukup bagus.
Pada saat karya Kerenidis dan Prakash muncul, ada sangat sedikit contoh masalah yang seharusnya diselesaikan komputer kuantum secara eksponensial lebih cepat daripada yang klasik. Untuk sebagian besar, tugas-tugas ini khusus - masalah sempit yang dirancang khusus untuk mengambil keuntungan dari kekuatan komputer kuantum (termasuk masalah "
korelasi " yang sudah kita tulis). Karya Kerenidis dan Prakash menarik karena menyoroti masalah nyata, penting bagi orang-orang, di mana komputer kuantum menyalip yang klasik.
"Dari sudut pandang saya, ini adalah salah satu contoh pertama pembelajaran mesin dan pemrosesan data besar, di mana kami menunjukkan bahwa komputer kuantum dapat melakukan sesuatu yang kami belum tahu bagaimana melakukannya dengan menggunakan metode klasik," kata Kerenidis, spesialis dalam ilmu komputer dari Paris Institute for Computer Science Research.
Kerenidis dan Prakash membuktikan bahwa komputer kuantum dapat memecahkan masalah rekomendasi secara eksponensial lebih cepat daripada algoritma yang dikenal, tetapi mereka belum membuktikan bahwa tidak ada algoritma klasik yang cepat. Karena itu, ketika Aaronson mulai bekerja dengan Tan pada tahun 2017, ia mengajukan tugas seperti itu - untuk membuktikan tidak adanya algoritma klasik yang cepat, membenarkan percepatan kuantum dari Kerenidis dan Prakash.
"Tampak bagi saya bahwa ini akan menjadi poin penting yang akan kita siapkan untuk menyelesaikan cerita ini," kata Aaronson, yang pada waktu itu percaya bahwa algoritma klasik cepat tidak ada.
Tang mulai bekerja pada musim gugur 2017 ini, berharap bahwa tugas rekomendasi akan menjadi subjek disertasinya. Selama beberapa bulan, Tan mencoba membuktikan ketidakmungkinan keberadaan suatu algoritma klasik. Waktu berlalu, dan Tan mulai berpikir bahwa mungkin algoritma semacam itu memang ada.
"Saya mulai percaya pada keberadaan algoritma klasik, tetapi saya tidak dapat meyakinkan diri saya tentang hal ini, karena Scott berpikir bahwa dia tidak ada, dan dia adalah otoritas bagi saya," kata Tan.
Akhirnya, ketika batas waktu untuk disertasi sudah habis, Tan menulis surat kepada Aaronson, di mana ia mengakui kecurigaannya yang semakin besar. "Tan pada dasarnya menulis yang berikut kepada saya: Saya pikir algoritma klasik cepat ada," kata Aaronson.
Sepanjang musim semi, Tang menuliskan hasilnya dan bekerja dengan Aaronson untuk mengklarifikasi beberapa langkah pembuktian. Ditemukan oleh Tan, algoritma klasik cepat terinspirasi oleh algoritma kuantum cepat yang ditemukan oleh Kerenidis dan Prakash dua tahun sebelumnya. Tan menunjukkan bahwa pengambilan sampel kuantum yang digunakan dalam algoritma mereka dapat direproduksi dalam kondisi klasik. Algoritma Tan, seperti algoritma Kerenidis dan Prakash, dieksekusi dalam waktu polylogaritmik - yaitu, waktu perhitungan diperkirakan oleh logaritma parameter seperti jumlah pengguna dan produk - dan secara eksponensial lebih cepat daripada algoritma klasik lainnya yang sebelumnya dikenal.
Setelah Tan menyelesaikan algoritme, Aaronson ingin memastikan itu benar sebelum diterbitkan. "Saya masih gugup tentang kenyataan bahwa jika setelah publikasi karya Tan ternyata tidak benar, maka pekerjaan besar pertama dalam karir Tan akan berubah menjadi nihil," kata Aaronson.
Aaronson berencana menghadiri lokakarya komputasi kuantum di University of California di Berkeley pada Juni. Para tokoh dari daerah ini akan berkumpul di sana, termasuk Kerenidis dan Prakash. Aaronson mengundang Than bersamanya ke Berkeley untuk menyajikan algoritme secara informal setelah bagian resmi konferensi.
Pada pagi hari tanggal 18 dan pagi hari tanggal 19 Juni, Tan memberikan dua ceramah, menjawab pertanyaan dari para hadirin. Setelah empat jam, sebuah konsensus tercapai: algoritma Tan klasik tampak seperti yang tepat. Apa yang banyak dari mereka yang hadir tidak mengerti adalah bagaimana Tan muda. "Saya tidak tahu bahwa Yuvin berusia 18 tahun, dan tentu saja saya tidak merasa begitu dari hasil percakapan. Tampak bagi saya bahwa Juvin sedang berbicara sebagai orang dewasa, ”kata Kerenidis. Sekarang algoritma akan memiliki peer review formal sebelum dipublikasikan.
Untuk komputasi kuantum, hasil Tan adalah langkah mundur. Atau tidak. Tang menghilangkan salah satu contoh terbaik dari keunggulan kuantum. Pada saat yang sama, karya Tan adalah bukti lain dari keberadaan
interaksi yang bermanfaat antara studi algoritma klasik dan kuantum.
“Tang menghilangkan percepatan kuantum Kerenidis dan Prakash, tetapi dalam arti lain, Tang berkontribusi terhadap peningkatan besar dan didasarkan pada pekerjaan mereka. Tang tidak akan pernah menghasilkan algoritma klasiknya jika mereka tidak menerbitkan kuantum mereka, ”kata Aaronson.