Algorithme quantique pour le nombre de Dieu

Le nombre de Dieu est le pire des cas de l'algorithme de Dieu qui est

une notion issue de discussions sur les moyens de résoudre le puzzle Rubik's Cube, mais qui peut également être appliquée à d'autres puzzles combinatoires et jeux mathématiques. Il se réfère à tout algorithme qui produit une solution ayant le moins de mouvements possibles, l'idée étant qu'un être omniscient connaîtrait une étape optimale à partir de n'importe quelle configuration donnée.

Le calcul du nombre de Dieu à 20 a pris "35 années-CPU de temps inactif (classique) sur ordinateur."

Quel type d'accélération pourrait être atteint avec une approche quantique?

Nous pouvons penser du cube Rubik Cayley graphe avec chacune (couleur) bord E étant l' un des mouvements Singmaster ⟨ U , U 2 , U 3 = U - 1 , D , D 2 , D 3 , ⋯ ⟩ et chaque sommet V étant l'un des 43252003274489856000 $\Gamma=(V,E)$$E$$\langle U,U^{2},U^{3}=U^{-1},D,D^{2},D^{3},\cdots\rangle$$V$ configurations différentes du 3 × $43252003274489856000\approx 4.3e{19}$ cubes.$3\times 3\times 3$

Le diamètre d'un graphique est le chemin le plus long et le plus court du graphique. L'algorithme classique pour déterminer le diamètre est polynomial en ; voir, par exemple, cette réponse d'un site frère.$\vert V \vert$

Comme mentionné ci-dessus, le nombre de Dieu est (lié à) ce diamètre; pour connaître le chemin le plus long le plus court entre les sommets d'un graphe de Cayley sur un groupe, il suffit de savoir combien de pas s'éloignent de l'état résolu. Nous savons, grâce à Rokicki, Kociemba, Davidson et Dethridge, entre autres, que le nombre de Dieu est . Les algorithmes qu'ils ont exécutés étaient polynomiaux dans | V | , par exemple polynôme en 4.3 e 19 .$20$$\vert V\vert$$4.3e{19}$

L'algorithme quantique de Heiligman pour le diamètre graphique, mentionné dans les commentaires, réalise un gain de vitesse Grover sur les algorithmes de Djikstra, avec « un coût quantique total de . » Cependant, je crois que Heiligman code le graphe comme le ferait un algorithme classique; par exemple avec des qubits O ( | V | ) . Clairement si | V | = 4,3 e 19 alors cela n'aiderait pas.$O(|V|^{9/4})$$O(|V|)$$|V|=4.3e{19}$

Au lieu de cela, une autre façon d'encoder un cube de Rubik, comme indiqué dans les autres questions, est bien sûr de préparer une superposition uniforme sur tous les états . Cela ne prend que le journal 4.3 et 19 qubits.$4.3e{19}$$\log 4.3e{19}$

Les algorithmes quantiques sont bons pour parler de "valeurs propres" et "vecteurs propres" et "états propres". L'application de tous les mouvements Singmaster à une superposition uniforme de tous les états ne change pas l'état; c'est-à-dire que la superposition uniforme est un état propre de la chaîne de Markov sur le graphique de Cayley.$4.3e{19}$

Il existe des relations entre le diamètre d'un graphe et les valeurs propres / vecteurs propres de la matrice adjacente / laplacienne correspondante, en particulier l'écart spectral, la distance entre les deux plus grandes valeurs propres ( ). Une recherche rapide sur Google de "valeur propre de diamètre" produitceci; Je recommande d'explorer des recherches Google similaires.$\lambda_1-\lambda_2$

Les lacunes spectrales sont exactement ce qui limite l' algorithme adiabatique . Ainsi, peut-être en sachant à quelle vitesse un algorithme adiabatique doit fonctionner pour évoluer de la superposition uniforme à l'état résolu pour divers sous-groupes / sous-espaces du groupe de cubes de Rubik, on pourrait estimer l'écart spectral et l'utiliser pour délimiter le nombre de Dieu. Mais je suis rapidement hors de ma ligue ici et je doute que tout sentiment de précision soit réalisable.