⚛️ quantum physics

Quantum WalkScore: Benchmarking Quantum Computers on the Graph Nodefinding Problem

Este artículo introduce Quantum WalkScore (QWS), un benchmark escalable y orientado a aplicaciones que evalúa el rendimiento de las computadoras cuánticas NISQ y de las futuras computadoras tolerantes a fallos mediante la medición de su capacidad para resolver el problema de búsqueda de nodos en grafos utilizando caminatas cuánticas de tiempo discreto y amplificación de amplitud, validado tanto mediante simulaciones como mediante experimentos en procesadores cuánticos de IBM.

Autores originales: Noé Olivier, Michel Nowak

Publicado 2026-09-18

📖 5 min de lectura🧠 Análisis profundo

CC BY 4.0

Autores originales: Noé Olivier, Michel Nowak

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 la búsqueda de construir máquinas que puedan resolver problemas más allá del alcance de las supercomputadoras actuales, los científicos compiten por desarrollar computadoras cuánticas. Estos dispositivos no dependen de los simples interruptores de encendido y apagado de los bits clásicos, sino que utilizan bits cuánticos, o qubits, que pueden existir en múltiples estados a la vez. Esta propiedad única les permite explorar vastas posibilidades simultáneamente. Sin embargo, construir una máquina que pueda mantener de manera confiable estos frágiles estados cuánticos es increíblemente difícil. Los dispositivos actuales suelen estar plagados de ruido y errores, lo que lleva a los investigadores a plantearse una pregunta crítica: ¿cómo sabemos si una computadora cuántica está funcionando realmente y qué tan buena es para resolver tareas del mundo real? Para responder a esto, la comunidad científica necesita algo más que una lista de tasas de error; necesita una prueba práctica que mida si una máquina puede navegar con éxito un problema complejo.

Un equipo de investigadores en CortAIx Labs en Francia ha propuesto una nueva forma de medir esta capacidad, llamada Quantum WalkScore. En lugar de probar propiedades matemáticas abstractas, su prueba de rendimiento pide a la computadora que realice una tarea específica y útil: encontrar un objetivo oculto dentro de una red. Imagine a un viajero tratando de encontrar una ciudad específica en un vasto mapa de carreteras conectadas. Una computadora clásica revisaría las carreteras una por una, pero una computadora cuántica puede explorar muchos caminos a la vez. Los investigadores se centraron en dos herramientas poderosas que las computadoras cuánticas utilizan para este tipo de búsqueda: un método llamado caminata cuántica de tiempo discreto, que actúa como una forma sofisticada de moverse a través de la red, y una técnica llamada amplificación de amplitud, que aumenta las probabilidades de encontrar la respuesta correcta. Al combinar estas herramientas, el equipo creó una prueba que mide qué tan grande puede ser una red que una computadora cuántica pueda buscar antes de que el ruido en la máquina provoque su fallo.

La prueba de rendimiento está diseñada para ser escalable, lo que significa que puede comenzar con una red muy pequeña y crecer más grande y compleja a medida que el hardware mejora. Los investigadores probaron este protocolo en dos tipos de formas de red: un anillo simple, donde cada punto se conecta con dos vecinos, y una cuadrícula más compleja que se envuelve sobre sí misma, como la superficie de una dona. Definieron un objetivo claro: la computadora debe encontrar el objetivo oculto con una tasa de éxito superior a la que se esperaría por pura suerte. Si la computadora tiene éxito, la prueba pasa a una versión ligeramente más grande o más difícil del problema. La puntuación final es simplemente el tamaño de la red más grande que la computadora logró resolver antes de que ya no pudiera encontrar el objetivo de manera confiable. Este enfoque ofrece un número concreto que cualquiera puede entender, representando el límite práctico de la capacidad actual de la máquina.

Para ver cómo funciona esto en la práctica, los investigadores ejecutaron sus pruebas en varias generaciones de procesadores cuánticos reales proporcionados por IBM, incluyendo modelos llamados Heron y Nighthawk. También realizaron simulaciones en una computadora perfecta y sin ruido para ver cómo deberían ser los resultados en un mundo ideal. Las simulaciones mostraron que, con la configuración adecuada, los algoritmos cuánticos podrían teóricamente resolver problemas muy grandes, encontrando el objetivo con alta confianza. Sin embargo, cuando el equipo ejecutó las mismas pruebas en las máquinas físicas reales, los resultados fueron mucho más modestos. El ruido y los errores inherentes al hardware actual significaron que las computadoras solo podían resolver con éxito redes muy pequeñas. Para las redes con forma de anillo, las máquinas con mejor desempeño lograron encontrar el objetivo en redes de un tamaño pequeño específico, pero a medida que la red crecía, la tasa de éxito caía al nivel de un intento al azar.

El estudio destaca una brecha significativa entre lo que los algoritmos cuánticos pueden hacer en teoría y lo que el hardware actual realmente puede lograr. Los investigadores encontraron que la complejidad del circuito requerido para ejecutar la búsqueda crece rápidamente a medida que el problema se vuelve más grande. En las máquinas que probaron, los circuitos que eran demasiado profundos o complejos se vieron abrumados por los errores, causando que la información cuántica se degradara antes de que se pudiera encontrar la respuesta. Incluso con los procesadores más avanzados disponibles al momento del estudio, el equipo solo pudo demostrar una prueba de concepto, probando que el método funciona pero también revelando cuánto debe mejorar el hardware. Los resultados sugieren que, si bien las herramientas matemáticas están listas, las máquinas físicas aún se encuentran en las primeras etapas de ser capaces de manejar las tareas exigentes requeridas para aplicaciones del mundo real como la logística o la búsqueda en bases de datos.

Este nuevo benchmark, Quantum WalkScore, ofrece una forma clara y honesta de rastrear el progreso. No depende del potencial teórico o de simulaciones idealizadas, sino que mide el rendimiento real de la máquina de una manera controlada y repetible. Al establecer un estándar que requiere que la computadora supere el azar en un problema de grafos específico, los investigadores proporcionan un punto de referencia para todo el campo. A medida que el hardware cuántico continúa evolucionando, volviéndose más estable y menos propenso a errores, esta puntuación aumentará naturalmente. El trabajo sirve como un recordatorio de que el camino hacia la computación cuántica poderosa es un ascenso gradual, donde cada paso hacia arriba en el rendimiento debe ser verificado mediante la resolución exitosa de un problema que anteriormente estaba fuera del alcance. Los investigadores han trazado un mapa para este viaje, mostrando exactamente dónde se encuentran las máquinas hoy y qué deben superar para alcanzar el futuro.

Resumen Técnico: Quantum WalkScore (QWS)

Definición del Problema
El artículo aborda la necesidad de evaluaciones de rendimiento (benchmarks) orientadas a aplicaciones para evaluar la madurez de las computadoras cuánticas de Escala Intermedia con Ruido (NISQ) y las futuras computadoras cuánticas tolerantes a fallos. Mientras que los benchmarks existentes se centran en la fidelidad de las puertas físicas o el muestreo de circuitos aleatorios, existe una escasez de evaluaciones que utilicen rutinas cuánticas prometedoras, específicamente las Caminatas Cuánticas de Tiempo Discreto (DTQW) y la Amplificación de Amplitud Cuántica (AA), para resolver problemas de grafos prácticos. Los autores se centran en el problema de búsqueda de nodos en grafos: identificar un nodo objetivo específico "marcado" $v_t$ dentro de un grafo no dirigido partiendo de un nodo origen $v_0$ . Este problema sirve como un bloque de construcción fundamental para aplicaciones del mundo real como el enrutamiento de telecomunicaciones, la búsqueda en bases de datos y el análisis de redes complejas.

Metodología: El Protocolo Quantum WalkScore (QWS)
Los autores proponen el Quantum WalkScore (QWS), un protocolo de evaluación escalable diseñado para medir el tamaño de problema más grande que una computadora cuántica puede resolver con éxito.

Familias de Grafos: El benchmark utiliza dos topologías de grafos específicas para equilibrar la simplicidad, la escalabilidad y la aplicabilidad al hardware:
1. Grafos de Ciclo: Estructuras 1D con $2^n$ nodos, donde cada nodo se conecta con dos vecinos.
2. Grafos de Toro 2D: Estructuras 2D con $2^n \times 2^n$ nodos, donde cada nodo se conecta con cuatro vecinos (condiciones de contorno periódicas).
Instancia del Problema: Definida por $(n, d)$ , donde $n$ es el número de qubits y $d$ es la distancia (distancia de los bordes del camino más corto) entre el nodo origen y el nodo objetivo.
Rutina Algorítmica:
1. Inicialización: El sistema se inicializa en el estado $|v_0\rangle$ .
2. Caminata Cuántica de Tiempo Discreto (DTQW): El caminante evoluciona durante $num\_w$ pasos. El protocolo requiere que $num\_w \ge d$ y $num\_w \equiv d \pmod 2$ para asegurar la alcanzabilidad. Se utiliza una moneda de Hadamard para una caminata no sesgada.
3. Amplificación de Amplitud (AA): La rutina DTQW se integra dentro de un marco de AA (Brassard et al.) para aumentar la probabilidad de medir el estado objetivo. Esto implica $num\_aa$ iteraciones de reflexión sobre el estado objetivo y el estado inicial.
4. Medición: La probabilidad de éxito $p_{exp}$ se mide como la probabilidad de observar el estado del nodo objetivo.
Criterios de Puntuación:
- Probabilidad de Umbral ( $p^*$ ): Se define un umbral dinámico para asegurar que el éxito sea significemente mejor que el azar. Para una distancia $d \le 2$ , $p^* = 1/3$ . Para $d > 2$ , $p^* = 1/5 + 1/2^d$ .
- Métrica: La probabilidad de éxito se promedia sobre múltiples lotes (4 lotes de 1000 disparos/shots) y múltiples instancias de nodos objetivo (2 para ciclos, 4 para toro).
- Puntuación QWS: La puntuación es el tamaño de problema más grande $(n, d)$ para el cual la probabilidad de éxito medida supera $p^*$ antes del primer fallo. La puntuación se calcula como $QWS_{cycle} = 2^{e_n-1} + e_d$ y $QWS_{torus} = 2^{e_n} + e_d$ , donde $(e_n, e_d)$ es la última instancia exitosa.

Contribuciones Clave

Diseño del Protocolo: Introducción de un protocolo de evaluación completo y orientado a aplicaciones que integra DTQW y AA, dos rutinas críticas para futuros algoritmos cuánticos.
Escalabilidad y Reproducibilidad: El protocolo está diseñado para ser aplicable a cualquier computadora cuántica basada en puertas, con parámetros experimentales estandarizados (conteo de disparos, loteo) y parámetros algorítmicos flexibles ( $num\_w$ , $num\_aa$ ) dejados al usuario final para su optimización.
Análisis Teórico y Empírico: El artículo proporciona garantías teóricas para la existencia de parámetros que pueden resolver teóricamente cualquier tamaño de problema, junto con una estimación detallada de recursos (escalado de profundidad de circuito) tanto para implementaciones algorítmicas como de hardware nativo.
Validación Experimental: El protocolo se ejecuta en tres generaciones de procesadores cuánticos de IBM (Heron r2, Heron r3 y Nighthawk r1), proporcionando una evaluación de prueba de concepto de las capacidades actuales del hardware.

Resultos

Simulaciones sin Ruido: Las simulaciones en una computadora cuántica ideal demuestran que el benchmark es resoluble para tamaños de problema grandes. En el escenario "suff-perf" (minimizando las iteraciones de AA), las probabilidades de éxito se mantienen cercanas al umbral. En el escenario "best-perf", las probabilidades de éxito se acercan a 1, aunque esto requiere profundidades de circuito más altas.
Escalado de la Profundidad del Circuito: La profundidad algorítmica teórica escala como $O(nd)$. Sin embargo, al transponerse a la arquitectura Heron de IBM, la profundidad nativa escala como $O(n^{3.45}d)$ para grafos de ciclo y $O(n^{2.2}d)$ para grafos de toro 2D, resaltando la sobrecarga significativa del mapeo de hardware.
Rendimiento Experimental en Hardware IBM:
- Los experimentos en el procesador ibm_kingston (Heron r2) mostraron que las probabilidades de éxito caen rápidamente a medida que aumenta el tamaño del problema debido al ruido y la decoherencia.
- El sistema pasó con éxito el umbral solo hasta el tamaño de problema (3, 1). La probabilidad de éxito cayó drásticamente a resultados similares a los de una elección al azar para los tamaños subsiguientes, con la excepción del tamaño de problema (4, 1), que no constituyó una secuencia de éxito continua. En consecuencia, el Quantum WalkScore para grafos de ciclo se determinó en 5 bajo el escenario "suff-perf".
- Para instancias más grandes (por ejemplo, profundidad > 700 puertas), los resultados se degradaron a niveles indistinguibles de una elección al azar.
- Las comparaciones entre Heron r2, Heron r3 y Nighthawk r1 mostraron tendencias similares, con Heron r3 ofreciendo una precisión ligeramente mejor, pero todas las arquitecturas actuales tuvieron dificultades con circuitos que excedían las ~1000 puertas.

Significancia y Reivindicaciones
El artículo afirma que QWS sirve como una herramienta necesaria para cerrar la breancia entre las métricas de hardware abstractas y el rendimiento de las aplicaciones prácticas. Al centrarse en el problema de búsqueda de nodos en grafos, evalúa directamente la capacidad de un hardware para ejecutar primitivas cuánticas esenciales (DTQW y AA) requeridas para tareas de optimización y búsqueda.

Los autores enfatizan que el benchmark resalta la interacción entre los parámetros algorítmicos y las limitaciones del hardware. Los resultados demuestran que, si bien el marco teórico permite resolver problemas grandes, los dispositivos NISQ actuales están limitados por la profundidad del circuito y la acumulación de errores. El artículo concluye que QWS proporciona una puntuación significativa e interpretable para rastrear la maduración de las computadoras cuánticas, distinguiendo el rendimiento entre dispositivos NISQ y futuros dispositivos de Computación Cuántica Tolerante a Fallos (FTQC). La modesta puntuación de 5 alcanzada en el hardware actual subraya los significativos desafíos tecnológicos que aún quedan por delante antes de que estos algoritmos puedan aplicarse a problemas prácticos de gran escala.

Resumen Técnico: Quantum WalkScore (QWS)

Más como este