Americký startup Physical Superintelligence (PSI) 6. listopadu oznámil, že jeho výzkumný systém dokázal jednu z dlouho otevřených domněnek teoretické informatiky – Aaronsonovu–Ambainisovu domněnku. Podle firmy na důkaz přišly instance neveřejného modelu společnosti Anthropic běžící v interním „výzkumném postroji“, který vyvinul David Turturean. Kompletní důkaz měl systém k dispozici třetí den běhu a automatický dokazovač Lean ho přijal. Celý balík – článek i formalizaci – PSI zveřejnila v repozitáři na GitHubu.
O čem domněnka je
Kvantové počítače jsou slavné tím, že některé úlohy zvládnou nesrovnatelně rychleji než klasické stroje. Nejznámější příklad, Shorův algoritmus na rozklad čísel z roku 1994, ale těží ze skryté struktury úlohy. Scott Aaronson a Andris Ambainis se ptali, co se stane, když žádná taková struktura není – tedy když kvantový počítač dostane obecný, náhodný vstup. Ukázali, že pokud platí jejich domněnka, kvantový počítač může být na náhodných vstupech rychlejší jen polynomiálně, nikoli exponenciálně.
Samotná domněnka je čistě matematická. Pravděpodobnost, že kvantový algoritmus odpoví „ano“, se dá zapsat jako polynom ve vstupních bitech. Tvrzení zní, že každý takový omezený polynom nízkého stupně, který není konstantní, má alespoň jeden bit se znatelným „vlivem“ – jeho překlopení tedy v průměru výrazně změní výsledek. Prakticky to znamená, že obyčejný počítač dokáže odpověď kvantového stroje napodobit pro naprostou většinu vstupů s rozumným počtem nahlédnutí do dat.
Jak AI postupovala
Podle repozitáře důkaz sleduje plán, který v roce 2023 navrhli Shachar Lovett a Jiapeng Zhang a v němž zůstala jedna nerovnost nedokázaná. Systém PSI ji nahradil novou nerovností a odvodil explicitní dolní mez vlivu, zhruba (ε/d)^7. Server OfficeChai uvádí, že dosavadní meze pro obecné polynomy klesaly se stupněm exponenciálně. Po prvním úspěchu PSI nasměrovala systém na příbuzné otevřené problémy a výsledek se podle firmy podařilo dvakrát zlepšit.
Turturean podle PSI problém vybral, systém spustil a nechal model připravit první verzi článku, kterou pak zrevidoval. Jako poradci se zapojili Jim Halverson, který důkaz auditoval, a Phiala Shanahanová, jež komentovala formalizaci. PSI, sídlící v Cambridgi ve státě Massachusetts, se představila letos v září se seedovým kolem 58 milionů dolarů od Breakthrough Energy Ventures.
Co Lean zaručuje – a co ne
Formální ověření v Leanu je silná záruka: každý logický krok kontroluje stroj. Repozitář ale sám upozorňuje, že čtenář musí ověřit, zda formální zadání skutečně odpovídá původní domněnce, a že textová část článku strojově kontrolovaná není. Výsledek zatím neprošel recenzí a veřejně se k němu nevyjádřili ani Aaronson, ani Ambainis. Skupina Guy Blanc, Jordan Docter, Carmen Strassleová a Li-Yang Tan, která letos v srpnu vyřešila speciální případ, podle OfficeChai důkaz čte a připravuje jeho kratší výklad pro odborníky.
Je to obrovský výsledek.— Blanc, Docter, Strassleová a Tan podle OfficeChai
Přesah
Komu patří objev, který nikdo nevymyslel?
Matematika byla dlouho poslední baštou čistě lidského porozumění. Důkaz nebyl jen řetězec správných kroků, ale i vhled – chvíle, kdy někdo uvidí, proč věci drží pohromadě. Když důkaz najde stroj a jiný stroj ho zkontroluje, zůstává ten vhled vůbec někde? Nebo se z porozumění stává až dodatečná práce lidí, kteří po AI „čtou a vykládají“?
Zajímavé je, že odpovědnost tu zůstává lidská: za správnost článku ručí konkrétní výzkumník. Připomíná to starou Turingovu otázku obrácenou naruby – už neřešíme, zda stroj umí myslet, ale co přesně ještě znamená, že člověk něčemu rozumí. Možná se matematik budoucnosti bude podobat spíš kurátorovi a překladateli než osamělému hledači. A možná právě to, co nedokáže delegovat – volba otázek, které stojí za to klást – bude nejcennější částí jeho řemesla.
Zdroje
- A proof of the Aaronson-Ambainis conjecture (repozitář a Lean formalizace) · GitHub / Physical Superintelligence
- US Startup Physical Superintelligence Proves Aaronson-Ambainis Conjecture · OfficeChai
- Physical Superintelligence says its AI system proved the Aaronson-Ambainis conjecture · RuntimeWire
Tento článek napsal AI redaktor Noumo vlastními slovy na základě uvedených zdrojů. Může obsahovat nepřesnosti — fakta si ověř u originálu.
