Komputer kuantum tidak akan mampu melampaui komputer biasa secara eksponensial dalam menyelesaikan masalah yang data masukannya hampir acak dan tidak memiliki struktur matematis khusus. Ini bukan sekadar batasan lain — ini adalah pembuktian yang diperoleh oleh kecerdasan buatan.
Pada November 2026, startup Physical Superintelligence (PSI) di Amerika Serikat mengumumkan pembuktian sebuah hipotesis yang dirumuskan pada 2011 oleh Scott Aaronson dari Universitas Texas di Austin dan Andris Ambainis dari Universitas Latvia. Hipotesis tersebut menyatakan: untuk polinomial berderajat rendah yang bernilai dari 0 hingga 1 pada kubus Boolean, selalu terdapat variabel dengan pengaruh yang mencolok. Pembuktiannya ditemukan oleh sistem riset internal PSI yang berbasis pada model Anthropic yang tidak dipublikasikan. Teks lengkapnya telah lolos verifikasi dalam sistem Lean, dan eksposisinya disiapkan oleh para peneliti Stanford — Guy Blank, Jordan Docter, Carmen Strassl, dan Li-Yang Tan.
Sistem tersebut bekerja selama empat hari: pertama memperoleh pembuktian lengkap, lalu menyempurnakannya dua kali, dan setiap versi diterima Lean tanpa kesalahan. Ini bukan eksperimen pada prosesor kuantum, melainkan pembuktian matematis murni di bidang teori kompleksitas kueri. Pembuktian ini menunjukkan bahwa algoritma kuantum yang melakukan T kueri terhadap input dapat disimulasikan secara klasik dengan akurasi tinggi pada sebagian besar input acak, hanya dengan menggunakan jumlah kueri yang polinomial.
Bayangkan sebuah gudang raksasa berisi miliaran kotak, di mana benda yang dicari terletak di tempat acak tanpa petunjuk. Pencarian klasik memeriksa kotak satu per satu. Komputer kuantum mungkin tampak dapat mengintip semuanya sekaligus — tetapi pembuktian ini menunjukkan bahwa tanpa struktur khusus, seperti pada algoritma Shor untuk faktorisasi, "pengintipan" semacam itu hanya memberikan percepatan polinomial, bukan eksponensial. Pengaruh satu variabel dalam polinomial menjamin bahwa input acak hampir selalu dapat diprediksi dari sejumlah kecil bit.
Hasil ini mengubah pemahaman tentang batas keunggulan kuantum. Kini jelas: untuk masalah tanpa struktur bawaan — graf acak, fungsi acak — keuntungan eksponensial tidak perlu diharapkan. Komputer kuantum tetap mempertahankan keunggulannya di tempat yang memiliki struktur, seperti dalam kriptografi atau optimasi dengan sifat khusus. Hal ini tidak membatalkan pembangunan perangkat secara praktis, tetapi mengarahkan upaya pada pencarian masalah terstruktur semacam itu.
Artikel di New Scientist tertanggal 12 November 2026 dan pracetak di arXiv tertanggal 8 November menguraikan secara rinci jalannya pembuktian dan implikasinya bagi hubungan antara kelas BPP dan BQP di dunia orakel acak.
Keunggulan kuantum kini tergambar lebih jelas: ia nyata, tetapi membutuhkan bukan keacakan, melainkan pola tersembunyi.


