Fair sampling with temperature-targeted QAOA based on quantum-classical correspondence theory

Este artículo propone SBO-QAOA, un algoritmo cuántico dirigido por temperatura basado en la teoría de la correspondencia cuántico-clásica que logra un muestreo justo de estados fundamentales degenerados al converger a una distribución de Gibbs uniforme, superando los sesgos inherentes al QAOA estándar incluso con parámetros variacionales mínimos.

Lo esencial

El Gran Problema: Encontrar al Ganador "Justo"

Imagina que estás organizando un concurso para encontrar la mejor solución a un rompecabezas complejo. En muchos casos, no hay una sola respuesta perfecta; hay varias respuestas diferentes que son igualmente perfectas. Llamemos a esto "estados fundamentales degenerados".

En el mundo real, si tienes cinco equipos diferentes que empatan en el primer lugar, quieres elegir uno de ellos al azar para que ningún equipo se sienta estafado. Esto se llama muestreo justo (fair sampling). Quieres que la computadora elija al Equipo A, al Equipo B o al Equipo C con la misma probabilidad, no favoreciendo a uno solo por la forma en que funciona la computadora.

El problema es que el método líder actual para resolver estos rompecabezas en computadoras cuánticas (llamado QAOA) es un poco como un árbitro sesgado. A medida que la computadora profundiza en el cálculo (aumentando la "profundidad del circuito"), comienza a favorecer accidentalmente a ciertos equipos ganadores sobre otros, a pesar de que todos son matemáticamente iguales. Deja de ser justa.

La Forma Antigua vs. La Nueva Forma

Los investigadores, Tetsuro Abe y Shu Tanaka, analizaron cómo solucionar esto.

• La Forma Antigua (QAOA Estándar): Piensa en esto como intentar encontrar el fondo de un valle. La computadora utiliza una herramienta de "sacudida" estándar (un mezclador de campo transversal) para ayudar a la bola a rodar hacia abajo. El problema es que esta herramienta de sacudida empuja la bola hacia puntos específicos en el fondo del valle, ignorando los otros puntos igualmente profundos. Es como un viento que solo sopla en una dirección, empujando la bola hacia un lado del suelo del valle.
• La Nueva Forma (SBO-QAOA): En lugar de cambiar la herramienta de "sacudida", los investigadores decidieron cambiar la forma del valle mismo. Utilizaron un truco matemático ingenioso basado en la "correspondencia cuántica-clásica".

La Analogía Creativa: El Mapa Dirigido por la Temperatura

Imagina que quieres simular una multitud de personas en una habitación.

• QAOA Estándar es como intentar que todos se sienten en la silla más cómoda. Funciona, pero obliga a todos a ocupar un solo lugar, o hace que se quede estancado favoreciendo una silla sobre otra.
• SBO-QAOA es como ajustar la temperatura de la habitación.
  • Si la habitación está muy fría (temperatura baja), todos quieren sentarse en los mejores asientos absolutos.
  • Si la habitación está cálida (temperatura más alta), las personas están más relajadas y dispersas, sentándose en varios buenos asientos con una probabilidad que coincide con qué tan cómodos se sientan.

Los investigadores diseñaron un nuevo "mapa" (llamado Hamiltoniano SBO) que codifica este concepto de temperatura directamente en las reglas de la computadora cuántica. En lugar de solo buscar el punto de menor energía, la computadora está programada para asentarse naturalmente en una distribución que parece una habitación cálida donde todos tienen la misma probabilidad de sentarse en cualquiera de los "mejores" asientos.

Lo Que Hicieron (El Experimento)

Para probar esto, utilizaron un pequeño "modelo de juguete" con solo 5 espines (como 5 diminutos imanes). Este modelo fue diseñado para tener seis soluciones diferentes que eran todas igualmente buenas (un empate de seis vías).

Ejecutaron dos tipos de simulaciones:

1. QAOA Estándar: Aumentaron la complejidad (profundidad del circuito) para ver si podía encontrar a los ganadores.
2. SBO-QAOA: Utilizaron su nuevo "mapa dirigido por la temperatura".

Los Resultados

• QAOA Estándar: A medida que hacían el cálculo más profundo, la computadora encontraba las soluciones ganadoras muy a menudo (casi el 100% de las veces). Sin embargo, era injusta. Seguía eligiendo dos soluciones ganadoras específicas e ignoraba las otras cuatro. El "árbitro" estaba sesgado.
• SBO-QAOA: La computadora encontró las soluciones ganadoras aproximadamente el 83% de las veces (que es exactamente lo que la física predice para una habitación a esa "temperatura" específica). Crucialmente, cuando encontraba un ganador, elegía las seis soluciones con igual probabilidad. Era perfectamente justa.

Aún mejor, probaron una versión "simplificada" de su nuevo método donde redujeron el número de ajustes que la computadora tenía que calibrar a solo cuatro perillas. Incluso con esta configuración simple, la computadora se mantuvo justa y dirigida por la temperatura.

La Conclusión

El artículo afirma que no es necesario inventar una herramienta de "sacudida" complicada para obtener resultados justos. En su lugar, si cambias el objetivo al que apunta la computadora (usando el Hamiltoniano SBO), la computadora aprende naturalmente a elegir a todos los ganadores empatados de manera justa, tal como las personas se dispersan en una habitación a una temperatura específica.

Esto funciona incluso si mantienes los ajustes simples (esquema lineal), lo que sugiere que el muestreo justo es posible sin hacer que el circuito de la computadora cuántica sea excesivamente complejo. Los autores señalan que, si bien esto funciona de maravilla en pequeñas simulaciones, el siguiente paso es descubrir cómo construir esto de manera eficiente en máquinas cuánticas reales y a gran escala, ya que el nuevo "mapa" involucra interacciones complejas que son difíciles de construir físicamente.

Resumen técnico

Resumen Técnico: Muestreo Justo con QAOA Dirigido por Temperatura

Planteamiento del Problema
En los problemas de optimización combinatoria caracterizados por estados fundamentales degenerados, la capacidad de realizar un "muestreo justo" (obtener una distribución uniforme sobre todos los estados solución degenerados sin sesgo) es crítica. Aunque el Recocido Cuántico (QA) y el Algoritmo de Optimización Aproximada Cuántica (QAOA) son metaheurísticas prometedoras para estos problemas, las implementaciones estándar que utilizan un mezclador de campo transversal suelen fallar en lograr un muestreo justo. La evidencia teórica y experimental sugiere que, a medida que aumenta la profundidad del circuito, el QAOA estándar induce sesgos entre los estados degenerados, favoreciendo soluciones específicas incluso cuando la relación de aproximación converge a la unidad. Las soluciones existentes, como los mezcladores especializados o el post-procesamiento híbrido, a menudo aumentan la complejidad del circuito o requieren pasos computacionales clásicos adicionales.

Metodología
Los autores proponen SBO-QAOA, una variante de QAOA que aborda el sesgo de muestreo no modificando el mezclador, sino rediseñando el Hamiltoniano de costo (objetivo) basado en la teoría de correspondencia cuántico-clásica.

• Marco Teórico: En lugar de apuntar al estado fundamental del Hamiltoniano de Ising clásico $\hat{H}_0$, el SBO-QAOA apunta al estado fundamental de un Hamiltoniano efectivo, $\hat{H}_S(T)$, derivado de Somma et al. Este Hamiltoniano se construye de tal manera que su estado fundamental único corresponde a un estado cuántico $|\psi_{Gibbs}(T)\rangle$, donde las amplitudes de probabilidad son las raíces cuadradas de los factores de Boltzmann del sistema clásico a una temperatura específica $T$.
• Construcción del Hamiltoniano: El Hamiltoniano SBO se define como:
  $$\hat{H}_S(T) = -e^{-\alpha/T} \sum_{i=1}^N \left( \hat{\sigma}_i^x - e^{\hat{H}_i/T} \right)$$
  donde $\hat{H}_i$ representa los términos locales de $\hat{H}_0$ dependientes del espín $i$, y $\alpha$ es un factor de escala que evita la divergencia cuando $T \to 0$. En SBO-QAOA, $\hat{H}_C$ se establece como $\hat{H}_S(T)$, mientras que se retiene el mezclador de campo transversal estándar $\hat{H}_X$.
• Esquemas de Parametrización: El estudio evalúa dos estrategias de parametrización para los ángulos variacionales $\{\gamma_k, \beta_k\}$:
  1. Parámetro completo: $2p$ variables independientes para la profundidad del circuito $p$.
  2. Linealizada: Un esquema de reducción donde los ángulos son funciones lineales del índice de profundidad, reduciendo las variables de optimización a cuatro ($\gamma_{pendiente}, \gamma_{intersección}, \beta_{pendiente}, \beta_{intersección}$) independientemente de la profundidad.
• Configuración Experimental: Se realizaron simulaciones numéricas en un modelo de juguete de Ising frustrado de 5 espines con degeneración de estado fundamental de seis veces. El sistema se simuló exactamente (evolución de matriz completa) para comparar el QAOA estándar y el SBO-QAOA a través de diversas profundidades de circuito ($p=1$ a $100$) y temperaturas.

Resultos Clave

• Sesgo del QAOA Estándar: En el QAOA estándar (apuntando a $\hat{H}_0$), el aumento de la profundidad del circuito $p$ impulsa la probabilidad total del estado fundamental ($P_{GS}$) hacia la unidad. Sin embargo, la distribución dentro del subespacio degenerado permanece sesgada; pares de estados específicos se vuelven dominantes mientras que otros son suprimidos, independientemente de si se utilizan parámetros completos o linealizados.
• Justicia del SBO-QAOA: Al apuntar a $\hat{H}_S(T)$, el SBO-QAOA exhibe un comportamiento fundamentalmente diferente:
  • Dirección por Temperatura: La probabilidad total del estado fundamental $P_{GS}$ no se acerca a la unidad, sino que se satura en un valor consistente con la probabilidad de la distribución de Gibbs a la temperatura $T$ especificada (por ejemplo, $\approx 0.83$ para $T=1$).
  • Muestreo Uniforme: A medida que $p$ aumenta, la distribución de probabilidad a través de los estados fundamentales degenerados se vuelve uniforme. Las probabilidades de distintos pares de estados convergen a valores idénticos, confirmando un muestreo justo.
  • Distancia de Variación Total (TVD): La TVD entre la distribución de salida y la distribución de Gibbs objetivo disminuye con el aumento de $p$, convergiendo cerca de cero. Esto confirma que el algoritmo reproduce la distribución completa de temperatura finita, no solo los estados fundamentales.
• Robustez a la Reducción de Parámetros: El muestreo justo y las propiedades de dirección por temperatura del SBO-QAOA se preservan incluso bajo el esquema linealizado, donde el número de parámetros variacionales se reduce de $2p$ a solo cuatro.

Significancia y Reivindicaciones
El artículo afirma que el muestreo justo en QAOA puede lograrse sin aumentar la complejidad del mezclador ni añadir pasos de post-procesamiento clásico. Al reemplazar el Hamiltoniano objetivo con el Hamiltoniano SBO, el algoritmo codifica inherentemente la distribución de Gibbs como su estado fundamental. Los autores demuestran que este enfoque permite:

1. Muestreo Justo: Lograr una distribución uniforme sobre los estados fundamentales degenerados.
2. Dirección por Temperatura: Controlar la distribución de muestreo mediante el parámetro $T$.
3. Eficiencia: Mantener estas propiedades con un conjunto mínimo de parámetros variacionales (cuatro), lo que hace que el enfoque sea potencialmente escalable en términos de complejidad de optimización.

Los autores señalan que, si bien el presente trabajo valida estas propiedades en un sistema pequeño mediante diagonalización exacta, el trabajo futuro debe abordar la escalabilidad. Específicamente, la implementación de $\hat{H}_S(T)$ en dispositivos basados en puertas requiere expansiones de cadenas de Pauli eficientes y descomposiciones de circuitos, ya que el Hamiltoniano generalmente induce interacciones de muchos cuerpos.