¿Cuánto tiempo toma el recocido cuántico para encontrar la solución a un problema dado?

15

El recocido cuántico es un protocolo de optimización que, gracias al túnel cuántico, permite en determinadas circunstancias maximizar / minimizar una función determinada de manera más eficiente que los algoritmos de optimización clásicos.

Un punto crucial del recocido cuántico es la adiabaticidad del algoritmo, que se requiere para que el estado permanezca en el estado fundamental del hamiltoniano dependiente del tiempo. Sin embargo, esto también es un problema, ya que significa que encontrar una solución puede requerir mucho tiempo.

¿Cuánto tiempo tienen que ser estos tiempos para un hamiltoniano determinado? Más precisamente, dado un problema hamiltoniano del cual queremos encontrar el estado fundamental, ¿hay resultados que indiquen cuánto tiempo tomaría un recocido cuántico alcanzar la solución?H

glS
fuente
3
Las respuestas a esta pregunta deberían considerar tener en cuenta el ruido, ya que es una parte crítica de lo que determina la velocidad del túnel cuántico.
DanielSank
1
¿No está relacionado con las propiedades espectrales de ? H
Mark S

Respuestas:

14

El tiempo de solución (tts) depende en gran medida del hamiltoniano del problema que uno quisiera resolver. El D-Wave utiliza un Hamiltoniano similar al vidrio giratorio que puede estar en la clase de complejidad NP-Complete.

Debido a tener que ejecutar el proceso de recocido varias veces, las medidas de tts generalmente se cuantifican según el tiempo que lleva encontrar el estado fundamental en un porcentaje del tiempo.

Aquí hay un artículo de algunos colegas que explica tts (ver especialmente la ecuación 3).

Andrew O
fuente