PSI umumkan bukti dugaan Aaronson-Ambainis yang terbuka sejak 2008, diperiksa dengan Lean
Physical Superintelligence mengumumkan pada 6 November 2026 bahwa sistem risetnya menemukan bukti dugaan Aaronson-Ambainis. Eksposisi bukti terbit di arXiv pada 10 November 2026, tetapi penilaian pakar independen masih ditunggu.
Perusahaan Physical Superintelligence (PSI) mengumumkan pada 6 November 2026 bahwa sistem riset internalnya menemukan bukti dugaan Aaronson-Ambainis, persoalan matematika yang terbuka sejak 2008. Sistem itu bekerja dengan model Anthropic yang belum dirilis publik, dan hasilnya diterima oleh Lean, perangkat lunak pembukti teorema. Pada 10 November 2026, para peneliti dari MIT dan Stanford menerbitkan eksposisi bukti tersebut di arXiv.
Apa yang dipersoalkan dugaan ini
Dugaan ini menyangkut pertanyaan apakah komputer kuantum bisa jauh lebih cepat daripada komputer biasa pada masukan acak. Menurut PSI, percepatan kuantum yang dramatis, seperti algoritma Shor, bergantung pada struktur: masukan dijanjikan memuat pola langka. Untuk string acak, yang hampir tidak pernah berpola, jawabannya belum diketahui.
Aaronson dan Ambainis merumuskan pertanyaan itu sebagai dugaan tentang polinomial. Peluang sebuah algoritma kuantum menjawab "ya" setelah sejumlah pembacaan masukan berupa polinomial berderajat paling tinggi 2T dengan nilai antara 0 dan 1. Dugaan menyatakan bahwa polinomial semacam itu selalu punya satu variabel yang pengaruhnya (influence, yaitu rata-rata perubahan nilai polinomial ketika bit tersebut dibalik) tidak terlalu kecil, sebanding dengan pangkat tetap dari rasio variansi terhadap derajat.
Batas yang dibuktikan
Dalam pengumumannya, PSI menulis bahwa untuk polinomial tak konstan, ada bit dengan pengaruh minimal sebesar c dikali v pangkat 5/2 dibagi d pangkat 6, dan nilai itu tidak kurang dari (v/d) pangkat 7. Di sini v adalah variansi dan d adalah derajat polinomial. Eksposisi arXiv memaparkan versi yang lebih lemah, yaitu Ω(Var(p)^8/d^12). Para penulisnya menyatakan sengaja tidak mengoptimalkan parameter agar gagasan kuncinya lebih mudah dilihat, sedangkan bukti asli memiliki eksponen lebih kuat, yakni Ω(Var(p)^{5/2}/d^6).
Dampaknya pada komputasi kuantum
Menurut PSI, pada pertanyaan ya atau tidak tentang string acak, komputer kuantum tidak dapat menghemat jumlah pembacaan secara eksponensial kecuali string itu berpola langka. Jumlah pembacaan yang dibutuhkan komputer klasik untuk menirunya tumbuh paling cepat sebagai pangkat tetap dari T.
Eksposisi arXiv menambahkan dua implikasi. Pertama, algoritma kuantum untuk masalah keputusan dapat disimulasikan secara klasik pada sebagian besar masukan, yang dikenal sebagai dugaan simulasi. Kedua, sebuah klaim tentang masalah BPP versus BQP menjadi tanpa syarat. Klaim itu menyangkut kemiripan status masalah tersebut pada dunia dengan oracle acak dan dunia tanpa oracle.
Cara bukti ditemukan dan diperiksa
PSI menyatakan sistemnya sudah memiliki bukti lengkap pada hari ketiga proses, dan Lean menerimanya. Lean memeriksa setiap langkah bukti secara mekanis. PSI lalu menugaskan sistem itu ke masalah terbuka terkait; hasilnya diperbaiki dua kali sebelum Lean menerima versi akhir. David Turturean memimpin pekerjaan itu dan bertanggung jawab atas kebenaran makalahnya, sementara Jim Halverson mengaudit bukti dan Phiala Shanahan mengomentari formalisasi Lean.
Menurut laporan Unite.AI, audit repositori menunjukkan pengembangan formal tidak memuat placeholder bukti maupun aksioma tambahan. Deklarasinya juga dicek ulang dengan lean4lean, implementasi independen dari pemeriksa tipe Lean.
Peran para peneliti di luar PSI
Pada Agustus 2026, Guy Blanc, Jordan Docter, Carmen Strassle, dan Li-Yang Tan telah menyelesaikan kasus khusus, yaitu algoritma kuantum yang membaca masukan dalam jumlah putaran paralel tetap. Mereka kemudian mempelajari bukti PSI dan menyusun eksposisi yang diterbitkan pada 10 November 2026. Menurut catatan penulis, mereka tidak menerima kompensasi dari Anthropic maupun PSI, dan artikel itu tidak dimaksudkan untuk terbit di konferensi atau jurnal.
Apa artinya bagi pembaca
Bagi mahasiswa dan praktisi teknik, kabar ini menunjukkan dua hal: AI mulai dipakai dalam penelitian matematika, dan pembuktian yang diverifikasi komputer menjadi cara memeriksa klaim semacam itu. Namun ada batasnya. Menurut Unite.AI, pembaca masih harus memastikan pernyataan formal di Lean cocok dengan dugaan yang tercetak, dan makalah yang bisa dibaca manusia belum diperiksa mesin. Pakar independen juga masih perlu menilai bagian di luar Lean, sehingga klaim ini belum bisa dianggap final.