Czy komputery kwantowe rozwiążą szachy?

18

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?

MikhailTal
źródło
10
„Ale teraz komputery kwantowe będą wkrótce dostępne” Źródło na ten temat?
Cleveland
5
Jako student fizyki zapewniam, że komputery kwantowe nie zostaną wkrótce wykorzystane do gry w szachy .
Danu,
3
@Spork, możesz powiedzieć to samo o „Mój przyjaciel pokazał mi artykuł”
Cleveland
3
@Cleveland, że jedno jest tak oczywiste, wątpię, aby wielu ludzi w to uwierzyło. Przyjaciel prawdopodobnie i tak mówił o grach Xbox na 2015 rok neowin.net/news/…
Spork
3
Komputer kwantowy nie działa, przechowując klasyczną informację o wartości 2 ^ n bitów w n kubitach i wykorzystując ją tak, jak zrobiłby to klasyczny komputer.
JiK,

Odpowiedzi:

24

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ę:

NN - NN

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.

David Richerby
źródło
1
Nie odłożyłbym tego od obliczeń kwantowych ... widzieliśmy duży postęp w innych problemach związanych z wyszukiwaniem grafów, takich jak używanie kwantowania do rozwiązania problemu podróżnego sprzedawcy. Może jakaś sprytna osoba może wymyślić, jak zrobić coś podobnego w szachach? gizmag.com/d-wave-quantum-computer-supercomputer-ranking/27476
tbischel
2
@tbischel Ale szachy, wyszukiwanie drzewa przeciwnika, wcale nie wygląda jak TSP, który jest kolejnym problemem związanym ze stosem siana. Należy również zauważyć, że twierdzenia DWave są, powiedzmy, dość kontrowersyjne . Istnieją co najmniej dwie grupy, które napisały symulacje wyżarzania kwantowego, które przewyższają DWave, na przykład na zwykłym laptopie.
David Richerby
2
Nie przeczę, że obecnie nie istnieje kwantowy odpowiednik wyszukiwania alfa-beta ... ale biorąc pod uwagę, że algorytmy obliczeń kwantowych są jeszcze w powijakach, to nie znaczy, że nigdy nie będą. Na przykład: web.ist.utl.pt/luis.tarrataca/publications/... Co do DWave, dostrzegam kontrowersje, ponieważ ich model obliczeń kwantowych różni się od standardowych modeli ... Podchodziłbym do nich ostrożnie, chociaż tak jest mają klientów takich jak Google, NASA i NSA.
tbischel
Czy kwantowe wyżarzanie nie rozwiązałoby szachów?
Behrang Saeedzadeh
-1

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ę?

użytkownik21914
źródło
-3

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 20J) 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 36 , który jest bliski 2 122 .

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 138w 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 64 = 196053476430761073330659760423566015424403280004115787589590963842248961.

To około 2 x 10 71 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 32 = 442779263776840698304313192148785281,

lub około 5 x 10 35 . 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 32 jest za duży ...

Ta najmniejsza liczba kończy się na około 2 120 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 126 do 2 130 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.

Jonathan Garber
źródło
1
Komputery kwantowe nie mają żadnych problemów z pojemnością. Rzecz 2 ^ n vs n, więc 2 ^ 120 pozycji w ciągu 64-bajtowym to 2 ^ 126 pozycji lub 2 ^ 129. komputer kwantowy potrzebuje tylko 129 cząstek kwanty (teoretycznie). Ponieważ do tego czasu będziemy dysponować technologią obliczeń kwantowych, prawdopodobnie obliczenia nie zajmą wszystkich zasobów planetarnych ani całej przestrzeni planetarnej. Komputer, który może to zrobić, prawdopodobnie nie będzie większy niż duży pokój.
MikhailTal,
1
Wydaje się, że może to być nieporozumienie dotyczące działania komputerów kwantowych. Jak rozumiem, qbity reprezentują superpozycję wszystkich stanów, w których pojedyncze obliczenie (przejście bramki odczytu) działa na wszystkie stany jednocześnie, zwracając wynik probabilistycznie. Powyższy argument dotyczy bardziej tradycyjnych paradygmatów CMOS.
tbischel,
Myślę, że prawdziwym pytaniem jest, czy przeszukiwanie grafów pasuje do paradygmatu obliczeń kwantowych ... Słyszałem, że istnieją dobre wyniki w rozwiązaniu problemu podróżnego sprzedawcy z komputerami kwantowymi, więc może jest takie podejście
tbischel
2
@JonathanGarber Jak zdobyć 2 ^ 126 lub 2 ^ 130? I nie rozumiem, w jaki sposób bramki CMOS są powiązane z szacowaniem wymagań energetycznych komputera kwantowego.
JiK,
3
Ta odpowiedź jest zasadniczo błędna, ponieważ dotyczy wyłącznie klasycznych komputerów, a pytanie dotyczy komputerów kwantowych.
David Richerby