Algorytm kwantowy dla liczby Boga

9

Numer Boga jest najgorszym przypadku algorytmu Boga , który jest

koncepcja wywodząca się z dyskusji na temat sposobów rozwiązania zagadki Kostka Rubika, ale która może być również zastosowana w innych łamigłówkach kombinacyjnych i grach matematycznych. Odnosi się do dowolnego algorytmu, który wytwarza rozwiązanie o możliwie najmniejszej liczbie ruchów, przy czym idea polega na tym, że wszechwiedząca istota zna optymalny krok z dowolnej konfiguracji.

Obliczenie liczby Boga na 20 wymagało „35 lat bezczynności (klasycznego) czasu pracy komputera”.

Jakiego rodzaju przyspieszenie można osiągnąć dzięki podejściu kwantowemu?

meowzz
źródło
1
„Liczba Boga” dla łamigłówek kombinatorycznych jest związana ze średnicą wykresu podobnego do Cayleya, to znaczy największą najmniejszą ścieżką na wykresie. Nie sądzę, aby ogólny problem zagadek w . Nie studiowałem tego artykułu - arxiv.org/abs/quant-ph/0303131 - ale myślę, że twierdzi on przyspieszenie Grovera nad klasycznym. n×n×nNP
Mark S
1
Możesz zadać takie pytanie dla wszystkiego, co jest trudne do obliczenia. Nie wydaje się to zbyt konstruktywne. Dlaczego uważasz, że ten konkretny problem może zainteresować algorytmy kwantowe?
Norbert Schuch,
@Norbert Schuch I cube i robię obliczenia kwantowe. To dla mnie naprawdę interesujący problem (i pomyślałbym każdemu, kto jest zainteresowany kwantową optymalizacją kombinatoryczną).
meowzz
1
Zobacz także mathoverflow.net/questions/77836/... ze strony siostrzanej.
Mark S

Odpowiedzi:

4

Możemy myśleć o sześcianie Rubika wykres Cayley'a przy czym każda (kolorowa) krawędź jest jednym z ruchów Singmastera a każdy wierzchołek jest jedną z różnych konfiguracji kostek .Γ=(V,E)EU,U2,U3=U1,D,D2,D3,V432520032744898560004.3e193×3×3

Średnica wykresu jest najdłuższy najkrótsza ścieżka na wykresie. Klasyczny algorytm do określania średnicy jest wielomianem w ; patrz np. odpowiedź z siostrzanej strony.|V|

Jak wspomniano powyżej, liczba Boga jest (związana z) tą średnicą; aby poznać najdłuższą najkrótszą ścieżkę między wierzchołkami dla wykresu Cayleya w grupie, wystarczy wiedzieć, ile kroków dzieli nas od rozwiązania stanu. Wiemy, między innymi dzięki Rokickiemu, Kociembie, Davidsonowi i Dethridge, że liczba Boga wynosi . Algorytmy, które wykonali, były wielomianem w , np. Wielomianem w .20|V|4.3e19

Wspomniany w komentarzach algorytm kwantowy Heiligmana dla średnicy wykresu osiąga przyspieszenie Grovera w stosunku do algorytmów Djikstry, z „całkowitym kosztem kwantowym ”. Uważam jednak, że Heiligman koduje wykres podobnie jak klasyczny algorytm; np. z . Oczywiście, jeśli to nie pomogłoby.O(|V|9/4)O(|V|)|V|=4.3e19

Zamiast tego, innym sposobem kodowania kostki Rubika, jak wskazano w innych pytaniach, jest oczywiście przygotowanie jednolitej superpozycji we wszystkich . To zajmuje tylko .4.3e19log4.3e19

Algorytmy kwantowe są dobre w mówieniu o „wartościach własnych” i „wektorach własnych” i „stanach własnych”. Zastosowanie wszystkich ruchów Singmastera do jednolitej superpozycji wszystkich nie zmienia stanu; tj. jednolita superpozycja jest stanem własnym łańcucha Markowa na wykresie Cayleya.4.3e19

Istnieją zależności między średnicą wykresu a wartościami własnymi / wektorami własnymi odpowiadającej przyległości / macierzy Laplaciana, zwłaszcza szczeliną widmową, odległością między dwoma największymi wartościami własnymi ( ). Szybkie wyszukiwanie w Google z „średnica wartości własnej” produkuje to ; Polecam zbadanie podobnych wyszukiwań w Google.λ1λ2

Luki widmowe są dokładnie tym , co ogranicza algorytm adiabatyczny . Zatem, być może wiedząc, jak szybko musi działać algorytm adiabatyczny, aby ewoluować od jednolitego superpozycji do stanu rozwiązanego dla różnych podgrup / podprzestrzeni grupy kostki Rubika, można oszacować lukę widmową i wykorzystać to do ograniczenia liczby Boga. Ale szybko wyszedłem z mojej ligi i wątpię, by jakiekolwiek poczucie dokładności było możliwe.

Znaki
źródło
Przede wszystkim dziękuję za doskonałą odpowiedź. Jestem bardzo zainteresowany, aby dowiedzieć się więcej o lukach spektralnych i procesach diabatycznych. Czy wiesz coś o grafach podrzędnych ? Ponadto, czy wiesz cokolwiek na temat liczb surrealistycznych (w szczególności luk )? Czy masz też jakieś przemyślenia na temat skrzynki 2x2? Czy przypadek nxn (dla )? 3<n
meowzz
1
@meowzz, nie ma za co. Przepraszam, nie wiem nic o liczbach surrealistycznych lub grafach podrzędnych. Powyższy wykres Cayleya nie jest sześcienny i ma wartość jak sądzę ( twarzy i ćwierć, pół lub trzy czwarte ruchu na twarz). W przypadku przypadku obowiązuje to samo myślenie ... zmierzyć, jak długo algorytm adiabatyczny ewoluuje w stan rozwiązany, użyj relacji między i aby ograniczyć lukę widmową i ograniczyć średnicę w relacji między i ...186n×nτnτnλ2δλ2δ
Mark S
1
Czytając odpowiedź, nie jest jeszcze w pełni jasne „Jakiego rodzaju przyspieszenie można osiągnąć dzięki podejściu kwantowemu?”.
JanVdA,
1
@JanVdA Dziękujemy za komentarz. Nigdy nie twierdziłem, że znam wszystkie szczegóły odpowiedzi na odważne pytanie. Po prostu starałem się przekazać informacje zwrotne na temat podejść, które mogą być warte zbadania, a także lekko odeprzeć inny komentarz w pytaniu. Poza tym ktoś był bardzo przyjazny na podobne pytanie ode mnie.
Mark S