Czy komputery kwantowe rozwiążą szachy?

Teoria jest taka, że ​​istnieje ponad 10 ^ 40 pozycji, a komputer działający w skali atomowej musi być niemożliwie duży (jak w dużej skali galaktycznej) i znacznie przekraczać nasz obecny poziom wiedzy.

Ale teraz komputery kwantowe będą wkrótce dostępne. Ten komputer może mieć 2 ^ n zamiast n bajtów miejsca z powodu stanów kwantowych. Czy to nowe duże miejsce na stoliki zostanie rozwiązane? Oczywiście będzie to wymagało więcej przełomów w przyszłości, ale czy w kolejnych latach zobaczymy 8-częściowe bazy danych?

Wiele pytań o możliwość rozwiązania szachów dotyczy tego, że nie mamy wystarczającej ilości miejsca na komputer, aby je wypełnić. Czy komputery kwantowe zmienią status quo?

Nie jestem ekspertem w dziedzinie obliczeń kwantowych, ale rozumiem, że komputery kwantowe nie powinny być przydatne w szachach.

Algorytmy kwantowe są bardzo dobre na znalezienie igły w stogi: trzy duże algorytmy kwantowe są algorytm faktoryzacji shor za , algorytm przeszukiwania bazy danych Grovera i algorytm Deutsch-Jozsa, który zasadniczo określa, czy długa lista liczb zawiera albo wszystkie zera, wszystkie jedynki, czy ich połowę. Wszystkie te problemy można postrzegać jako przykłady „Ukryłem coś: musisz to szybko znaleźć”. Podczas faktoryzacji „ukryłem” czynniki pierwsze i musisz je znaleźć; w wyszukiwaniu bazy danych ukryłem wpis z danym kluczem w dużej nieposortowanej tabeli i musisz go znaleźć; w problemie rozwiązanym przez Deutscha-Jozsę mógłbym umieścić dużą liczbę zer w tabeli jedynek, ale przy klasycznym algorytmie, gdy spojrzałeś na połowę tabeli i zobaczyłeś tylko te, mógłbyś mieć pecha i spojrzał na „niewłaściwą” połowę. Zauważ też, że wszystkie te problemy mogą być szybko rozwiązane przez nierealistycznie równoległy klasyczny komputer: możesz wypróbować wszystkie czynniki równolegle,

Rozwiązywanie szachów nie przypomina nawet żadnego z tych problemów. Jest to zasadniczo sekwencyjne działanie. To, czy mój ruch jest dobry, zależy od tego, co zrobisz w odpowiedzi. To, czy twoja odpowiedź będzie dobra, zależy od tego, co zrobię w odpowiedzi. I tak dalej. Możesz sobie wyobrazić, że możesz wykonać pierwszą warstwę wyszukiwania, przyjmując superpozycję możliwych ruchów. Ale co robisz na drugiej warstwie? Nie możesz po prostu nałożyć superpozycji wszystkich pozycji, w których moglibyśmy być po dwóch warstwach, ponieważ to zapomniało o strukturze drzewa. Rozważmy na przykład tę bardzo sztuczną pozycję, z białą do poruszania się:

Jeśli zapomnimy o strukturze drzewa, czarny jest bardzo szczęśliwy. Mówi: „W dwóch warstwach najlepszą pozycją, w jakiej mogę być, jest dostarczenie mat! To prawda, ale oczywiście białe nigdy na to nie pozwolą, ponieważ najlepszym ruchem białych jest taki, który uniemożliwia czarnemu matowanie (lub robienie czegokolwiek innego). Szachy nie polegają na ustaleniu najlepszego ruchu, jaki możesz wykonać w warstwie N: chodzi o ustalenie najlepszego ruchu, który przeciwnik pozwoli ci grać w warstwie N. Komputery kwantowe nie wydają się być dobre w tym rozumowaniu typu „daj i bierz”. Nie wiemy nawet, jak rozwiązać szachy za pomocą nierealistycznie równoległego klasycznego komputera.

Należy ją zwerbalizować, co dokładnie oznacza „rozwiązanie szachów”.
Wtedy zrozumiemy, co dokładnie możemy wydostać z hipotetycznego solvera szachowego czarnej skrzynki (BBCS).
Będziemy karmić BBCS pozycją szachownicy.
BBCS wypluje liczbę całkowitą X. 0 oznacza, że ​​nie ma rozwiązania dla tej pozycji (lub sama pozycja jest nieprawidłowa) Inna liczba całkowita oznacza najmniejszą liczbę ruchów w celu przekształcenia pierwotnej pozycji w pozycję mat w pozycji niewspółpracującej gra w szachy. Ostatecznym rozwiązaniem dla szachów będzie tylko liczba całkowita, co oznacza dokładną liczbę ruchów od początkowej pozycji szachowej do pozycji szachowej. Czy to zadanie dla komputera kwantowego? NIE WIEM. Jak wyszukuje David Richerby - szachy nie są przeznaczone do kontroli jakości. Ale kiedy musimy znaleźć pojedynczą liczbę całkowitą X, aby zadeklarować „wiązanie w ruchach X”, bardziej przypomina znalezienie igły w stogu siana ... Czy się mylę?

Uczciwe ostrzeżenie: ta odpowiedź zawiera liczby spekulatywne i może być wyłączona z powodu rzędów wielkości.

Jest to po prostu możliwe, ale mało prawdopodobne.

Problem niekoniecznie polega na tym, czy komputery kwantowe będą w stanie „równolegle” do tego stopnia, czy nie. Problem polega na prostej fizyce, której nawet komputery kwantowe nie mogą realistycznie obejść. Mówiąc prosto, istnieje ograniczona liczba obliczeń, które można kiedykolwiek wykonać. Zostało to odebrane przez Thomasa Pornin na Security.SE, cytuję niektóre jego odpowiedź tutaj:

Spójrzmy na bardziej przyziemną perspektywę. Wydaje się słuszne założyć, że przy istniejącej technologii każda elementarna operacja musi w jakiś sposób oznaczać przełączenie przynajmniej jednej bramki logicznej. Moc przełączania pojedynczej bramki CMOS wynosi około C * V ^2, gdzie C jest pojemnością obciążenia bramki, a V jest napięciem, przy którym brama działa. Począwszy od 2011 roku, brama bardzo high-end będzie mógł działać przy napięciu 0,5 V i pojemności ładunkowej kilku femtofarads ( „femto”, czyli „10 ^-15 ”). Prowadzi to do minimum zużycia energii na działanie nie mniej niż, powiedzmy, 10 ^-15 J. prąd całkowite zużycie energii na świecie około 500 EJ (5 * 10 ²⁰J) rocznie (tak mówi ten artykuł ). Zakładając, że całkowita produkcja energii na Ziemi jest przekazywana do jednego obliczenia na dziesięć lat, otrzymujemy limit 5 * 10 ³⁶ , który jest bliski 2 ¹²² .

Następnie należy wziąć pod uwagę postęp technologiczny. Biorąc pod uwagę obecną tendencję w kwestiach ekologicznych i szczytową ropę naftową , całkowita produkcja energii nie powinna znacznie wzrosnąć w nadchodzących latach (powiedz nie więcej niż 2 razy do roku 2040 - już koszmar ekologiczny). Z drugiej strony postęp technologiczny w projektowaniu układów scalonych. Prawo Moore'a mówi, że co dwa lata można zamontować dwa razy więcej tranzystorów na danej powierzchni układu. Bardzo optymistyczny pogląd, że to podwojenie liczby tranzystorów może być wykonane przy stałym zużyciu energii, co przekłada się na zmniejszenie o połowę kosztów energii elementarnej operacji na dwa lata. Doprowadziłoby to do ogólnej liczby 2 ¹³⁸w roku 2040 - i dotyczy to jednego dziesięcioletniego obliczenia, które mobilizuje wszystkie zasoby całej planety.

Jest to absolutna maksymalna liczba podstawowych operacji, które można ewentualnie wykonać. Zobaczmy teraz, ile jest pozycji szachowych ...

Zróbmy kilka szybkich liczb. Każdy z 64 kwadratów może być pusty lub pomieścić jeden z 12 różnych elementów (R, K, B, Q, K i P w czerni i bieli), więc całkowita liczba pozycji, które można ustawić, wynosi najwyżej

13 ⁶⁴ = 196053476430761073330659760423566015424403280004115787589590963842248961.

To około 2 x 10 ⁷¹ różnych pozycji. Oczywiście jest to ogromne przeszacowanie, ponieważ większość pozycji jest fałszywa (powinniśmy eliminować pozycje z trzema lub więcej królami, dziewięcioma lub więcej białymi pionkami, pionkami ósmej rangi, poczwórnymi czekami itp.). Weźmy pierwiastek kwadratowy:

13 ³² = 442779263776840698304313192148785281,

lub około 5 x 10 ³⁵ . Przyjmując pierwiastek kwadratowy udajemy, że dla każdej legalnej pozycji istnieje wszechświat szachowy o odrębnych fałszywych pozycjach. Jest to prawdopodobnie niedoceniane, więc prawdziwa odpowiedź musi znajdować się gdzieś pomiędzy tymi dwiema liczbami. Teraz możemy śmiało powiedzieć, że komputery nie mogą zbadać każdej pozycji prawnej w rozsądnym czasie. Nawet „mały” 13 ³² jest za duży ...

Ta najmniejsza liczba kończy się na około 2 ¹²⁰ lub więcej.

Załóżmy, że reprezentujemy nasze tablice ciągiem 64-bajtowym. (Praktycznie byłoby to potraktowane trochę inaczej, ale chodźmy na razie.) Jeśli dobrze pamiętam moją matematykę, komputer kwantowy byłby w stanie to przedstawić za pomocą 8-bajtowego ciągu lub 64 bitów. To pozostawia nam w sumie od 2 ¹²⁶ do 2 ¹³⁰ podstawowych operacji, aby przechowywać każdą legalną i możliwą pozycję .

Spójrz na to przez chwilę. Nie robimy nic użytecznego z informacjami, po prostu je przechowujemy. W tym celu mobilizujemy zasoby całej planety . Nieważne, gdzie fizycznie znajduje się magazyn. Zignoruj ​​cały problem chłodzenia. Odłóż na bok kwestię transmisji danych. Odwracamy wystarczającą moc, aby oświetlić Księżyc tylko do przechowywania pozycji.

Zgodnie z najbardziej optymistycznymi oczekiwaniami komputer kwantowy może rozwiązać szachy kosztem zasobów całej planety. Realistycznie tak się nie stanie.