Algoritmo Cuántico para el Número de Dios

9

El número de Dios es el peor caso del algoritmo de Dios que es

Una noción que se origina en las discusiones sobre formas de resolver el rompecabezas del cubo de Rubik, pero que también se puede aplicar a otros rompecabezas combinatorios y juegos matemáticos. Se refiere a cualquier algoritmo que produzca una solución que tenga la menor cantidad de movimientos posibles, la idea es que un ser omnisciente conozca un paso óptimo de cualquier configuración dada.

Calcular el número de Dios en 20 tomó "35 años de CPU de tiempo inactivo (clásico) en la computadora".

¿Qué tipo de aceleración podría lograrse con un enfoque cuántico?

meowzz
fuente
1
El "número de Dios" para los acertijos combinatorios está relacionado con el diámetro del gráfico similar a Cayley, es decir, el camino más pequeño y más grande del gráfico. No creo que el problema generalizado de los rompecabezas esté en . No he estudiado este artículo, arxiv.org/abs/quant-ph/0303131 , pero creo que afirma una aceleración de Grover sobre la clásica. N Pn×n×nNP
Mark S
1
Puede hacer una pregunta como esta para cualquier cosa que sea difícil de calcular. Esto no parece ser muy constructivo. ¿Por qué pensarías que este problema específico podría ser de interés para los algoritmos cuánticos?
Norbert Schuch el
@ Norbert Schuch Cubo y hago computación cuántica. Es un problema realmente interesante para mí (y creo que para cualquier otra persona interesada en la optimización combinatoria cuántica).
meowzz
1
Vea también mathoverflow.net/questions/77836/… de un sitio hermano.
Mark S

Respuestas:

4

Podemos pensar en el gráfico Cayley del cubo de Rubik con cada borde (de color) como uno de los movimientos de Singmaster y cada vértice es una de las configuraciones diferentes de los cubos.E U , U 2 , U 3 = T - 1 , D , D 2 , D 3 , V 43252003274489856000 4,3 e 19 3 × 3 × 3Γ=(V,E)EU,U2,U3=U1,D,D2,D3,V432520032744898560004.3e193×3×3

El diámetro de un gráfico es la ruta más corta más larga del gráfico. Algoritmo clásico para determinar el diámetro es polinomial en ; ver, por ejemplo, esta respuesta de un sitio hermano.|V|

Como se mencionó anteriormente, el número de Dios está (relacionado con) este diámetro; Para conocer el camino más corto más largo entre los vértices para un gráfico de Cayley en un grupo, es suficiente saber a cuántos pasos del estado resuelto se encuentra uno. Sabemos, gracias a Rokicki, Kociemba, Davidson y Dethridge, entre otros, que el número de Dios es . Los algoritmos que ejecutaron fueron polinomiales en , por ejemplo, polinomios en .| V | 4.3 e 1920|V|4.3e19

El algoritmo cuántico de Heiligman para el diámetro del gráfico, mencionado en los comentarios, logra una aceleración de Grover sobre los algoritmos de Djikstra, con "un costo cuántico total de ". Sin embargo, creo que Heiligman codifica el gráfico como lo haría un algoritmo clásico; por ejemplo, con qubits . Claramente si entonces esto no ayudaría.O ( | V | ) | V | = 4.3 e 19O(|V|9/4)O(|V|)|V|=4.3e19

En cambio, otra forma de codificar un cubo de Rubik, como se insinuó en las otras preguntas, es, por supuesto, preparar una superposición uniforme en todos los . Esto solo toma qubits. log 4.3 e 194.3e19log4.3e19

Los algoritmos cuánticos son buenos para hablar de "valores propios" y "vectores propios" y "estados propios". La aplicación de todos los movimientos de Singmaster a una superposición uniforme de todos los no cambia el estado; es decir, la superposición uniforme es un estado propio de la cadena de Markov en el gráfico de Cayley.4.3e19

Existen relaciones entre el diámetro de un gráfico y los valores propios / vectores propios de la matriz adyacente / laplaciana correspondiente, especialmente el espacio espectral, la distancia entre los dos valores propios más grandes ( ). Una búsqueda rápida en Google del "valor propio del diámetro" produce esto ; Recomiendo explorar búsquedas similares en Google.λ1λ2

Las brechas espectrales son exactamente lo que limita el algoritmo adiabático . Por lo tanto, tal vez al saber qué tan rápido necesita correr un algoritmo adiabático para evolucionar desde el superpositorio uniforme al estado resuelto para varios subgrupos / subespacios del grupo de cubos de Rubik, uno podría estimar la brecha espectral y usar esto para vincular el número de Dios. Pero estoy rápidamente fuera de mi alcance aquí y dudo que se pueda lograr una sensación de precisión.

Marcas
fuente
En primer lugar, gracias por la excelente respuesta. Estoy muy interesado en obtener más información sobre las brechas espectrales y los procesos diabáticos. ¿Sabes algo sobre los gráficos subcúbicos ? Además, ¿sabes algo sobre los números surrealistas (en particular, las brechas )? Además, ¿tiene alguna idea sobre el caso 2x2? ¿O el caso nxn (para )? 3<n
meowzz
1
@meowzz, de nada. Lo siento, no sé nada sobre números surrealistas o gráficos subcúbicos. El gráfico de Cayley anterior no es cúbico y creo que tiene una valencia de ( caras y un movimiento de cuarto, medio o tres cuartos por rostro). Sobre el caso , se aplica el mismo pensamiento ... mida cuánto tarda un algoritmo adiabático para evolucionar a un estado resuelto, use una relación entre y para unir el espacio espectral y el diámetro con relación entre y ...6 n × n τ n τ n λ 2 δ λ 2 δ186n×nτnτnλ2δλ2δ
Mark S
1
Al leer la respuesta aún no está completamente claro "¿Qué tipo de aceleración podría lograrse con un enfoque cuántico?".
JanVdA
1
@ JanVdA Gracias por tu comentario. Nunca pretendí conocer todos los detalles de la respuesta a la pregunta en negrita. Simplemente intenté dar algunos comentarios sobre los enfoques que podrían valer la pena explorar más, y también contrarrestar ligeramente otro comentario en la pregunta. Además, alguien fue muy amable con una pregunta similar mía.
Mark S