La optimización combinatoria impregna la ciencia y la ingeniería: desde la planificación de rutas hasta la asignación de recursos. Muchos de estos problemas equivalen a encontrar el estado fundamental del modelo de Ising, lo que pertenece a la clase de problemas NP-difíciles. Las heurísticas clásicas, como el recocido simulado, a menudo quedan atrapadas en mínimos locales debido a un paisaje energético accidentado. Los enfoques cuánticos, en particular QAOA, prometen aceleración, pero sufren de problemas de entrenabilidad y de la profundidad limitada de los circuitos en el hardware actual. Este trabajo se inscribe en la línea de intentos recientes de utilizar procesadores cuánticos intermedios ruidosos (NISQ) para tareas prácticas: investigaciones vecinas estudian algoritmos cuánticos, corrección de errores e información cuántica. La diferencia de este trabajo radica en el esquema híbrido concreto, donde la parte cuántica solo propone "saltos" entre cuencas, mientras que toda la optimización fina permanece clásica.
El algoritmo Qjump funciona de forma iterativa. Dada una 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, L capas de operadores de costo 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 evita el problema de las mesetas estériles. Tras el muestreo cuántico, el ordenador clásico realiza una búsqueda local (descenso voraz) para cada candidato y selecciona la mejor solución. Los experimentos se llevaron a cabo en un procesador superconductor de 104 cúbits con una precisión mediana de las puertas de dos cúbits del 99,5%. Como comparación se utilizó un recocido simulado clásico altamente optimizado (SA) en una CPU de un solo núcleo.
En 20 instancias especialmente seleccionadas del problema de Ising con 104 cúbits, Qjump encontró el mínimo global en promedio 2,23 veces más a menudo que SA, en un tiempo fijo. Además, el muestreador cuántico mostró una mayor probabilidad de caer en la región del mínimo global en comparación con el muestreo aleatorio clásico con la misma proporción de bits invertidos. Con base en supuestos sobre el futuro hardware cuántico (frecuencia de muestreo de 0,4 MHz, control rápido mediante FPGA), se estimó el tiempo hasta la solución (TTS): Qjump superó a SA en CPU de un solo núcleo en 2,34 veces. Para sistemas más pequeños (60 y 84 cúbits), la ventaja fue menor (0,98 y 1,56 veces, respectivamente), lo que indica una mejora con el tamaño del problema. QAOA con búsqueda local resultó casi ineficaz para estos problemas.
El trabajo demuestra que los esquemas híbridos, donde el procesador cuántico se utiliza solo para "saltar" por el paisaje y el clásico para la optimización precisa, pueden ser un camino práctico hacia la ventaja cuántica en dispositivos NISQ. A diferencia de trabajos vecinos que se centran en algoritmos puramente cuánticos o en la corrección de errores, aquí se propone un mecanismo concreto de división de tareas que reduce los requisitos de profundidad de circuito y calidad de los cúbits. Esto amplía la aplicabilidad de los procesadores cuánticos existentes para problemas de optimización hoy mismo.
El siguiente paso natural es escalar a miles de cúbits y mejorar las métricas de los cúbits. También es interesante investigar los parámetros óptimos del muestreador y la estructura del circuito, así como el impacto del ruido de las puertas y las mediciones. Potencialmente, Qjump podría combinarse con otras heurísticas clásicas (búsqueda tabú, método de ramificación y acotación) o utilizarse como módulo en un conjunto de algoritmos.
Los resultados pueden influir en áreas donde se requiere resolver problemas NP-difíciles: logística, finanzas, ciencia de materiales, aprendizaje automático. El enfoque híbrido podría adaptarse a otras plataformas cuánticas.
Realizar experimentos en sistemas con miles de cúbits y mejores precisiones de puertas. Investigar el escalado de la complejidad temporal de Qjump con el tamaño del problema.
En el campo de la computación cuántica sigue abierta la cuestión de si los dispositivos cuánticos intermedios ruidosos pueden proporcionar una ventaja práctica sobre los algoritmos clásicos para problemas de optimización. Este trabajo contribuye demostrando un algoritmo híbrido concreto y evidencia experimental de ventaja en 104 cúbits, pero la prueba estricta de la aceleración cuántica requiere más investigación.
Esta sección está dirigida al autor del trabajo y a sus colegas. Los trabajos vecinos los encontró la búsqueda por significado en nuestro archivo, no por coincidencia de palabras. No evaluamos: mostramos el campo alrededor.
Qué hace el trabajo
En este trabajo se propone un algoritmo híbrido cuántico-clásico llamado Qjump, que utiliza un muestreador cuántico para generar candidatos en diferentes cuencas de energía y una búsqueda local clásica para el descenso. En un procesador de 104 cúbits, el algoritmo encontró el mínimo global con más frecuencia que el recocido simulado clásico y mostró una aceleración extrapolada de 2.34 veces en el tiempo hasta la solución.
Dónde está su fuerza
La fortaleza radica en el esquema híbrido concreto, donde la parte cuántica se encarga solo de los 'saltos' entre cuencas, mientras que la optimización fina permanece clásica. Esto permite evitar los problemas de la optimización variacional y usar parámetros fijos del circuito.
Hacia dónde puede avanzar
Vale la pena probar
Trabajos cercanos en nuestro archivo
El archivo está vacío alrededor de este trabajo: el análisis más cercano queda en 0.58, frente a un 0.64 habitual. Parece que aquí al lado casi nadie ha perforado.
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.