Yapay zekâ 19 yıllık kuantum sanısını 3 günde çözdü, ispatı Lean doğruladı

Kuantum hesaplamanın yaklaşık 19 yıldır çözülemeyen sorularından biri bir yapay zekâ sistemiyle yanıt buldu. Physical Superintelligence (PSI) şirketinin açıklamasına göre Anthropic'in kamuya açık olmayan bir modelini kullanan araştırma sistemi, Aaronson-Ambainis sanısının tam ispatını üç gün içinde ortaya koydu. İspatın her adımı, matematiksel ispatları bilgisayarla denetleyen Lean ispat asistanı tarafından biçimsel olarak doğrulandı.

Kuantum hızlanmasının sınırı

Quantum Zeitgeist'in aktardığına göre ispat, rastgele girdiler üzerinde kuantum hızlanmasının sınırına dair temel bir soruyu kapatıyor. Sonuca göre evet ya da hayır yanıtı veren sorularda kuantum bilgisayarlar, sıradan bilgisayarlardan en fazla polinom ölçüsünde daha hızlı olabiliyor. Girdi nadir ve özel bir örüntü taşımadığı sürece üstel bir hız avantajı mümkün görünmüyor.

Bu, kuantum bilgisayarların bazı problemleri daha hızlı çözemeyeceği anlamına gelmiyor. Sonuç, hızlanmanın hangi koşullarda mümkün olduğunu netleştiriyor ve bu sınırları anlamak için sağlam bir matematiksel çerçeve sunuyor.

Bir kadran ve açık-kapalı anahtarlar

İspatın merkezinde, girdideki her bir bitin sonucu ne kadar etkilediğini ölçen "etki" kavramı var. Araştırmacılar bunu açık-kapalı anahtarlara bağlı bir kadran olarak düşünüyor. Kadranın değeri her zaman sıfır ile bir arasında kalıyor ve tek bir bitin değiştirilmesi kadranı ortalama olarak ne kadar oynattığı o bitin etkisini veriyor.

Sistem, sıradan bir bilgisayarın en etkili bitlere odaklanarak kuantum bilgisayarın çıktısını küçük bir hata payıyla tahmin edebileceğini gösterdi. Bunu yaparken gereken adım sayısı üstel değil, polinom ölçüsünde artıyor. Kritik adımda sistem, Shachar Lovett ve Jiapeng Zhang'ın önceki çalışmasından yararlanarak daha önce varsayılan bir eşitsizliğin yerine makalede kanıtlanan yeni bir eşitsizlik koydu.

"Neredeyse büyülü bir biçimde"

Stanford Üniversitesi'nden Guy Blanc, sonucun kuantum hızlanmasına izin veren problemlerin doğası açısından önemli sonuçları olan, on yıllardır süren bir sanıyı çözdüğünü söyledi. Blanc'a göre ispat, Boole fonksiyonlarının analizi ve olasılıksal kombinatorikteki pek çok çalışma hattını "neredeyse büyülü bir biçimde" bir araya getiriyor.

PSI sistemi ilk ispatı çalışmanın üçüncü gününde tamamladı ve ardından ispatı iki kez daha iyileştirdi. Her iki iyileştirme de Lean tarafından kabul edildi. Şirket ekibi şimdi ilgili diğer açık problemler üzerinde çalışıyor.