SI udowodniła hipotezę Aaronsona-Ambainisa: komputery kwantowe są ograniczone w zadaniach bez struktury

Edytowane przez: Svitlana Velhush

Komputer kwantowy nie zdoła wykładniczo wyprzedzić zwykłego przy rozwiązywaniu zadań, w których dane wejściowe są niemal losowe i pozbawione szczególnej struktury matematycznej. To nie jest zwyczajne kolejne ograniczenie — to dowód uzyskany przez sztuczną inteligencję.

W listopadzie 2026 roku startup Physical Superintelligence (PSI) w USA ogłosił dowód hipotezy, którą w 2011 roku sformułowali Scott Aaronson z Uniwersytetu Teksańskiego w Austin i Andris Ambainis z Uniwersytetu Łotwy. Hipoteza głosiła: dla wielomianów niskiego stopnia przyjmujących wartości od 0 do 1 na sześcianie Boole'a zawsze znajdzie się zmienna o zauważalnym wpływie. Dowód znalazł wewnętrzny system badawczy PSI oparty na niepublicznym modelu Anthropic. Pełny tekst przeszedł weryfikację w systemie Lean, a ekspozycję przygotowali badacze ze Stanford — Guy Blank, Jordan Docter, Carmen Strassl i Li-Yang Tan.

System działał przez cztery dni: najpierw uzyskał pełny dowód, następnie dwukrotnie go ulepszył, a każdy wariant Lean przyjął bez błędów. To nie eksperyment na procesorze kwantowym, lecz czysto matematyczny dowód w dziedzinie teorii złożoności zapytań. Pokazuje, że algorytm kwantowy wykonujący T zapytań do wejścia można z wysoką dokładnością zasymulować klasycznie na większości losowych wejść, zużywając jedynie wielomianową liczbę zapytań.

Wyobraźcie sobie ogromny magazyn z miliardami skrzyń, w którym potrzebny przedmiot leży w losowym miejscu bez podpowiedzi. Klasyczne przeszukiwanie przegląda skrzynie jedną po drugiej. Kwantowe mogłoby, jak się zdawało, zajrzeć do wszystkich naraz — ale dowód pokazuje, że bez szczególnej struktury, jak w algorytmie Shora do faktoryzacji, takie „zaglądanie” daje jedynie wielomianowe przyspieszenie, a nie wykładnicze. Wpływ jednej zmiennej w wielomianie gwarantuje, że losowe wejście niemal zawsze można przewidzieć na podstawie niewielkiej liczby bitów.

Wynik zmienia wyobrażenia o granicach przewagi kwantowej. Teraz jest jasne: dla zadań bez wbudowanej struktury — losowych grafów, losowych funkcji — nie należy oczekiwać wykładniczej korzyści. Komputery kwantowe zachowują przewagę tam, gdzie struktura istnieje, jak w kryptografii lub optymalizacji o szczególnych właściwościach. Praktycznej budowy urządzeń to nie przekreśla, ale kieruje wysiłki na poszukiwanie właśnie takich ustrukturyzowanych zadań.

Artykuł w New Scientist z 12 listopada 2026 roku i preprint na arXiv z 8 listopada szczegółowo opisują przebieg dowodu i jego konsekwencje dla relacji klas BPP i BQP w świecie losowych wyroczni.

Przewaga kwantowa jest teraz wyraźniej zarysowana: jest realna, ale wymaga nie przypadkowości, lecz ukrytej prawidłowości.

3 Wyświetlenia

Źródła

  • AI confirms a long-suspected limit on quantum computers’ advantages

  • psi.inc

  • arxiv.org

Komentarze

Czy znalazłeś błąd lub niedokładność?Rozważymy Twoje uwagi tak szybko, jak to możliwe.