Locally Acting Grover Mixers for Constraint-Preserving QAOA

Este artículo propone mezcladores de Grover de actuación local que reemplazan las costosas puertas de desfase multicontroladas globales en GM-QAOA por operaciones locales eficientes en subsistemas de cúbits disjuntos, logrando una convergencia comparable al método original mientras reduce significativamente la profundidad del circuito y el recuento de puertas para problemas como el de cobertura exacta y el del problema del viajante.

Lo esencial

Imagina que estás intentando resolver un rompecabezas masivo y complejo, como encontrar la ruta perfecta para que un vendedor viajero visite cada ciudad exactamente una vez. Tienes una computadora súper inteligente (una computadora cuántica) que puede probar millones de posibilidades a la vez. Sin embargo, esta computadora es actualmente un poco "ruidosa" y frágil, como una delicada escultura de cristal. Si le pides que haga algo demasiado complicado, se rompe o comete errores.

Este artículo presenta una nueva forma de guiar a esta frágil computadora para que pueda resolver estos rompecabezas mejor sin romperse.

El Problema: El libro de reglas "Global"

Los investigadores están trabajando con un método llamado QAOA (Algoritmo de Optimización Aproximada Cuántica). Piensa en el QAOA como un excursionista intentando encontrar el punto más bajo en un valle con niebla (la mejor solución). Para hacer esto, el excursionista necesita dos herramientas:

1. Un Mapa (Separación de Fase): Muestra al excursionista dónde están los puntos "malos".
2. Una Brújula (El Mezclador): Ayuda al excursionista a moverse para explorar nuevos puntos.

En la versión estándar de este método (llamada GM-QAOA), la "Brújula" es una Puerta Multicontrolada Global.

• La Analogía: Imagina intentar organizar una fiesta de baile para 100 personas. La Brújula estándar es como una regla gigante que dice: "Si todos en la sala están en una formación específica, entonces todos deben moverse juntos".
• El Problema: Para imponer esta regla en una computadora cuántica frágil, necesitas una máquina enorme y compleja que verifique a las 100 personas a la vez. Esta máquina es enorme, ocupa mucho espacio y es muy probable que se rompa (cometa errores) en las computadoras ruidosas de hoy.

La Solución: La Vigilancia Vecinal "Local"

Los autores, Minjin Choi, Dongkeun Lee y Junghee Ryu, proponen una forma más inteligente de construir esta Brújula. Ellos la llaman Mezcladores de Grover de Acción Local (Locally Acting Grover Mixers).

• La Analogía: En lugar de una regla gigante para toda la sala, dividen a las 100 personas en grupos más pequeños e independientes (como 10 mesas de 10 personas). Ahora, en lugar de una sola máquina gigante que verifica a todos, tienes 10 máquinas pequeñas y simples. Cada máquina solo verifica su propia mesa.
  • La máquina de la Mesa 1 dice: "Si todos en la Mesa 1 están en formación, muévanse".
  • La máquina de la Mesa 2 dice: "Si todos en la Mesa 2 están en formación, muévanse".
• El Resultado: Estas máquinas pequeñas son mucho más fáciles de construir, ocupan menos espacio y son mucho menos propensas a romperse. Crucialmente, debido a que los grupos son independientes, el resultado general es tan bueno como el de la máquina gigante.

Cómo lo Hicieron

Los investigadores se dieron cuenta de que para muchos rompecabezas, no es necesario forzar cada una de las reglas en la configuración inicial.

1. Codificación Parcial: En lugar de forzar a la computadora a comenzar con una solución que obedezca todas las reglas, permiten que comience con una solución que solo obedezca algunas reglas. Esto crea una "estructura de producto" (los grupos independientes mencionados anteriormente).
2. Mezcla Local: Luego utilizan su nuevo "Compás Local" para mezclar las cosas dentro de esos pequeños grupos.

La Prueba: Cobertura Exacta y el Vendedor Viajero

Probaron esta idea en dos rompecabezas famosos:

1. El Problema de Cobertura Exacta: Un rompecabezas lógico sobre cubrir elementos exactamente una vez.
2. El Problema del Vendedor Viajero (TSP): Encontrar la ruta más corta visitando múltiples ciudades.

Los Hallazgos:

• Misma Calidad: El nuevo método "Local" encontró soluciones tan buenas como el antiguo método "Global".
• Mucho Más Simple: El nuevo método utilizó un 87% menos de puertas de "entrelazamiento" complejas (las partes del circuito que son más propensas a romperse).
• El Intercambio: El nuevo método requiere que la computadora ejecute el circuito un poco más de veces para ajustar sus configuraciones (porque hay más perillas para girar). Sin embargo, dado que el circuito en sí es mucho más simple y menos propenso a romperse, este intercambio es una gran victoria para las computadoras ruidosas de hoy.

La Gran Conclusión

El artículo argumenta que para las computadoras cuánticas que tenemos en este momento (que son pequeñas y ruidosas), es mejor usar una estrategia "Local".

• Forma Antigua: Construir una máquina masiva y compleja que intenta hacer todo perfectamente pero se rompe fácilmente.
• Nueva Forma: Construir muchas máquinas pequeñas y simples que trabajan juntas. Pueden necesitar algunos intentos más para ajustar la configuración, pero son mucho más confiables y caben en el hardware actual.

En resumen, los autores encontraron una manera de hacer que los algoritmos cuánticos para problemas con restricciones sean más ligeros, más simples y más robustos, sin sacrificar la calidad de las respuestas que encuentran.

Resumen técnico

Resumen Técnico: Mezcladores de Grover de Actuación Local para QAOA con Preservación de Restricciones

Planteamiento del Problema
El Algoritmo de Optimización Aproximada Cuántica (QAOA) y su generalización, el Ansatz de Operador Alternante Cuántico (QAOA), son algoritmos variacionales prominentes para la optimización combinatoria. Un desafío crítico al aplicar estos algoritmos a problemas con restricciones es asegurar que la evolución cuántica permanezca confinada al subespacio factible definido por las restricciones del problema. El Grover Mixer QAOA (GM-QAOA) aborda esto empleando un operador de mezcla generado por el proyector sobre el estado inicial, lo que garantiza matemáticamente la preservación del subespacio factible.

Sin embargo, el mezclador GM-QAOA estándar requiere una puerta de desplazamiento de fase multi-controlada global que actúa sobre todos los $n$ cúbits. En dispositivos de escala intermedia con ruido (NISQ) de la era actual, que soportan nativamente solo operaciones de uno y dos cúbits, la descomposición de tal puerta global en puertas elementales resulta en una sobrecarga sustancial de circuitos. La profundidad y el recuento de puertas de estas descomposiciones crecen rápidamente con el número de cúbits, planteando una barrera significativa para la implementación práctica y aumentando la susceptibilidad al ruido del hardware.

Metodología
Los autores proponen una variante de "actuación local" del mezclador de Grover adaptada a estados iniciales que admiten una estructura de producto sobre subsistemas de cúbits disjuntos. Este enfoque aprovecha la observación de que, en muchos problemas combinatorios, las restricciones pueden codificarse parcialmente en la preparación del estado inicial, dejando las restricciones restantes para ser manejadas mediante términos de penalización en el Hamiltoniano de costo.

1. Estados Iniciales con Estructura de Producto: El método asume que el estado inicial $|\psi_0\rangle$ puede factorizarse como $|\psi_0\rangle = |\psi^{(1)}_0\rangle \otimes |\psi^{(2)}_0\rangle \otimes \dots \otimes |\psi^{(\ell)}_0\rangle$, donde cada $|\psi^{(j)}_0\rangle$ reside en un subconjunto disjunto de cúbits. Esta estructura se logra codificando solo un subconjunto de las restricciones del problema durante la preparación del estado.
2. Unitario de Mezcla Local: En lugar de un único mezclador global $e^{-i\beta |\psi_0\rangle\langle\psi_0|}$, el método propuesto construye la unitaria de mezcla como un producto tensorial de unitarias locales:
   $$U_M(\beta^{(1)}, \dots, \beta^{(\ell)}) = \bigotimes_{j=1}^{\ell} e^{-i\beta^{(j)} |\psi^{(j)}_0\rangle\langle\psi^{(j)}_0|}$$
   Cada unitaria local actúa independientemente en su respectivo subsistema utilizando una puerta de desplazamiento de fase multi-controlada confinada a dicho subsistema.
3. Parametrización: El ansatz introduce parámetros variacionales independientes $\beta^{(j)}$ para cada subsistema. Para un circuito de $p$ capas con $\ell$ subsistemas, el número total de parámetros de mezcla es $p\ell$, comparado con $p$ en el GM-QAOA original. Si bien esto aumenta la dimensión del paisaje de optimización clásica, reemplaza una enorme puerta global por $\ell$ puertas locales más pequeñas.

Contribuciones Clave

• Eficiencia del Circuito: La contribución principal es el reemplazo de la puerta de desplazamiento de fase multi-controlada global por $\ell$ operaciones locales. Esto reduce drásticamente el número de puertas entrelazantes (específicamente CNOTs) y la profundidad del circuito requerida para el paso de mezcla.
• Estrategia de Codificación de Restricciones: El artículo investiga el compromiso entre codificar todas las restricciones en el estado inicial frente a codificar solo un subconjunto. Demuestra que la codificación parcial de restricciones, que permite la estructura de producto requerida para el mezclador local, puede generar circuitos totales más compactos que la codificación completa de restricciones, incluso si esta última reduce el tamaño del espacio de búsqueda.
• Preservación de la Factibilidad: El método mantiene la ventaja central de GM-QAOA: el operador de mezcla preserva el espacio de búsqueda definido por el estado inicial, asegurando que el algoritmo no se desvíe hacia regiones infactibles.

Resultados
Los autores evaluaron el método propuesto en el problema de Exact-Cover y el Problema del Viajante (TSP) mediante simulaciones numéricas.

• Problema Exact-Cover: Para una instancia de siete cúbits, el método propuesto logró un comportamiento de convergencia comparable al GM-QAOA original. Crucialmente, la descomposición de la unitaria de mezcla en el conjunto de puertas $\{RX, RY, RZ, CNOT\}$ redujo el recuento de CNOT de 218 (original) a 28 (propuesto), una reducción aproximada del 87%.
• Problema del Viajante (TSP): Las simulaciones en instancias de TSP de cuatro ciudades (nueve cúbits) mostraron que el método propuesto mantiene probabilidades de solución comparables a GM-QAOA a través de diversas profundidades de capa $p$.
  • Resiliencia al Ruido: Bajo un modelo de ruido de depolarización, el método propuesto exhibió un error relativo significativamente menor en el valor esperado del Hamiltoniano de costo en comparación con el GM-QAOA original, atribuido a la reducción de la profundidad del circuito y el recuento de puertas.
  • Compromiso de Recursos: Aunque el método propuesto requiere más ejecuciones de circuitos durante la optimización clásica debido al mayor número de parámetros variacionales, la reducción en la complejidad del circuito cuántico (el recuento de CNOT cayó de 572 a 54 por operador de mezcla) lo hace más viable para hardware ruidoso.
  • Codificación Parcial vs. Completa: Para el TSP, codificar solo la restricción de paso de tiempo ($P_1$) en el estado inicial (codificación parcial) junto con el mezclador local resultó en una profundidad de circuito de 450 en el rendimiento óptimo ($p=7$). En contraste, codificar tanto la restricción de paso de tiempo como la de visita de ciudades ($P_1$ y $P_2$) en el estado inicial (codificación completa) requirió un mezclador global y resultó en una profundidad de circuito de 4142 en $p=1$, a pesar de lograr una alta probabilidad de solución más rápido. Los autores concluyen que la codificación parcial produce una complejidad de circuito general más favorable.

Significancia y Reivindicaciones
El artículo afirma que los mezcladores de Grover de actuación local propuestos ofrecen una vía práctica para implementar QAOA con preservación de restricciones en dispositivos cuánticos de la era NISQ. Al explotar la estructura de producto de los subespacios factibles, el método reduce significativamente el costo de implementación (recuento de puertas y profundidad) mientras preserva la capacidad del algoritmo para converger hacia soluciones de alta calidad.

Los autores señalan modestamente que, si bien el aumento de parámetros introduce una mayor carga de optimización clásica y potencialmente un paisaje de optimización más complejo, la reducción en la complejidad del circuito cuántico es el factor dominante para los dispositivos NISQ, donde la fidelidad de la puerta es la limitación principal. El trabajo sugiere que el compromiso entre el número de parámetros y la profundidad del circuito favorece el enfoque propuesto para el hardware actual. El artículo no pretende resolver la cuestión teórica de por qué la estructura de mezcla relajada logra una convergencia comparable, identificando esto como una dirección abierta para investigaciones futuras.