Quantenalgorithmus für Gottes Zahl

Gottes Zahl ist der schlimmste Fall von Algorithmus Gott , das ist

Ein Begriff, der aus Diskussionen über Möglichkeiten zur Lösung des Rubik's Cube-Puzzles stammt, der aber auch auf andere kombinatorische Rätsel und mathematische Spiele angewendet werden kann. Es bezieht sich auf jeden Algorithmus, der eine Lösung mit möglichst wenigen Bewegungen erzeugt, wobei die Idee darin besteht, dass ein allwissendes Wesen aus jeder gegebenen Konfiguration einen optimalen Schritt kennt.

Die Berechnung der Zahl Gottes auf 20 dauerte "35 CPU-Jahre Leerlauf (klassische) Computerzeit".

Welche Beschleunigung könnte mit einem Quantenansatz erreicht werden?

Wir können uns den Cayley-Graphen des Zauberwürfels wobei jede (farbige) Kante eine der Singmaster-Bewegungen ist und jeder Scheitelpunkt ist eine der verschiedenen Konfigurationen der Würfel.$\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$

Der Durchmesser eines Diagramms ist der längste kürzeste Pfad im Diagramm. Der klassische Algorithmus zur Bestimmung des Durchmessers ist ein Polynom in ; siehe zB diese Antwort von einer Schwesterseite.$\vert V \vert$

Wie oben erwähnt, ist Gottes Zahl (bezogen auf) diesen Durchmesser; Um den längsten kürzesten Weg zwischen den Eckpunkten für einen Cayley-Graphen in einer Gruppe zu kennen, genügt es zu wissen, wie viele Schritte von dem gelösten Zustand entfernt sind. Wir wissen unter anderem dank Rokicki, Kociemba, Davidson und Dethridge, dass Gottes Zahl . Die von ihnen ausgeführten Algorithmen waren Polynome in , z. B. Polynome in .$20$$\vert V\vert$$4.3e{19}$

Heiligmans Quantenalgorithmus für den Graphendurchmesser, der in den Kommentaren erwähnt wird, erreicht eine Grover-Beschleunigung gegenüber Djikstras Algorithmen mit "Gesamtquantenkosten von ". Ich glaube jedoch, dass Heiligman den Graphen so codiert, wie es ein klassischer Algorithmus tun würde. zB mit Qubits. Wenn würde dies natürlich nicht helfen.O ( | V | ) | V | = 4,3 e $O(|V|^{9/4})$$O(|V|)$$|V|=4.3e{19}$

Stattdessen besteht eine andere Möglichkeit, einen Zauberwürfel zu codieren, wie in den anderen Fragen angedeutet, natürlich darin, eine einheitliche Überlagerung über alle -Zustände vorzubereiten . Dies dauert nur Qubits. log 4.3 e $4.3e{19}$$\log 4.3e{19}$

Quantenalgorithmen können gut über "Eigenwerte" und "Eigenvektoren" und "Eigenzustände" sprechen. Das Anwenden aller Singmaster-Züge auf eine einheitliche Überlagerung aller -Zustände ändert den Status nicht. dh die einheitliche Überlagerung ist ein Eigenzustand der Markov-Kette im Cayley-Graphen.$4.3e{19}$

Es gibt Beziehungen zwischen dem Durchmesser eines Graphen und den Eigenwerten / Eigenvektoren der entsprechenden Adjazenz- / Laplace-Matrix, insbesondere der Spektrallücke, dem Abstand zwischen den beiden größten Eigenwerten ( ). Eine schnelle Google-Suche nach "Durchmessereigenwert" ergibt dies ; Ich empfehle, ähnliche Google-Suchanfragen zu untersuchen.$\lambda_1-\lambda_2$

Spektrale Lücken sind genau das , was den adiabatischen Algorithmus einschränkt . Wenn man also weiß, wie schnell ein adiabatischer Algorithmus ausgeführt werden muss, um sich von der einheitlichen Überlagerung zum gelösten Zustand für verschiedene Untergruppen / Unterräume der Rubik-Würfelgruppe zu entwickeln, könnte man die spektrale Lücke abschätzen und diese verwenden, um die Zahl Gottes zu begrenzen. Aber ich bin hier schnell aus meiner Liga heraus und bezweifle, dass ein Gefühl der Genauigkeit erreichbar ist.