Bukti baru yang mencolok dalam kompleksitas komputasi kuantum mungkin paling baik dipahami dengan eksperimen pemikiran yang menyenangkan. Jalankan bak mandi, lalu buang banyak magnet batang mengambang ke dalam air. Setiap magnet akan membalik orientasinya maju mundur, mencoba menyelaraskan dengan tetangganya. Ini akan mendorong dan menarik magnet lainnya dan didorong dan ditarik kembali. Sekarang coba jawab ini: Apa yang akan menjadi pengaturan akhir sistem?
Masalah ini dan masalah lain seperti itu, ternyata, sangat rumit. Dengan sesuatu yang lebih dari beberapa ratus magnet, simulasi komputer akan memakan waktu yang tidak masuk akal untuk memberikan jawabannya.
Sekarang buat magnet itu kuantum — atom individu tunduk pada aturan Bizantium dunia kuantum. Seperti yang Anda duga, masalahnya semakin sulit. "Interaksi menjadi lebih rumit," kata Henry Yuen dari Universitas Columbia. "Ada batasan yang lebih rumit ketika dua 'magnet kuantum' yang berdekatan bahagia."
Sistem yang tampak sederhana ini telah memberikan wawasan luar biasa tentang batas komputasi, baik dalam versi klasik maupun kuantum. Dalam kasus sistem klasik atau non-kuantum, a teorema tengara dari ilmu komputer membawa kita lebih jauh. Disebut teorema PCP (untuk "bukti yang dapat diperiksa secara probabilistik"), ia mengatakan bahwa tidak hanya keadaan akhir magnet (atau aspek yang terkait dengannya) yang sangat sulit untuk dihitung, tetapi juga banyak langkah yang mengarah ke sana. Kompleksitas situasi bahkan lebih drastis, dengan kata lain, dengan keadaan akhir yang dikelilingi oleh zona misterius.
Versi lain dari teorema PCP, yang belum terbukti, secara khusus membahas kasus kuantum. Ilmuwan komputer menduga bahwa dugaan PCP kuantum itu benar, dan membuktikannya akan mengubah pemahaman kita tentang kompleksitas masalah kuantum. Ini dianggap sebagai masalah terbuka paling penting dalam teori kompleksitas komputasi kuantum. Namun sampai saat ini masih belum terjangkau.
Sembilan tahun lalu, dua peneliti mengidentifikasi tujuan antara untuk membantu kami sampai di sana. Mereka datang dengan hipotesis yang lebih sederhana, yang dikenal sebagai dugaan “tidak ada keadaan sepele berenergi rendah” (NLTS), yang harus benar jika dugaan PCP kuantum benar. Membuktikannya tidak serta merta membuatnya lebih mudah untuk membuktikan dugaan PCP kuantum, tetapi itu akan menyelesaikan beberapa pertanyaannya yang paling menarik.
Kemudian bulan lalu, tiga ilmuwan komputer membuktikan dugaan NLTS. Hasilnya memiliki implikasi yang mencolok untuk ilmu komputer dan fisika kuantum.
"Ini sangat menarik," kata Dorit Aharonov dari Universitas Ibrani Yerusalem. “Ini akan mendorong orang untuk melihat masalah yang lebih sulit dari dugaan PCP kuantum.”
Untuk memahami hasil baru, mulailah dengan membayangkan sistem kuantum seperti sekumpulan atom. Setiap atom memiliki sifat, yang disebut spin, yang agak mirip dengan pelurusan magnet, dalam hal itu menunjuk sepanjang sumbu. Tapi tidak seperti pelurusan magnet, spin atom bisa dalam keadaan campuran simultan dari arah yang berbeda, sebuah fenomena yang dikenal sebagai superposisi. Lebih lanjut, mungkin tidak mungkin untuk menggambarkan spin satu atom tanpa memperhitungkan spin atom lain dari daerah yang jauh. Ketika ini terjadi, atom-atom yang saling terkait itu dikatakan berada dalam keadaan belitan kuantum. Keterikatan luar biasa, tetapi juga rapuh dan mudah terganggu oleh interaksi termal. Semakin banyak panas dalam suatu sistem, semakin sulit untuk menjeratnya.
Sekarang bayangkan mendinginkan sekelompok atom sampai mendekati nol mutlak. Saat sistem menjadi lebih dingin dan pola keterikatan menjadi lebih stabil, energinya berkurang. Energi serendah mungkin, atau "energi tanah", memberikan deskripsi singkat tentang keadaan akhir yang rumit dari keseluruhan sistem. Atau setidaknya bisa, jika bisa dihitung.
Dimulai pada akhir 1990-an, para peneliti menemukan bahwa untuk sistem tertentu, energi tanah ini tidak akan pernah dapat dihitung dalam kerangka waktu yang wajar.
Namun, fisikawan berpikir bahwa tingkat energi yang dekat dengan energi dasar (tetapi tidak cukup sampai di sana) seharusnya lebih mudah untuk dihitung, karena sistemnya akan lebih hangat dan tidak terlalu terikat, dan karena itu lebih sederhana.
Ilmuwan komputer tidak setuju. Menurut teorema PCP klasik, energi yang mendekati keadaan akhir sama sulitnya untuk dihitung seperti energi akhir itu sendiri. Jadi versi kuantum dari teorema PCP, jika benar, akan mengatakan bahwa energi pendahulu energi dasar akan sama sulitnya untuk dihitung seperti energi dasar. Karena teorema PCP klasik benar, banyak peneliti berpikir versi kuantum juga benar. “Tentunya, versi kuantum pasti benar,” kata Yuen.
Implikasi fisik dari teorema semacam itu akan sangat mendalam. Ini berarti bahwa ada sistem kuantum yang mempertahankan keterjeratannya pada suhu yang lebih tinggi — benar-benar bertentangan dengan harapan fisikawan. Tetapi tidak ada yang bisa membuktikan bahwa sistem seperti itu ada.
Pada tahun 2013, Michael Freedman dan Matthew Hastings, keduanya bekerja di Microsoft Research's Station Q di Santa Barbara, California, mempersempit masalah. Mereka memutuskan untuk mencari sistem yang energi terendah dan hampir terendahnya sulit dihitung berdasarkan hanya satu metrik: jumlah sirkuit yang diperlukan komputer untuk mensimulasikannya. Sistem kuantum ini, jika mereka dapat menemukannya, harus mempertahankan pola keterjeratan yang kaya pada semua energi terendahnya. Keberadaan sistem seperti itu tidak akan membuktikan dugaan PCP kuantum — mungkin ada metrik kekerasan lain yang perlu dipertimbangkan — tetapi itu akan dianggap sebagai kemajuan.
Ilmuwan komputer tidak mengetahui sistem seperti itu, tetapi mereka tahu ke mana harus mencarinya: di bidang studi yang disebut koreksi kesalahan kuantum, di mana para peneliti membuat resep keterjeratan yang dirancang untuk melindungi atom dari gangguan. Setiap resep dikenal sebagai kode, dan ada banyak kode baik yang lebih besar maupun lebih kecil.
Pada akhir tahun 2021, para ilmuwan komputer membuat terobosan besar dalam menciptakan kode koreksi kesalahan kuantum yang pada dasarnya bersifat ideal. Selama bulan-bulan berikutnya, beberapa kelompok peneliti lain membangun hasil tersebut untuk membuat versi yang berbeda.
Tiga penulis makalah baru, yang telah berkolaborasi dalam proyek terkait selama dua tahun terakhir, berkumpul untuk membuktikan bahwa salah satu kode baru memiliki semua properti yang diperlukan untuk membuat sistem kuantum seperti yang dihipotesiskan Freedman dan Hastings. . Dengan melakukan itu, mereka membuktikan dugaan NLTS.
Hasil mereka menunjukkan bahwa keterjeratan tidak selalu rapuh dan sensitif terhadap suhu seperti yang dipikirkan fisikawan. Dan itu mendukung dugaan PCP kuantum, menunjukkan bahwa bahkan jauh dari energi dasar, energi sistem kuantum dapat tetap hampir mustahil untuk dihitung.
"Ini memberitahu kita bahwa hal yang tampaknya tidak mungkin benar itu benar," kata Ishak Kim dari Universitas California, Davis. “Meskipun dalam sistem yang sangat aneh.”
Para peneliti percaya bahwa alat teknis yang berbeda akan diperlukan untuk membuktikan dugaan PCP kuantum penuh. Namun, mereka melihat alasan untuk optimis bahwa hasil saat ini akan membawa mereka lebih dekat.
Mereka mungkin paling tertarik dengan apakah sistem kuantum NLTS yang baru ditemukan — meskipun secara teori mungkin — benar-benar dapat dibuat di alam, dan seperti apa bentuknya. Menurut hasil saat ini, mereka akan membutuhkan pola rumit dari keterjeratan jarak jauh yang belum pernah diproduksi di laboratorium, dan yang hanya dapat dibangun menggunakan jumlah atom yang sangat banyak.
"Ini adalah objek yang sangat direkayasa," kata Chinmay Nirkhe, seorang ilmuwan komputer di University of California, Berkeley, dan rekan penulis makalah baru bersama dengan Anurag Anshu dari Universitas Harvard dan Nikolas Breukmann dari Universitas College London.
“Jika Anda memiliki kemampuan untuk memasangkan qubit yang sangat jauh, saya yakin Anda dapat mewujudkan sistemnya,” kata Anshu. "Tapi ada perjalanan lain yang harus dilakukan untuk benar-benar pergi ke spektrum energi rendah." Breuckmann menambahkan, “Mungkin ada bagian dari alam semesta yang NLTS. Aku tidak tahu."
