Algorytm kwantowy dla liczby Boga

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

„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 \times n \times n

$n\times n \times n$

N P

$\mathsf{NP}$

— Mark S

@mark s chat.stackexchange.com/rooms/81283/quantum

— meowzz

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

Zobacz także mathoverflow.net/questions/77836/... ze strony siostrzanej.

— Mark S

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 . $\Gamma=(V,E)$ $E$ $\langle U,U^{2},U^{3}=U^{-1},D,D^{2},D^{3},\cdots\rangle$ $V$ $43252003274489856000\approx 4.3e{19}$ $3\times 3\times 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. $\vert V \vert$

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$ $\vert V\vert$ $4.3e{19}$

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.3e{19}$

Zamiast tego, innym sposobem kodowania kostki Rubika, jak wskazano w innych pytaniach, jest oczywiście przygotowanie jednolitej superpozycji we wszystkich . To zajmuje tylko . $4.3e{19}$ $\log 4.3e{19}$

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.3e{19}$

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. $\lambda_1-\lambda_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

$3<n$

— meowzz

@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 ...

18

$18$

6

$6$

n \times n

$n\times n$

τ_{n}

$\tau_n$

τ_{n}

$\tau_n$

λ_{2}

$\lambda_2$

δ

$\delta$

λ_{2}

$\lambda_2$

δ

$\delta$

— Mark S

Czytając odpowiedź, nie jest jeszcze w pełni jasne „Jakiego rodzaju przyspieszenie można osiągnąć dzięki podejściu kwantowemu?”.

— JanVdA,

@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