Physical Superintelligence (PSI) julkaisi 6. marraskuuta verkkosivuillaan tiedotteen ja GitHub-repositoriossaan käsikirjoituksen. Niiden mukaan Scott Aaronsonin ja Andris Ambainisin konjektuuri on todistettu. PSI:n mukaan konjektuuri oli ollut ratkaisematta vuodesta 2008.

Käsikirjoituksen mukaan tekoälymallit tuottivat sen matemaattiset väitteet. PSI:n David Turturean rajasi ongelman ja rakensi harnessin eli ohjelman, joka antaa mallille työkalut ja ajaa sen työvaiheet. Harnessissa toimi useita Anthropicin julkaisemattoman mallin instansseja. Ne etsivät aiempia ideoita, ehdottivat ja testasivat uusia ja valvoivat muiden instanssien työtä. PSI:n mukaan todistus oli valmis ajon kolmantena päivänä.

Myös käsikirjoituksen ensimmäisen luonnoksen kirjoitti malli. Turturean kertoo tarkastaneensa ja muokanneensa luonnoksen ja vastaavansa sen oikeellisuudesta.

Mitä tulos sanoo kvanttitietokoneista

Syöte on pitkä nollien ja ykkösten jono. Kyselymallissa lasketaan, montako kertaa algoritmi lukee sitä. Aiemmin tiedettiin, että T kyselyn jälkeen kvanttialgoritmin todennäköisyys vastata ”kyllä” on syötteen biteistä riippuva polynomi. Polynomin aste on enintään 2T ja arvot nollan ja yhden välillä.

Konjektuurin mukaan tällaisessa polynomissa on vaikutusvaltainen bitti, jos polynomin arvo ei ole vakio. Bitin vaikutus (influence) on polynomin arvon muutoksen neliön keskiarvo kaikilla syötteillä, kun bitti käännetään. Käsikirjoituksen mukaan jonkin bitin vaikutus on vähintään (ε/d)⁷, kun d on polynomin aste ja ε sen varianssin alaraja. Aiemmat yleiset alarajat heikkenivät eksponentiaalisesti asteen kasvaessa.

Aaronsonin ja Ambainisin aiemman tuloksen mukaan tavallinen algoritmi voi siten lukea vaikutusvaltaisia bittejä yksi kerrallaan. Käsikirjoituksen mukaan se arvioi enintään (4T)⁸ ε⁻¹⁴ δ⁻⁸ kyselyllä kvanttialgoritmin kyllä-todennäköisyyden enintään ε:n virheellä kaikilla syötteillä paitsi δ-osuudella. Kyselyjen määrä kasvaa polynomisesti eikä eksponentiaalisesti.

Tulos ei koske rakenteellisia syötteitä. Käsikirjoituksen mukaan polynomista suurempi kvanttinopeutus kyselymallissa vaatii rakennetta, esimerkiksi takuun siitä, millainen syöte on. PSI:n mukaan esimerkiksi Shorin tekijöihinjakoalgoritmi nojaa tällaiseen rakenteeseen.

Todistus ja sen tarkistus

Todistus noudattaa Shachar Lovettin ja Jiapeng Zhangin suunnitelmaa, mutta korvaa heidän konjektuuriksi jättämänsä epäyhtälön uudella. Uuden epäyhtälön todistus parittaa syötteet yksi yhteen determinantin avulla.

Käsikirjoituksen mukaan päälause ja sen seurauslause on formalisoitu Lean-todistusavustajassa, ja Leanin ydin on hyväksynyt ne. Formalisointi on PSI:n repositoriossa. Todistuksen tarkasti PSI:n neuvonantaja Jim Halverson.

Stanfordin yliopiston Guy Blanc, Jordan Docter, Carmen Strassle ja Li-Yang Tan todistivat elokuussa konjektuurin seurauksen erikoistapauksessa, jossa kvanttialgoritmi lukee syötettään kiinteän määrän rinnakkaisia kierroksia. PSI:n mukaan he ovat lukeneet todistusta ja kirjoittavat siitä lyhyempää esitystä asiantuntijoille. PSI:n sivulla julkaistussa viestissä he kirjoittavat: ”Tämä on valtava tulos. Se ratkaisee vuosikymmeniä vanhan konjektuurin, jolla on tärkeitä seurauksia sille, millaisissa ongelmissa kvanttinopeutus on mahdollinen.”

Kyse on yhtiön itse julkaisemasta käsikirjoituksesta. Vertaisarvioinnista lähteissä ei kerrota.