Comparing Qubit and Qudit Encodings for EV Charging and Trip Assignment Problems

Este artículo demuestra que el uso de codificaciones de qudits (enteros) en lugar de las codificaciones convencionales de qubits (binarios) para algoritmos cuánticos variacionales reduce significativamente los requisitos de recursos y el tiempo de ejecución de la simulación, al tiempo que logra un rendimiento de optimización comparable o superior en problemas realistas de gestión de flotas de vehículos eléctricos.

Lo esencial

Imagina que eres el gerente de una pequeña flota de taxis eléctricos. Tienes dos grandes tareas que realizar cada día:

1. Cargar los coches: Necesitas decidir cuándo enchufarlos (para cargar) o permitir que devuelvan energía a la red (descargar) para ahorrar dinero.
2. Asignar viajes: Necesitas decidir qué coche realiza el viaje de qué cliente.

Esto es un rompecabezas. Si asignas el coche incorrecto a un viaje, o lo cargas en el momento equivocado, podrías quedarte sin batería o infringir las reglas de la red eléctrica. Resolver este rompecabezas perfectamente es muy difícil para las computadoras, especialmente cuando se añaden las reglas de la física cuántica a la mezcla.

Este artículo es un informe de investigadores del Honda Research Institute y de la Universidad de Leiden, quienes se plantearon una pregunta sencilla: "¿Importa cómo traducimos este rompecabezas al lenguaje de una computadora cuántica?"

Ellos probaron dos "idiomas" (codificaciones) diferentes para ver cuál ayuda a la computadora cuántica a resolver el problema más rápido y mejor.

Los Dos Idiomas: "Qubits" vs. "Qudits"

Para entender su experimento, imagina que estás tratando de describir una lista de viajes a un robot.

1. La Vieja Forma: El Idioma "Qubit" (El Interruptor Binario)
Piensa en un interruptor de luz. Está o bien ENCENDIDO o bien APAGADO.

• En este método, los investigadores utilizaron un interruptor de luz separado para cada posible combinación de un coche y un viaje.
• Si tienes 3 coches y 2 viajes, necesitas 6 interruptores. Si un interruptor está ENCENDIDO, significa "El Coche 1 realiza el Viaje A". Si está APAGADO, no lo hace.
• El Problema: Esto crea una habitación masiva y desordenada llena de interruptores. La computadora tiene que verificar millones de combinaciones, la mayoría de las cuales son sin sentido (como "El Coche 1 realiza el Viaje A" Y "El Coche 2 realiza el Viaje A" al mismo tiempo). La computadora pierde tiempo verificando estos escenarios imposibles.

2. La Nueva Forma: El Idioma "Qudit" (El Dial de Múltiples Posiciones)
Piensa en un regulador de intensidad o en un dial que puede apuntar a muchos números, no solo a 0 o 1.

• En este método, en lugar de usar muchos interruptores, utilizaron un dial para cada viaje.
• Si el dial apunta a "1", significa "El Coche 1 realiza este viaje". Si apunta a "2", significa "El Coche 2". Si apunta a "0", significa "Ningún coche realiza este viaje".
• El Beneficio: Esto es mucho más directo. No necesitas verificar si dos coches están peleando por el mismo viaje; el dial físicamente no puede apuntar a dos coches a la vez. Reduce el "espacio" que la computadora tiene que explorar.

El Experimento: Una Carrera Contra el Tiempo

Los investigadores ejecutaron una simulación de su computadora cuántica (una "simulación de vector de estado", que es como una práctica perfecta y libre de ruido) para ver cómo rendían estos dos idiomas. Configuraron muchos escenarios aleatorios con diferentes números de coches, viajes y franjas horarias.

Esto es lo que encontraron:

• El Espacio de Búsqueda se Redujo: El método "Qudit" (dial) redujo el tamaño del espacio de búsqueda de forma exponencial. Imagina tratar de encontrar una aguja en un pajar. El método Qubit te dio un pajar del tamaño de una montaña. El método Qudit te dio un pajar del tamaño de una caja de zapatos.
• Resultados Más Rápidos: Debido a que la "caja de zapatos" era mucho más pequeña, la simulación se ejecutó mucho más rápido. El método Qudit tardó significativamente menos tiempo en encontrar una solución.
• Mejor Calidad: Sorprendentemente, el método Qudit no solo corrió más rápido; encontró soluciones mejores o iguales. Las soluciones que encontró estaban más cerca de la respuesta perfecta, y los resultados fueron más consistentes (menos "inestables" o aleatorios).
• El Problema "Profundo": Intentaron hacer que la computadora cuántica "pensara" más duro añadiendo más capas (profundidad) al algoritmo. Por lo general, pensar más duro ayuda. Pero aquí, el método Qubit se confundió y rindió peor a medida que se hacía más profundo, probablemente porque tenía demasiadas variables que manejar y la computadora dejó de optimizar demasiado pronto. El método Qudit se mantuvo estable y robusto, incluso a medida que el problema se volvía más complejo.

La Conclusión

El artículo concluye que para problemas que involucran la programación y asignación de cosas (como coches eléctricos a viajes), utilizar el enfoque Qudit (dial) es una elección mucho más inteligente que el enfoque tradicional Qubit (interruptor).

Es como hacer las maletas para un viaje:

• Qubit: Traes una maleta llena de calcetines individuales, uno por uno, e intentas meterlos en una caja. Pierdes espacio y tiempo.
• Qudit: Traes un solo paquete de calcetines doblados ordenadamente. Cabe perfectamente, ocupa menos espacio y puedes agarrarlo instantáneamente.

Los investigadores sugieren que para problemas de programación del mundo real con muchas opciones, el uso de estos "diales cuánticos de múltiples valores" (qudits) es un camino práctico y eficiente hacia adelante, ahorrando tanto tiempo como potencia de computación.

Resumen técnico

Resumen Técnico: Comparación de Codificaciones de Qubit y Qudit para Problemas de Carga de Vehículos Eléctricos y Asignación de Viajes

Planteamiento del Problema
El artículo aborda el problema de optimización con restricciones de gestionar una flota de vehículos eléctricos (VE). Esto implica dos procesos de decisión acoplados: programar la carga bidireccional (o unidireccional) de $N_{EV}$ vehículos durante un horizonte de tiempo discreto $T$, y asignar estos vehículos a $R$ solicitudes de viaje de clientes. El objetivo es minimizar los costos de carga mientras se satisfacen estrictas restricciones operativas, incluidos los límites del estado de carga (SOC) de la batería, las superposiciones de viajes, los límites de potencia de la red y el requisito de que un vehículo no puede cargar mientras realiza un viaje.

El desafío central investigado es cómo la elección de la codificación para las variables de asignación de viajes afecta los requisitos de recursos y el comportamiento de optimización de los Algoritmos Cuánticos Variacionales (VQA), específicamente el Algoritmo Cuántico Aproximado de Optimización (QAOA). Los autores comparan dos representaciones distintas:

1. Codificación Binaria (Qubit): Utiliza una variable binaria ($r_{n,i} \in \{0,1\}$) para cada par vehículo-viaje. Esto requiere restricciones explícitas para garantizar que cada viaje sea atendido por como máximo un vehículo y que los viajes superpuestos no se asignen al mismo vehículo.
2. Codificación Entera (Qudit): Utiliza una variable entera ($q_i \in \{0, \dots, N_{EV}\}$) por viaje, donde el valor especifica directamente el vehículo asignado (o un estado no atendido). Esta codificación satisface inherentemente la restricción de "un vehículo por viaje", eliminando la necesidad de restricciones binarias explícitas sobre la asignación.

Metodología
Los autores formulan el problema utilizando QAOA. Ambas codificaciones utilizan variables qudit para los niveles de potencia de carga ($l_{n,t}$), pero difieren en la base computacional para las asignaciones de viajes.

• Construcción del Hamiltoniano: Las funciones de costo clásicas y las restricciones se promueven a operadores diagonales en la base computacional. Las restricciones (por ejemplo, límites de SOC, sin carga durante los viajes) se hacen cumplir mediante términos de penalización no lineales añadidos al Hamiltoniano de costo.
• Simulación: El estudio emplea simulaciones exactas de vectores de estado para evaluar el rendimiento de los algoritmos. Para imitar las limitaciones realistas del hardware, los valores esperados de la función de costo se estiman utilizando un número finito de disparos de medición ($M=256$) en lugar de un cálculo exacto.
• Optimización: Un optimizador clásico (método de Powell) minimiza la función de costo variando los parámetros de QAOA ($\gamma, \beta$). El estudio ejecuta 10 instancias aleatorias para cada clase de problema, con 10 ejecuciones de optimización por instancia, utilizando un presupuesto fijo de 200 iteraciones internas del optimizador.
• Casos de Prueba: Se analizan dos clases de problemas:
  • Carga bidireccional: 3 VE, 2 pasos de tiempo, 2 viajes, 3 niveles de carga ($d=3$).
  • Carga unidireccional: 2 VE, 3 pasos de tiempo, viajes variables ($R=2,3,4$), 2 niveles de carga ($d=2$).

Contribuciones y Resultados Clave
El artículo proporciona un análisis comparativo de las dos codificaciones a través de varias métricas:

1. Reducción del Espacio de Hilbert: La codificación entera (qudit) reduce exponencialmente la dimensión del espacio de Hilbert en comparación con la codificación binaria (qubit). La relación de configuraciones viene dada por $N_{int}/N_{bin} \approx 2^{-R N_{EV} + R \log_2(N_{EV}+1)}$. Para las instancias probadas, esto resulta en una reducción del espacio de búsqueda de decenas de miles a unos pocos miles de estados.
2. Rendimiento de Optimización:
   • Brecha de Energía Media: La codificación qudit logra consistentemente una brecha de energía media comparable o ligeramente mejor que la codificación qubit.
   • Varianza: Los resultados qudit exhiben una varianza significativamente menor en las brechas de energía a través de diferentes ejecuciones.
   • Probabilidad de Éxito: La fracción de ejecuciones que encuentran el óptimo global y la fracción de estados factibles muestreados son generalmente más altas o más estables para la codificación qudit.
3. Tiempo de Ejecución y Convergencia:
   • Tiempo de Ejecución de Simulación: Debido al espacio de Hilbert más pequeño, la codificación qudit requiere tiempos de ejecución de simulación sustancialmente más cortos (lineales en la profundidad del circuito, pero con un coeficiente mucho menor).
   • Comportamiento de la Profundidad de Capas: A medida que aumenta la profundidad de QAOA ($L$), el rendimiento de la codificación qubit se degrada más significativamente que el de la codificación qudit. Los autores atribuyen esto al mayor número de parámetros variacionales que hacen que el paisaje de optimización sea más difícil de navegar dentro de un presupuesto fijo de iteraciones. La codificación qudit es más robusta frente a la terminación prematura del optimizador clásico.
4. Paisaje de Costos: Los paisajes de costos para la codificación qubit muestran una escala de energía mayor y frecuencias de oscilación más altas debido a la mayor fracción de estados no factibles (que incurren en altos costos de penalización) en comparación con la codificación qudit.

Significado y Afirmaciones
El artículo afirma que las codificaciones nativas de qudit ofrecen una vía práctica para resolver problemas de programación enteros y multivaluados en la optimización cuántica variacional. El significado principal radica en demostrar que representar variables discretas multivaluadas directamente mediante qudits, en lugar de expandirlos en qubits binarios, produce:

• Ahorros exponenciales de recursos en la dimensión del espacio de Hilbert.
• Reducción de la sobrecarga computacional en simulaciones clásicas (sirviendo como un proxy para la complejidad representacional).
• Mejora de la robustez en el proceso de optimización, particularmente en regímenes altamente restringidos donde las soluciones factibles son escasas.

Los autores señalan que, aunque el estudio utiliza simulaciones de vectores de estado, la representación compacta sugiere beneficios potenciales para las implementaciones en hardware al reducir la sobrecarga del manejo de restricciones y el mapeo de variables lógicas. Concluyen que para problemas de programación con restricciones, la codificación qudit es una opción superior que mantiene o mejora el rendimiento de optimización mientras reduce drásticamente los requisitos de recursos. El artículo sugiere modestamente que el trabajo futuro debería probar estas tendencias en instancias más grandes y en hardware cuántico real para verificar si las ventajas persisten más allá de la simulación.