Qubit-efficient quantum combinatorial optimization solver

1. El Problema

La optimización combinatoria es fundamental en áreas como la logística y la cadena de suministro. Aunque los algoritmos cuánticos prometen ventajas, su aplicación práctica actual se ve severamente limitada por la escasez de cúbits en los procesadores cuánticos actuales (NISQ).

• Limitación actual: Los métodos estándar (como QAOA) utilizan una mapeo de "un variable a un cúbit". Para problemas del mundo real con miles de variables, esto requiere miles de cúbits, algo que las computadoras actuales no poseen.
• Desafío del ruido: Añadir más cúbits físicos para escalar el problema generalmente introduce más ruido y errores, degradando la calidad de la solución, especialmente sin corrección de errores cuántica completa.
• Necesidad: Se requieren métodos que resuelvan problemas grandes utilizando significativamente menos cúbits físicos, manteniendo la calidad de la solución.

2. Metodología Propuesta

Los autores desarrollan un algoritmo variacional inspirado en QAOA (Quantum Approximate Optimization Algorithm) que utiliza una codificación eficiente en cúbits basada en un mapeo "muchos-a-uno".

A. Codificación Eficiente en Cúbits

En lugar de asignar un cúbit por variable, el método agrupa las $N$ variables binarias en $N/d$ grupos de $d$ variables cada uno.

• Estructura del estado: Las variables se almacenan en una función de onda entrelazada de $q = d + \log_2(N/d)$ cúbits.
  • Cúbits de datos ($d$): Almacenan los valores de las variables dentro de un grupo.
  • Cúbits de etiqueta ($\log_2(N/d)$): Indican qué grupo de variables está activo en los cúbits de datos.
• Funcionamiento: Una medición proyectiva de los cúbits de etiqueta selecciona un grupo específico, y los cúbits de datos revelan los valores de las $d$ variables de ese grupo. Esto permite representar $N$ variables con muy pocos cúbits físicos.

B. El Ansatz Variacional

Se propone un circuito cuántico parametrizado que generaliza QAOA:

1. Hamiltoniano de Costo Dependiente del Estado: A diferencia de QAOA estándar donde el Hamiltoniano de costo es fijo, aquí el Hamiltoniano $\hat{H}[\psi_{p-1}]$ en la capa $p$ depende de la función de onda de la capa anterior. Esto se debe a que las interacciones entre variables de diferentes grupos (etiquetas distintas) se tratan mediante un acoplamiento de campo medio (promedio) basado en las mediciones previas.
2. Capas Alternas: El circuito alterna entre:
   • Un mezclador de campo transversal ($e^{-i\beta_p \hat{H}_x}$).
   • Un separador de fase dependiente del estado ($e^{-i\gamma_p \hat{H}[\psi_{p-1}]}$).
3. Romper la Simetría $Z_2$: El ansatz original sufría de una simetría que impedía alcanzar el costo del estado fundamental. Los autores introducen una modificación con un término de sesgo unario ($\hat{H}_z$) para romper esta simetría y permitir la convergencia a la solución óptima.

C. Estimación del Costo

Dado que no se miden todas las variables simultáneamente, el costo se estima mediante:

• Condicionalidad: Para variables dentro del mismo grupo, se calculan correlaciones directas post-seleccionando las mediciones de la etiqueta correspondiente.
• Campo Medio: Para variables de grupos diferentes, se estiman como el producto de sus valores esperados individuales ($\bar{z}_i \times \bar{z}_j$).

3. Contribuciones Clave

1. Algoritmo Escalable: Demostración de que es posible resolver problemas de optimización con miles de variables utilizando un número polinomial de cúbits (mucho menor que $N$), reduciendo la sobrecarga computacional clásica en comparación con métodos de descomposición de circuitos.
2. Agrupación de Parámetros (Parameter Concentration): Los autores descubren y validan que los parámetros óptimos del ansatz para problemas de vidrio de espín Sherrington-Kirkpatrick (SK) tienden a concentrarse. Esto significa que los parámetros óptimos encontrados para un tamaño de problema pequeño (ej. $N=64$) pueden reutilizarse y escalarse para problemas mucho más grandes ($N=128, 256, \dots$) con un simple ajuste de escala, reduciendo drásticamente el costo de la búsqueda de parámetros clásica.
3. Validación Experimental: Ejecución exitosa del algoritmo en el chip superconductor Ankaa™-9Q-3 de Rigetti para un caso pequeño ($N=4$), mostrando una alta correlación entre la simulación sin ruido y los datos experimentales.
4. Ansatz Adaptativo: Propuesta de una versión adaptativa (similar a ADAPT-QAOA) que construye el circuito capa por capa seleccionando los mejores operadores mezcladores, logrando mejores resultados que la descomposición de problemas naive.

4. Resultados

• Rendimiento en Modelos SK: Se probaron ensembles de problemas Sherrington-Kirkpatrick con $N=64$ y $N=128$.
  • El algoritmo con $d=2$ o $d=4$ (usando muy pocos cúbits) logró ratios de aproximación comparables o incluso superiores a QAOA estándar con $d=N$ (un cúbit por variable) pero con menos capas de profundidad.
  • Por ejemplo, un ansatz con $d=2$ y profundidad $p=3$ superó a un ansatz estándar con $d=N$ y $p=1$, usando hasta 9 veces menos cúbits.
• Escalabilidad de Parámetros: Se demostró que los parámetros óptimos para $N=64$ pueden predecir el rendimiento para $N=128, 256$ y $512$ mediante una escala de $\gamma \propto d/N^{3/2}$, manteniendo ratios de aproximación altos sin necesidad de re-optimizar desde cero.
• Entrelazamiento: El estado objetivo es una función de onda entrelazada (ley de volumen), lo cual es crucial para la ventaja cuántica y la no simulabilidad clásica, a diferencia de los estados producto en QAOA estándar.

5. Significado e Impacto

• Utilidad Cuántica a Corto Plazo: Este enfoque es ideal para la era NISQ (Noisy Intermediate-Scale Quantum), permitiendo abordar problemas de tamaño realista (miles de variables) en dispositivos actuales con decenas de cúbits.
• Preparación para Futuro: Es relevante para futuras computadoras cuánticas tolerantes a fallos de pequeña escala, donde el número de cúbits lógicos podría ser limitado.
• Eficiencia de Recursos: Reduce la necesidad de corrección de errores masiva al minimizar el número de cúbits físicos requeridos, mitigando así el impacto del ruido del hardware.
• Generalización: El método no se limita a modelos de vidrio de espín; se puede extender a otros problemas de optimización combinatoria (QUBO, MaxCut) y aplicaciones de aprendizaje automático cuántico.

En resumen, el paper presenta un avance significativo al demostrar que la eficiencia en el uso de cúbits no sacrifica necesariamente la calidad de la solución, ofreciendo una vía práctica para la utilidad cuántica en optimización antes de la llegada de computadoras cuánticas a gran escala.