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?

algorithm speedup complexity-theory mathematics quantum-walks 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

Algorytm kwantowy dla liczby Boga

Odpowiedzi: