Algorithme quantique pour le nombre de Dieu

9

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?

meowzz
la source
1
Le «nombre de Dieu» pour les puzzles combinatoires est lié au diamètre du graphique de type Cayley, c'est-à-dire le plus grand chemin le plus petit du graphique. Je ne pense pas que le problème généralisé des puzzles soit dans . Je n'ai pas étudié cet article - arxiv.org/abs/quant-ph/0303131 - mais je pense qu'il revendique une accélération de Grover par rapport au classique. N Pn×n×nNP
Mark S
1
Vous pouvez poser une question comme celle-ci pour tout ce qui est difficile à calculer. Cela ne semble pas être très constructif. Pourquoi pensez-vous que ce problème spécifique pourrait présenter un intérêt pour les algorithmes quantiques?
Norbert Schuch
@Norbert Schuch I cube et fais de l'informatique quantique. C'est un problème vraiment intéressant pour moi (et je pense à quiconque s'intéresse à l'optimisation combinatoire quantique).
meowzz
1
Voir aussi mathoverflow.net/questions/77836/… d'un site partenaire .
Mark S

Réponses:

4

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 Γ=(V,E)EU,U2,U3=U1,D,D2,D3,V configurations différentes du 3 × 3432520032744898560004.3e19 cubes.3×3×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.|V|

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|V|4.3e19

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.3e19

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.3e19log4.3e19

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.3e19

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.λ1λ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.

Des marques
la source
Tout d'abord, merci pour l'excellente réponse. Je suis très intéressé à en savoir plus sur les lacunes spectrales et les processus diabatiques. Savez-vous quelque chose sur les graphes subcubiques ? De plus, connaissez-vous des choses sur les nombres surréalistes (spécifiquement les lacunes )? Avez-vous également des réflexions sur le cas 2x2? Ou le cas nxn (pour 3 < n )? 3<n
meowzz
1
@meowzz, vous êtes les bienvenus. Je suis désolé de ne rien savoir sur les nombres surréalistes ou les graphiques sous-cubiques. Le graphique de Cayley ci-dessus n'est pas cubique et a une valence de je pense ( 6 faces et un quart, demi ou trois quart de mouvement par face). À propos du cas n × n , la même réflexion s'applique ... mesurer le temps τ n qu'un algorithme adiabatique prend pour évoluer vers un état résolu, utiliser une relation entre τ n et λ 2 pour délimiter l'écart spectral et délimiter le diamètre δ avec relation entre λ 2 et δ ...186n×nτnτnλ2δλ2δ
Mark S
1
Lors de la lecture de la réponse, il n'est pas encore complètement clair "Quel type d'accélération pourrait être atteint avec une approche quantique?".
JanVdA
1
@JanVdA Merci pour votre commentaire. Je n'ai jamais prétendu connaître tous les détails de la réponse à la question en gras. J'ai simplement essayé de donner un retour sur les approches qui pourraient mériter d'être explorées davantage et de contrer légèrement un autre commentaire dans la question. De plus, quelqu'un était très accueillant à une question similaire de ma part.
Mark S