Efficient Fourier-Based Linear Combination of Unitaries and Applications in Quantum Optimization

Este artículo propone un marco de Combinación Lineal de Unitarios (LCU) basado en Fourier y libre de ancillas que descompone eficientemente circuitos cuánticos complejos para tareas de optimización intercambiando la complejidad del circuito por una sobrecarga de muestreo polinómica, permitiendo así implementaciones amigables con el hardware de algoritmos como QAOA en dispositivos cuánticos de corto plazo mientras se mantienen garantías rigurosas de rendimiento.

Lo esencial

Imagina que estás intentando resolver un rompecabezas masivo e increíblemente complejo. En el mundo de la computación cuántica, este rompecabezas suele ser un problema de optimización: encontrar la mejor disposición posible de las cosas (como la ruta de entrega más eficiente o la mejor cartera de inversiones).

El artículo de Carrera Vázquez, Egger y Woerner introduce una nueva y astuta forma de abordar estos rompecabezas utilizando una computadora cuántica, específicamente una que aún se encuentra en sus etapas tempranas y "ruidosas" de desarrollo.

Aquí tienes el desglose de su idea utilizando analogías simples:

El Problema: El Circuito "Todos a Bordo"

Tradicionalmente, para resolver estos rompecabezas en una computadora cuántica, necesitas construir una máquina específica (un circuito cuántico) donde cada pieza individual del rompecabezas hable con cada otra pieza simultáneamente.

• La Analogía: Imagina intentar organizar una fiesta donde 100 invitados necesitan estrecharse la mano con todos los demás invitados exactamente al mismo tiempo. En una habitación real, esto es imposible; las personas chocarían entre sí, la habitación estaría demasiado llena y el evento fracasaría.
• La Realidad Cuántica: En términos cuánticos, esto requiere "conectividad total" y circuitos muy profundos y complejos. Las computadoras cuánticas actuales son como habitaciones pequeñas; no pueden manejar tantos apretones de manos simultáneos sin cometer errores (ruido).

La Solución: El Enfoque del "Libro de Recetas" (LCU)

Los autores proponen una nueva estrategia llamada Combinación Lineal de Unitarias (LCU). En lugar de intentar construir la máquina imposible de "todos a bordo", dividen la tarea compleja en una lista de tareas mucho más simples y pequeñas.

• La Analogía: En lugar de intentar hornear un pastel de bodas gigante e intrincado de una sola vez (lo cual podría colapsar), horneas 100 cupcakes simples y pequeños.
  • Algunos cupcakes son de vainilla, otros de chocolate, otros tienen chispas.
  • No necesitas un horno gigante; puedes hornearlos uno por uno o en pequeños lotes.
  • Después, mezclas los resultados en un plato. Si los mezclas en las proporciones correctas, el "sabor" del plato sabe exactamente igual al pastel de bodas gigante que querías.

En el artículo, estos "cupcakes" son circuitos cuánticos simples que solo requieren puertas de un solo qubit (una persona estrechando la mano con otra persona). La "mezcla" ocurre clásicamente (en una computadora regular) después de que se completa la parte cuántica.

El Secreto: La Transformada de Fourier

¿Cómo saben qué cupcakes hornear y cuánto de cada uno mezclar? Utilizan una herramienta matemática llamada Transformada de Fourier.

• La Analogía: Piensa en una canción compleja. Una transformada de Fourier descompone esa canción en notas individuales (frecuencias). Los autores utilizan esto para descomponer una "canción" cuántica compleja (el circuito) en una serie de notas simples y repetitivas (rotaciones de un solo qubit).
• El Resultado: Pueden expresar una operación cuántica muy difícil y compleja como una suma ponderada de operaciones muy fáciles.

El Intercambio: Calidad vs. Cantidad

Hay una trampa. Como no estás construyendo la máquina gigante directamente, tienes que realizar el experimento de los "cupcakes" muchas más veces para obtener una respuesta confiable.

• La Analogía: Si quieres conocer la altura promedio de una multitud, podrías medir a todos una vez (difícil de hacer si todos se mueven). O, podrías medir a 10 personas al azar, luego a 10 más, luego a 10 más, y tomar el promedio. Obtienes el mismo resultado, pero tienes que realizar más mediciones.
• La Afirmación del Artículo: Los autores muestran que, aunque necesitas ejecutar los circuitos simples más veces (una "sobrecarga de muestreo"), el número de ejecuciones adicionales es manejable (polinómico), no imposible. Este intercambio les permite ejecutar problemas en el hardware actual que de otro modo serían imposibles.

Aplicación en el Mundo Real: El "Subgrafo Más Denso"

Para demostrar que esto funciona, lo probaron en un problema específico llamado "Subgrafo k más denso" (encontrar el grupo de amigos más unido en una red social masiva).

1. Escala Pequeña: Lo simularon en un grafo de 12 nodos (como un vecindario pequeño) para mostrar que las matemáticas funcionan perfectamente.
2. Escala Grande: Lo ejecutaron en una computadora cuántica real de IBM con 106 qubits (un vecindario grande).
   • Encontraron con éxito soluciones de alta calidad.
   • Compararon dos métodos: uno que utilizaba una "penalización" (como una multa por romper reglas) y otro que utilizaba un "mezclador" especial (una danza que sigue las reglas).
   • El Hallazgo: El enfoque del "mezclador", combinado con su nuevo método de Fourier, funcionó excepcionalmente bien, encontrando soluciones que eran casi tan buenas como la mejor teórica, incluso en hardware real y ruidoso.

El Truco del "Sin Ayudante"

Por lo general, para mezclar estos "cupcakes" juntos, necesitas un qubit ayudante extra (un "ancilla") para llevar la cuenta de las matemáticas.

• La Innovación: Los autores desarrollaron una forma de hacer esto sin el ayudante.
• La Analogía: En lugar de necesitar un árbitro para decirte qué equipo anotó, simplemente dejas que los jugadores jueguen al azar y luego miras el marcador después para averiguar al ganador. Esto elimina una gran cantidad de complejidad del circuito cuántico, haciéndolo mucho más amigable para las máquinas de hoy.

Resumen

Este artículo presenta una nueva forma de ejecutar algoritmos cuánticos de optimización complejos en el hardware imperfecto de hoy. En lugar de intentar construir una máquina masiva y frágil que conecte todo con todo, dividen el problema en muchas piezas pequeñas y simples, ejecutan esas piezas y combinan los resultados clásicamente.

Demostraron que esto funciona resolviendo un problema de grafos difícil en una computadora cuántica de 106 qubits, mostrando que podemos resolver problemas más grandes y complejos hoy en día intercambiando la "complejidad del circuito" (qué tan difícil es construir la máquina) por la "sobrecarga de muestreo" (cuántas veces tenemos que ejecutar la prueba).

Resumen técnico

Resumen Técnico: Combinación Lineal de Unitarias Basada en Fourier Eficiente y Aplicaciones en Optimización Cuántica

Planteamiento del Problema
Los algoritmos de optimización cuántica, particularmente el Algoritmo Cuántico de Aproximación para Optimización (QAOA), enfrentan barreras significativas de implementación en hardware a corto plazo. La estructura matemática de los problemas de optimización, especialmente aquellos que involucran restricciones (por ejemplo, restricciones de cardinalidad), a menudo requiere circuitos cuánticos con alta conectividad (interacciones de todos a todos), profundidades de circuito elevadas y numerosas puertas de dos qubits. Estos requisitos frecuentemente exceden las capacidades de los procesadores cuánticos superconductores actuales. Si bien existen estrategias como el corte de circuitos o la aproximación de circuitos, estas a menudo intercambian la calidad de la solución por la complejidad o requieren una sobrecarga de muestreo sustancial sin garantías rigurosas de rendimiento.

Metodología
Los autores proponen un marco de Combinación Lineal de Unitarias (LCU) basado en Fourier diseñado para aproximar circuitos cuánticos complejos utilizando conjuntos de circuitos más simples y compatibles con el hardware. La metodología central implica:

1. LCU sin Qubit Auxiliar para Muestreo: A diferencia de las implementaciones estándar de LCU que utilizan un qubit auxiliar para implementar coherentemente una combinación lineal de unitarias (requiriendo operaciones controladas), este trabajo se centra en aplicaciones basadas en muestreo. Al eliminar los factores de signo asociados a la descomposición de cuasi-probabilidad (QPD) y reemplazar el qubit auxiliar con aleatoriedad clásica, el método elimina la necesidad de qubits auxiliares y puertas controladas. Esto transforma la implementación en una mezcla probabilística de circuitos más simples, donde la sobrecarga de muestreo se cuantifica mediante un factor $\Gamma$.
2. Descomposición de Fourier para Unitarias Diagonales: Para unitarias diagonales (comunes en funciones de costo y términos de penalización), los autores utilizan la transformada discreta de Fourier. Una unitaria objetivo $U_f(\gamma) = \sum_x e^{-i\gamma f(g(x))} |x\rangle\langle x|$ se descompone en una combinación lineal de unitarias más simples $V(\theta_j)$, que a menudo son simplemente capas de puertas $R_Z$ de un solo qubit. Los coeficientes se derivan de la transformada de Fourier de la función que define la unitaria. Este enfoque reemplaza interacciones complejas de múltiples qubits (por ejemplo, penalizaciones cuadráticas que requieren $O(n^2)$ puertas) con capas de un solo qubit, a costa de una sobrecarga de muestreo $\Gamma \le m+1$.
3. Extensión a Unitarias No Diagonales Invariantes bajo Permutación: El marco se generaliza a unitarias no diagonales, como el mezclador XY totalmente conectado utilizado para preservar las restricciones de peso de Hamming. Aprovechando la dualidad de Schur-Weyl y la teoría de representaciones de $SU(2)$, los autores expresan las unitarias invariantes bajo permutación como combinaciones lineales continuas de rotaciones colectivas de un solo qubit $R(g)^{\otimes n}$. Esto permite la implementación de mezcladores altamente no locales utilizando únicamente puertas de un solo qubit, con una sobrecarga de muestreo teórica acotada por $O(n^3)$.
4. Conexión con la Relajación Lagrangiana: El artículo establece un vínculo formal entre las penalizaciones cuánticas basadas en Fourier y la relajación lagrangiana clásica. Se demuestra que optimizar una sola rama de la descomposición LCU es equivalente a optimizar un parámetro lagrangiano, proporcionando una perspectiva unificada sobre el manejo de restricciones.

Contribuciones Clave

• Desarrollo del Marco: Introducción de un marco LCU basado en Fourier y sin qubit auxiliar que descompone amplias clases de unitarias diagonales y no diagonales en conjuntos de capas de puertas de un solo qubit.
• Eficiencia de Hardware: Demostración de que operadores complejos y conectados de todos a todos (como penalizaciones de cardinalidad y mezcladores XY) pueden ser reemplazados por circuitos significativamente más simples, intercambiando la profundidad y conectividad del circuito por una sobrecarga de muestreo polinómica.
• Garantías Teóricas: Provisión de límites de rendimiento rigurosos, mostrando que la probabilidad de muestrear cadenas de bits de alta calidad en el enfoque LCU está acotada inferiormente por la probabilidad coherente escalada por $1/\Gamma$. El artículo también conecta la optimización del Valor Condicional en Riesgo (CVaR) con estos límites.
• Validación de Escalabilidad: Aplicación exitosa del marco al problema del subgrafo más denso de $k$ vértices en instancias de hasta 106 qubits en hardware real de IBM Quantum, una escala previamente intratable para implementaciones totalmente coherentes de tales restricciones.

Resultados Experimentales
Los autores validaron su enfoque mediante simulaciones exactas de vectores de estado en una instancia de 12 nodos y experimentos a gran escala en un dispositivo de 106 qubits:

• Simulación de 12 Nodos: Las comparaciones entre QAOA totalmente coherente y el enfoque LCU basado en Fourier mostraron que, aunque los valores esperados brutos de los circuitos LCU eran más bajos (debido a la sobrecarga de muestreo), optimizar un único circuito base LCU (un ansatz variacional derivado del LCU) produjo la mayor probabilidad de muestrear soluciones óptimas, superando la línea base coherente en métricas específicas.
• Experimento de Hardware de 106 Nodos: En un grafo heavy-hex de 106 qubits (extendido mediante capas SWAP), se ejecutaron los enfoques LCU basados en penalizaciones y basados en mezcladores XY. Los resultados demostraron que la sobrecarga de muestreo práctica fue significativamente menor que los límites teóricos del peor caso ($\Gamma \approx 10^4$). El ansatz LCU de rama única encontró exitosamente soluciones de alta calidad (hasta 81 aristas en el subgrafo más denso) con probabilidades factibles que oscilaron entre el 2.7% y el 4.8%, indicando la viabilidad del método para problemas a gran escala.
• Mezclador XY vs. Penalización: El enfoque LCU basado en mezclador XY generalmente superó al enfoque basado en penalizaciones, particularmente al utilizar un único circuito base optimizado, lo que sugiere que los mezcladores que preservan restricciones son más efectivos cuando se combinan con esta descomposición.

Significado y Afirmaciones
El artículo afirma que el marco LCU basado en Fourier ofrece una ruta sistemática para extender el alcance práctico de la optimización cuántica a corto plazo. Al reemplazar operaciones coherentes complejas con combinaciones ponderadas de circuitos más simples, el método amplía el rango de instancias de problemas (específicamente aquellas con restricciones globales) que pueden ejecutarse en el hardware actual. Los autores enfatizan que este enfoque no requiere la reproducción exacta de la distribución objetivo, sino que se centra en muestrear soluciones de alta calidad, un objetivo bien adaptado para tareas de optimización. El trabajo sugiere que el intercambio entre la complejidad del circuito y la sobrecarga de muestreo es favorable, ya que los límites teóricos a menudo son holgados en la práctica, y el método permite el estudio de algoritmos e instancias de problemas que de otro modo estarían más allá de las capacidades del hardware. El artículo concluye que esto proporciona un principio de diseño flexible para algoritmos cuánticos más compatibles con el hardware, particularmente para el manejo de restricciones en QAOA.