Tres mil metros sobre el nivel del mar, una pared vertical. El escalador clásico trepa por una sola ruta, paso a paso, y a menudo se queda atascado en un mínimo local: una pequeña repisa desde la que no hay camino hacia arriba. El escalador cuántico actúa de otra manera: es capaz de saltar sobre el cañón y aterrizar en la cuenca de energía vecina, donde la ruta es mejor.
El paisaje energético es la gráfica de la energía de todas las configuraciones posibles del sistema. Para un problema de optimización, cada punto del paisaje corresponde a una solución, y la altura, a su calidad. Los problemas NP-difíciles, como la búsqueda del estado fundamental del modelo de Ising, tienen un paisaje accidentado con muchos mínimos locales. Las heurísticas clásicas, como el recocido simulado, imitan el enfriamiento del metal: el sistema se enfría lentamente, buscando el mínimo de energía, pero a menudo se queda atrapado en pozos poco profundos.
El algoritmo Qjump funciona de forma iterativa. Dada la solución actual (una cadena de bits), el circuito cuántico genera un conjunto de candidatos, "saltando" a cuencas de energía vecinas. El circuito consta de una capa de codificación, varias capas de operadores de coste y mezcla inspirados en QAOA, y mediciones. Los parámetros del circuito no se optimizan variacionalmente, sino que se toman de valores precalculados para QAOA profundo, lo que elimina el problema de las mesetas estériles. Tras el muestreo cuántico, el ordenador clásico realiza una búsqueda local (descenso codicioso) para cada candidato y elige la mejor solución.
Los experimentos se realizaron en un procesador superconductor de 104 cúbits con una fidelidad mediana de puertas de dos cúbits del 99,5%. En las 20 instancias difíciles seleccionadas, Qjump encontró el mínimo global en promedio 2,23 veces más a menudo que el recocido simulado, en un tiempo fijo. Al extrapolar a equipos futuros con una frecuencia de muestreo de 0,4 MHz y control rápido mediante FPGA, la estimación del tiempo hasta la solución mostró una aceleración de 2,34 veces. Para sistemas más pequeños, la ventaja fue menor: 0,98 veces para 60 cúbits y 1,56 veces para 84 cúbits. Esto indica una mejora con el tamaño del problema. QAOA con búsqueda local resultó casi ineficaz para estos problemas.
Qjump demostró que los esquemas híbridos (donde el procesador cuántico se usa solo para "saltos" por el paisaje y el ordenador clásico para la optimización fina) pueden ser un camino práctico hacia la ventaja cuántica en dispositivos cuánticos intermedios ruidosos. Antes no estaba claro si estos dispositivos sin corrección de errores podrían superar a las heurísticas clásicas. Ahora existe un mecanismo concreto de división del trabajo que reduce los requisitos de profundidad de circuito y calidad de cúbits. Esto amplía la aplicabilidad de los procesadores cuánticos existentes para problemas de optimización ya hoy: logística, planificación, finanzas.
El escalador cuántico no reemplaza al clásico. Solo salta sobre los cañones, y el descenso clásico lleva la solución a la perfección. Juntos ascienden a donde por separado no se podría llegar.
Para seleccionar las instancias difíciles, los científicos generaron 4000 configuraciones aleatorias de conexiones y campos, y luego se quedaron solo con 20 en las que el recocido simulado clásico funcionaba peor. Esto garantiza que la comparación fuera justa: el algoritmo cuántico se probó en los casos más difíciles.