¿Qué es precisamente el recocido inverso?

9

El recocido cuántico (preguntas relacionadas con el recocido cuántico , o relacionado con hamilton ) es el proceso utilizado en el anillador cuántico de D-Waves, en el que se exploran los paisajes energéticos, para diferentes soluciones, y al sintonizar un hamiltoniano adecuado, se enfoca en un posible óptimo Solución a un problema. El proceso de recocido cuántico reduce los "campos magnéticos transversales" en el hamiltoniano, además de otros efectos cuánticos como el túnel cuántico, el enredo y la superposición, que a su vez juegan un papel en la reducción a cero a un "valle" de una función de onda mecánica cuántica. , donde se encuentra la solución "más probable".

El proceso de recocido inverso, muy brevemente, consiste en utilizar métodos clásicos, como el recocido simulado, para encontrar una solución y perfeccionar un valle utilizando el recocido cuántico. Si el Hamiltoniano usado por el Quantum Annealer ya está en un "valle", ya que se le está pasando una solución en primer lugar: ¿la máquina D-Wave alcanza otro "valle" (una solución mejor?) Usando el Hamiltoniano pasado a en primer lugar?

usuario3483902
fuente

Respuestas:

4

Hasta hace poco, los dispositivos de recocido cuántico de D-Wave siempre partían de una superposición uniforme sobre todos los qubits:N

                                                Hinitial=|+0|+1...|+N

donde .|+i=12(|0i+|1i)

Entonces, supongamos que ya ejecutó algunos recocidos con esta configuración y uno de los resultados de baja energía parece una solución relativamente buena (algunos óptimos locales) para su problema de optimización. Hasta la introducción muy reciente de la función de recocido inverso , era imposible usar esta solución como entrada para el próximo recocido a fin de explorar el espacio local alrededor de esa solución para cadenas de bits con energía aún más baja. Por lo tanto, el recocido inverso nos permite inicializar el recocido cuántico con una solución conocida (clásica) y buscar el espacio de estado alrededor de este óptimo local.

Al explorar paisajes energéticos complicados (accidentados) de problemas de optimización, necesita equilibrar la exploración global del espacio estatal con la explotación de los óptimos locales. En el recocido cuántico tradicional (onda D), comenzamos con un campo transversal alto que luego disminuye gradualmente como lo describió en su pregunta. El recocido cuántico de D-Wave estaba realizando una búsqueda global (debido a una gran cantidad de túneles cuánticos) al comienzo del programa de recocido cuando el campo transversal es fuerte. A medida que el campo transversal se debilita, la búsqueda se vuelve más y más local. Por el contrario, el recocido inverso comienza con una solución clásica definida por el usuario, luego aumenta gradualmente el campo transversal (recocido hacia atrás) para luego disminuir nuevamente el campo transversal (recocido hacia adelante).

Esto introduce la nueva distancia de inversión de parámetros que determina qué tan lejos desea recocer hacia atrás (qué tan fuerte debe ser el campo transversal). D-Wave publicó las siguientes dos parcelas en este documento técnico de D-Wave :

trazados de distancia de inversión

En el diagrama de la izquierda puede ver que la distancia de inversión es un nuevo hiperparámetro muy importante ya que su valor determina la probabilidad de obtener un nuevo estado fundamental (región azul). Si la distancia de inversión es demasiado baja, obtendrá el mismo estado con el que comenzó (región roja) que sería inútil. Y, por supuesto, si invierte el recocido durante demasiado tiempo, esencialmente realiza el recocido cuántico tradicional y pierde la información con la que comenzó. ¡Recuerde que demasiado campo transversal significa que estamos realizando una búsqueda global nuevamente!

La gráfica correcta muestra esencialmente lo mismo al trazar la distancia de Hamming contra la distancia de inversión y la probabilidad de obtener un nuevo estado fundamental. Para su problema en cuestión, desea encontrar ese punto óptimo (máximos de la curva roja). Para grandes distancias de inversión, nuevamente vemos que obtenemos cadenas de solución que están lejos de nuestro estado inicial en términos de distancia de Hamming.

En general, el recocido inverso es algo bastante nuevo y, que yo sepa, no hay documentos publicados sobre su efectividad. En su Whitepaper , D-Wave afirma la generación de 'nuevas óptimas globales hasta 150 veces más rápidas que el recocido cuántico directo'.

Mark Fingerhuth
fuente
2

Existen algunos documentos sobre algoritmos que se pueden construir utilizando el recocido inverso, http://iopscience.iop.org/article/10.1088/1367-2630/aa59c4/meta y https://arxiv.org/abs/1609.05875 ( Vale la pena señalar el trabajo anterior del sistema cerrado algo relacionado: https://link.springer.com/article/10.1007/s11128-010-0168-z ). En cuanto a los resultados experimentales, creo que los únicos visibles públicamente en el momento de la redacción son el documento técnico que figura en la publicación anterior. Sin embargo, habrá algunos trabajos nuevos presentados en AQC 2018 ( https://ti.arc.nasa.gov/events/aqc-18/ ) a fines de junio y estas conversaciones generalmente se ponen en línea unos meses después de la conferencia.

Nick Chancellor
fuente