¿Por qué el recocido cuántico no puede describirse mediante un modelo de puerta?

21

Esta es una pregunta que me inspiró hacer en base a esta pregunta , que señala que el recocido cuántico es un modelo de computación completamente diferente al modelo de circuito habitual. He escuchado esto antes, y tengo entendido que el modelo de puerta no se aplica al recocido cuántico, pero nunca he entendido por qué, o cómo analizar los cálculos que puede hacer un anillador. Según tengo entendido por varias conversaciones (¡algunas por D-wave!), El hecho de que los recoctores están confinados a un Hamiltoniano específico juega en él.

Emily Tyhurst
fuente

Respuestas:

18

Un analizador cuántico, como una máquina D-Wave, es una representación física del modelo Ising y, como tal, tiene un 'problema' hamiltoniano de la forma

HP=J=1nhjσjz+i,jJijσizσjz.

Esencialmente, el problema a resolver se asigna al Hamiltoniano anterior. El sistema comienza con el Hamiltoniano y el parámetro de recocido s se usa para mapear el Hamiltoniano H I inicial al problema Hamiltoniano H P usando H ( s ) = ( 1 - s ) H I + s H P .HI=J=1nhjσjXsHyoHPAGSH(s)=(1-s)Hyo+sHPAGS

Como se trata de un recocido, el proceso se realiza lo suficientemente lento como para permanecer cerca del estado fundamental del sistema, mientras que el Hamiltoniano varía según el problema, utilizando túneles para permanecer cerca del estado fundamental como se describe en la respuesta de Nat .

Ahora, ¿por qué no se puede usar esto para describir un control de calidad del modelo de puerta? Lo anterior es un problema de optimización binaria sin restricciones cuadrática (QUBO) , que es NP-hard ... De hecho, aquí hay un artículo que asigna una serie de problemas de NP al modelo de Ising . Cualquier problema en NP puede asignarse a cualquier problema NP-duro en tiempo polinómico y la factorización de enteros es de hecho un problema NP.

Bueno, la temperatura no es cero, por lo que no estará en el estado fundamental durante el recocido y, como resultado, la solución sigue siendo solo aproximada. O, en términos diferentes, la probabilidad de falla es mayor a la mitad (no tiene nada de cerca tener una probabilidad de éxito decente en comparación con lo que un control de calidad universal considera 'decente' - a juzgar por los gráficos que he visto, la probabilidad de éxito para el La máquina actual es de alrededor del y esto solo empeorará con el aumento del tamaño), y el algoritmo de recocido no es un error acotado. En absoluto. Como tal, no hay forma de saber si tiene o no la solución correcta con algo como la factorización de enteros.0.2 0.2%

Lo que (en principio) hace es acercarse mucho al resultado exacto, muy rápidamente, pero esto no ayuda para nada donde se requiere el resultado exacto, ya que pasar de 'casi correcto' a 'correcto' sigue siendo extremadamente difícil ( es decir, presumiblemente todavía NP en general, cuando el problema original está en NP) en este caso, ya que los parámetros que son / dan una solución 'casi correcta' no necesariamente se distribuirán en ningún lugar cerca de los parámetros que son / dan el solución correcta

Edite para aclarar: lo que esto significa es que un recocido cuántico (QA) todavía toma tiempo exponencial (aunque potencialmente un tiempo exponencial más rápido) para resolver problemas de NP como la factorización de enteros, donde un QC universal da una velocidad exponencial y puede resolver lo mismo problema en el tiempo poli. Esto es lo que implica que un control de calidad no puede simular un control de calidad universal en el tiempo polivinílico (de lo contrario, podría resolver problemas en el tiempo polivinílico que no puede). Como se señaló en los comentarios, esto no es lo mismo que decir que un control de calidad no puede dar la misma velocidad en otros problemas, como la búsqueda en la base de datos.

Mithrandir24601
fuente
1
Si entiendo correctamente, básicamente estás diciendo que un recocido cuántico no puede describir un circuito cuántico porque el problema de encontrar el mínimo de un Hamiltoniano arbitrario es NP-duro. No entiendo esta implicación. Simular circuitos cuánticos también es en general difícil de simular clásicamente (véase, por ejemplo, 1610.01808 )
glS
1
Además, se sabe que algunos problemas que se pueden resolver mediante algoritmos expresados ​​como circuitos cuánticos también se pueden resolver mediante recocido cuántico. Un ejemplo notable es la búsqueda en la base de datos (ver, por ejemplo, la sección II de 1006.1696 ). Esto significa que, en cierto sentido , en algunas circunstancias se puede asignar un circuito aq en un problema de recocido q. ¿No invalida esto también su tercer párrafo (específicamente, la afirmación de que esto [no puede] usarse para describir un
control de
1
@glS no, para nada: todavía se necesita un tiempo exponencial para encontrar el mínimo (según el artículo en su segundo comentario) de un problema NP-difícil, por lo que si bien hay problemas en P (por ejemplo, búsqueda en la base de datos) donde la aceleración puede para poder coincidir con el control de calidad universal, la resolución de un problema de NP todavía requiere un tiempo exponencial para estar dentro del error acotado, donde un control de calidad universal puede resolver el mismo problema en el tiempo polivinílico, por ejemplo, la factorización de enteros. Como el control de calidad no puede hacer esto, un control de calidad no puede simular un control de calidad universal en tiempo polivinílico
Mithrandir24601
Ok, pero eso no es lo que estás diciendo en la respuesta (o al menos, no explícitamente). Según la respuesta, parece que está diciendo que el control de calidad nunca se puede usar para resolver un problema resuelto a través del modelo de control de calidad QC. Esto es muy diferente a decir que la GC no puede resolver eficazmente un problema NP-duro (que podría a veces ser resuelto por un circuito cuántico ... aunque no creo que esto ha sido demostrado, ya que no sabemos si es realmente Factoring NP-hard, y la mayoría de los otros problemas en los que se ha demostrado una ventaja cuántica no son problemas de decisión, que yo sepa).
glS
Hice una edición que espero aclare las cosas. No se sabe si P = NP o no, claro, pero sigue siendo un ejemplo específico de QC que es exponencialmente más rápido, según el conocimiento actual
Mithrandir24601
16

El recocido es más una táctica analógica.

La esencia es que tiene alguna función extraña que desea optimizar. Entonces, rebotas a su alrededor. Al principio, la " temperatura " es muy alta, de modo que el punto seleccionado puede rebotar mucho. Luego, a medida que el algoritmo se " enfría ", la temperatura baja y el rebote se vuelve menos agresivo.

En última instancia, se establece en un óptimo local que, idealmente, es favorablemente como el óptimo global.

Aquí hay una animación para el recocido simulado (no cuántico):

Pero, es más o menos el mismo concepto para el recocido cuántico :

Por el contrario, la lógica de puerta es mucho más digital que analógica. Se trata de qubits y operaciones lógicas en lugar de simplemente encontrar un resultado después de un caótico rebote.

Nat
fuente
Gracias, esto aclara ciertas limitaciones para mí. ¿Conoces algún problema que no sea posible reformular como un problema de recocido? me encantaría escucharlos :)
Emily Tyhurst
2
@EmilyTyhurst Técnicamente, cualquier problema puede describirse en términos de escalada. Es más una cuestión de qué tan bien se ve el problema cuando se describe en formato de escalada. Los problemas que no encajan bien pueden ser increíblemente feos. Para problemas completamente no convexos, escalar colinas, en el mejor de los casos, sería básicamente una búsqueda de fuerza bruta.
Nat
@EmilyTyhurst Hah opps, leyó mal su comentario en la dirección opuesta. xD Pero, sí, puedes hacer recocido simulado en una computadora cuántica tal como puedes hacerlo en una computadora clásica. Entonces, supongo que si lo llamamos o no " recocido cuántico " se convierte más en una cuestión de semántica.
Nat
2
@EmilyTyhurst Sí, definitivamente son todos interconvertibles. Quiero decir, es algo así como el concepto de integridad de Turing: si tenemos algún tipo de lógica completa, podemos construir casi cualquier otra cosa con ella.
Nat
1
Un punto importante del recocido cuántico es el de cambiar adiabáticamente el hamiltoniano para que el estado permanezca en un estado fundamental del hamiltoniano (cambiante) en todo momento, y termines con el gs del hamiltoniano final, que es el objetivo del protocolo . ¿Cómo se relaciona esto con el "salto" que estás describiendo aquí? Este documento ( 1006.1696 ) puede ser de interés a este respecto (específicamente, la última parte de la segunda columna de la primera página).
glS