⚛️ quantum physics

Sampled-Based Guided Quantum Walk: Non-variational quantum algorithm for combinatorial optimization

El artículo presenta SamBa-GQW, un algoritmo cuántico no variacional que utiliza un protocolo de muestreo clásico fuera de línea para guiar una caminata cuántica de tiempo continuo hacia soluciones de alta calidad para problemas de optimización combinatoria, demostrando un rendimiento comparable a los métodos variacionales como QAOA sin requerir optimizadores clásicos.

Autores originales: Ugo Nzongani, Dylan Laplace Mermoud, Giuseppe Di Molfetta, Andrea Simonetto

Publicado 2026-10-02

📖 5 min de lectura🧠 Análisis profundo

CC BY 4.0

Autores originales: Ugo Nzongani, Dylan Laplace Mermoud, Giuseppe Di Molfetta, Andrea Simonetto

Artículo original bajo licencia CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta es una explicación generada por IA del artículo a continuación. No ha sido escrita ni avalada por los autores. Para mayor precisión técnica, consulte el artículo original. Leer descargo de responsabilidad completo

En el mundo de la informática, algunos problemas son como intentar encontrar un grano de arena específico en una playa que duplica su tamaño cada vez que das un paso. Estos se conocen como problemas de optimización combinatoria, donde una computadora debe elegir la mejor disposición entre un vasto número de posibilidades, como la ruta más eficiente para un camión de reparto o la mejor combinación de acciones para una cartera de inversiones. A medida que el número de opciones crece, el tiempo requerido para que una computadora tradicional verifique cada opción aumenta tan rápidamente que incluso las supercomputadoras más potentes tardarían más que la edad del universo en encontrar la respuesta. Las computadoras cuánticas, que utilizan las extrañas reglas de la física para procesar información, ofrecen un posible atajo. Pueden explorar muchas posibilidades a la vez, pero las máquinas actuales son ruidosas e imperfectas, y a menudo requieren un ajuste complejo para funcionar correctamente. Esto ha llevado a los investigadores a buscar nuevas formas de guiar estas máquinas cuánticas sin necesidad de que un humano ajuste constantemente la configuración.

Un equipo de investigadores ha introducido un nuevo método llamado SamBa-GQW, una técnica diseñada para resolver estos rompecabezas difíciles sin depender de una computadora clásica para ajustar con precisión el proceso cuántico. En lugar de utilizar un enfoque de prueba y error que requiere que una computadora clásica verifique y corrija constantemente la configuración de la máquina cuántica, este nuevo método utiliza un paso de preparación inteligente y único. Primero, los investigadores toman una muestra pequeña y manejable del paisaje del problema en una computadora regular. Esta muestra actúa como un mapa, revelando la forma general del espacio de soluciones y dónde es probable que se escondan las mejores respuestas. Usando este mapa, configuran la máquina cuántica para que realice un viaje específico, un flujo continuo de probabilidad que deriva naturalmente hacia las mejores soluciones. La máquina cuántica sigue entonces este camino precalculado, guiada por un ritmo cambiante que se ralentiza a medida que se acerca a la respuesta óptima, permitiendo eficazmente que la física del sistema realice el trabajo pesado.

Los investigadores probaron este enfoque en una variedad de problemas desafiantes, incluyendo encontrar la mejor manera de dividir una red en dos grupos, seleccionar el grupo más grande de elementos que no entren en conflicto entre sí y optimizar carteras de inversión. Simularon el proceso en problemas que involucraban hasta treinta variables, un tamaño que es significativo para la tecnología cuántica actual. Los resultados mostraron que el método encontraba consistentemente soluciones de alta calidad, aterrizando a menudo en la mejor respuesta posible o en una muy cercana a ella. En muchos casos, el estado cuántico se volvió altamente enfocado en la solución correcta, lo que significa que si se midiera la salida de la computadora, habría una muy buena probabilidad de obtener la respuesta correcta. El equipo descubrió que solo necesitaban muestrear una fracción diminuta de todas las decisiones posibles para construir un mapa efectivo, demostrando que no era necesario un análisis exhaustivo completo del paisaje del problema para guiar al caminante cuántico.

Al compararlo con otros métodos cuánticos populares, como el Algoritmo de Optimización Aproximada Cuántica (QAOA), la nueva técnica se mantuvo a la altura, aunque con un compromiso diferente. El método QAOA estándar depende de una computadora clásica para ajustar repetidamente la configuración de la máquina cuántica para encontrar el mejor rendimiento, un proceso que puede ser lento y propenso a quedarse atrapado en trampas locales. En contraste, el método SamBa-GQW no requiere tal ajuste; ejecuta una secuencia única y predeterminada. Si bien el método estándar a menudo logra resultados ligeramente mejores cuando se le otorgan circuitos muy profundos y complejos, el nuevo método funciona igual de bien cuando se permite que la profundidad del circuito crezca lo suficiente. Esto sugiere que, para las computadoras cuánticas futuras y más potentes, este enfoque no variacional podría ser una forma altamente eficiente de resolver problemas complejos, evitando la necesidad de los difíciles y prolongados bucles de optimización que actualmente limitan muchos algoritmos cuánticos.

El estudio también exploró cómo se comporta el método con diferentes tipos de problemas y niveles de dificultad variables. Para algunos problemas, como maximizar el número de condiciones satisfechas en un acertijo lógico, el método encontró las mejores soluciones con alta probabilidad incluso para versiones complejas del problema. Para otros, como el problema del viajante, el tiempo requerido para que la máquina cuántica completara su viaje dependía de las distancias específicas entre las ciudades, pero el método aun así guio con éxito al sistema hacia la ruta óptima. Los investigadores observaron que el estado cuántico se concentraría naturalmente en las mejores respuestas, encogiéndose desde una amplia dispersión de posibilidades hacia un grupo compacto alrededor de la solución. Esta localización ocurrió rápidamente en muchos casos, lo que sugiere que el método es robusto y confiable.

En última instancia, este trabajo presenta una alternativa prometedora para la próxima generación de la computación cuántica. Al reemplazar la necesidad de un optimizador clásico con un protocolo de muestreo sencillo y fuera de línea, los investigadores han creado un camino simplificado para que las máquinas cuánticas resuelvan problemas difíciles. El método no pretende resolver estos problemas instantáneamente o mediante un truco de magia; más bien, ofrece una forma práctica y matemáticamente fundamentada de navegar los vastos espacios de búsqueda de la optimización combinatoria. A medida que el hardware cuántico continúe mejorando, yendo más allá de la era ruidosa actual, este enfoque podría convertirse en una herramienta estándar para abordar los desafíos logísticos y científicos a gran escala que actualmente desbordan a las computadoras clásicas. Los hallazgos sugieren que, con la guía adecuada, los sistemas cuánticos pueden encontrar eficientemente el camino hacia las mejores soluciones sin necesidad de una mano humana que los dirija en cada paso.

Resumen Técnico: Caminata Cuántica Guiada Basada en Muestreo (SamBa–GQW)

Planteamiento del Problema

El artículo aborda el desafío de resolver problemas de optimización combinatoria binaria de grado arbitrario en computadoras cuánticas. Estos problemas, que a menudo son NP-duros, consisten en encontrar un vector binario $x^* \in \{0, 1\}^n$ que minimice una función de costo $C(x)$ , potencialmente sujeto a restricciones. Si bien las computadoras cuánticas ofrecen una forma natural de explorar espacios de soluciones exponenciales con recursos de cúbits lineales, los dispositivos actuales de Escala Intermedia con Ruido (NISQ) tienen dificultades con los algoritmos variacionales como el Algoritmo de Optimización Aproximada Cuántica (QAOA). Estos enfoques variacionales dependen de un optimizador clásico para ajustar parámetros, un proceso que suele verse afectado por "mesetas estériles" (gradientes evanescentes) y un escalado exponencial en el número de evaluaciones de circuito requeridas a medida que aumenta el tamaño del problema.

Las alternativas no variacionales existentes, como la Caminata Cuántica Guiada (GQW), intentan evitar la optimización clásica utilizando una tasa de salto dependiente del tiempo derivada del espectro del Hamiltoniano del problema. Sin embargo, calcular el espectro exacto es exponencialmente costoso, y las aproximaciones previas mediante curvas paramétricas (por ejemplo, curvas de Bézier) aún requerían optimización clásica, lo que conducía a un escalado exponencial en el número de iteraciones.

Metodología: SamBa–GQW

Los autores proponen SamBa–GQW (Caminata Cuántica Guiada Basada en Muestreo), un algoritmo cuántico no variacional que elimina la necesidad de un optimizador clásico durante la fase de ejecución cuántica. El algoritmo opera en dos etapas distintas:

1. Protocolo de Muestreo Clásico Offline

En lugar de computar el espectro exacto del Hamiltoniano de costo $H_C$ (lo que requiere $2^n$ evaluaciones) o de optimizar una curva paramétrica, el algoritmo emplea un protocolo de muestreo eficiente.

Muestreo: El protocolo selecciona aleatoriamente un número polinomial de estados candidatos, $q = \text{poly}(n)$ (encontrado empíricamente suficiente con $q=n^2$ ), del espacio de soluciones de $2^n$ .
Estimación de la Brecha (Gap): Para cada estado muestreado, el algoritmo computa las brechas de energía entre el estado y sus vecinos (definidos por la conectividad del mezclador, por ejemplo, el hipercubo para un mezclador X).
Aproximación del Espectro: Calcula el promedio de las mayores brechas de energía para niveles de energía específicos. Esto proporciona una aproximación de la función $\Gamma(E)$ , que relaciona la tasa de salto con la brecha de energía, tal como se deriva en la literatura previa de GQW.
Construcción del Cronograma (Schedule): Utilizando estos puntos muestreados, el algoritmo construye una tasa de salto continua, suave y dependiente del tiempo $\Gamma(t)$ mediante interpolación. Este cronograma está diseñado para equilibrar el Hamiltoniano de mezcla $H_M$ y el Hamiltoniano de costo $H_C$ , maximizando la transferencia de amplitud desde los estados de alta energía hacia los de baja energía.

2. Ejecución Cuántica Online

Una vez determinado el cronograma de salto $\Gamma(t)$ , la computadora cuántica ejecuta una caminata cuántica de tiempo continuo (CTQW) guiada por este cronograma.

Hamiltoniano: El sistema evoluciona bajo el Hamiltoniano dependiente del tiempo $H(t) = \Gamma(t)H_M + H_C$ .
Implementación de Circuito: Para ejecutar esto en computadoras cuánticas basadas en compuertas, los autores proponen una estrategia de discretización de dos niveles. El intervalo de tiempo se divide primero en periodos donde la tasa de salto se interpola linealmente. Estos periodos se subdividen posteriormente para aplicar la descomposición de Trotter-Suzuki. Esto resulta en un circuito cuántico con capas alternas de unitarias de costo ( $U_C$ ) y de mezcla ( $U_M$ ), con una estructura similar a QAOA pero con parámetros determinados a priori en lugar de optimizados.
Medición: El algoritmo realiza un único conjunto de mediciones en la base computacional. Se selecciona la mejor solución encontrada entre las mediciones.

Contribuciones Clave

Marco No Variacional: SamBa–GQW es un algoritmo de "un solo paso" (one-shot) que no requiere un optimizador clásico para ajustar los parámetros cuánticos, evitando así las mesetas estériles y el escalado exponencial asociado con los bucles variacionales.
Muestreo Eficiente: El artículo demuestra que un número polinomial de muestras ( $q \approx n^2$ ) es suficiente para aproximar la tasa de salto óptima, evitando el costo exponencial del análisis espectral exacto.
Implementación de Circuito: Los autores proporcionan un método concreto para discretizar la evolución de tiempo continuo en un circuito cuántico basado en compuertas con profundidad polinomial respecto al número de cúbits y muestras.
Amplia Aplicabilidad: El algoritmo es probado en una diversidad de problemas, incluyendo:
- Problemas Cuadráticos: MaxCut, Conjunto Independiente Máximo (MIS) y Optimización de Portafolio (con restricciones).
- Problemas de Orden Superior: Secuencias Binarias de Baja Autocorrelación (LABS), MAX-k-SAT y una reformulación cuártica del Problema del Viajante (TSP).

Resultados

Los autores presentan simulaciones numéricas (tanto de Hamiltoniano como basadas en circuitos) para tamaños de problema de hasta $n=30$ cúbits.

Desempeño: SamBa–GQW encuentra consistentemente soluciones aproximadas de alta calidad. Para muchas instancias, la probabilidad de medir la solución óptima o soluciones dentro del top 5% de los rankings es muy alta.
Comparación con GQW: Al compararse con el GQW variacional (que utiliza un optimizador clásico para ajustar una curva de Bézier), SamBa–GQW logra ratios de aproximación comparables. Crucialmente, SamBa–GQW reduce el tiempo de ejecución al menos en un orden de magnitud porque evita el bucle de optimización clásica iterativa.
Comparación con QAOA:
- Circuitos de Baja Profundidad (Régimen NISQ): Cuando se restringe a profundidades de circuito bajas (por ejemplo, $p < 20$ ), QAOA generalmente supera a SamBa–GQW, particularmente para MaxCut pesado y MIS. Esto se atribuye a la capacidad de QAOA de usar la optimización clásica para ajustar finamente los parámetros para instancias específicas del problema.
- Circuitos Profundos (Más allá de NISQ): Cuando se permite aumentar la profundidad del circuito (hasta $p \approx 100$ o más), SamBa–GQW se desempeña "a la par" con QAOA en términos de ratios de aproximación. El artículo señala que SamBa–GQW requiere circuitos más profundos para alcanzar su máximo rendimiento en comparación con la saturación temprana de QAOA, pero logra una calidad final similar sin la sobrecarga variacional.
Escalabilidad: El algoritmo escala razonablemente bien con el número de cúbits. Para problemas como MaxCut y MIS, el ratio de aproximación permanece alto incluso cuando $n$ aumenta, siempre que se ajusten adecuadamente el parámetro de muestreo $q$ y la profundidad del circuito.

Significancia y Reivindicaciones

El artículo posiciona a SamBa–GQW como un heurístico prometedor para abordar problemas de optimización combinatoria más allá del régimen NISQ. Su principal significancia radica en ofrecer una alternativa no variacional que es robusta contra las mesetas estériles y no sufre el escalado exponencial de las iteraciones de optimización clásica encontradas en los métodos variacionales.

Los autores afirman que, si bien SamBa–ＧW puede requerir circuitos más profundos que QAOA para lograr resultados óptimos, ofrece un intercambio favorable entre la calidad de la solución y el costo computacional al eliminar la necesidad de evaluaciones repetidas del circuito cuántico durante un bucle de optimización clásica. El algoritmo se presenta no como una solución de tiempo polinomial para problemas NP-duros, sino como un método donde los recursos polinomiales (en términos de muestreo y profundidad de circuito) pueden ser suficientes para guiar eficazmente la búsqueda hacia estados de alta calidad. El trabajo sugiere que, a medida que el hardware cuántico mejore y los circuitos más profundos sean factibles, SamBa–GQW podría servir como un enfoque competitivo y escalable para la optimización combinatoria a gran escala.