Sampling (noisy) quantum circuits through randomized rounding

Resumen Técnico: Muestreo de Circuitos Cuánticos Ruidosos mediante Redondeo Aleatorizado

1. Planteamiento del Problema

La era actual de procesadores cuánticos (NISQ) cuenta con cientos a miles de qubits ruidosos. Si bien la comunidad ha desarrollado buenas estrategias para simular clásicamente y "desruidar" (error mitigation) los valores esperados de observables, existe un vacío crítico en aplicaciones que requieren las cadenas de bits (bit-strings) mismas, como en la optimización combinatoria (ej. Max-Cut, QUBO).

• El Dilema: Los métodos actuales de mitigación de errores solo devuelven estimaciones de valores esperados, no muestras de la distribución de salida. Para obtener una solución real a un problema de optimización, se necesitan las cadenas de bits.
• La Limitación: Muestrear directamente de un circuito cuántico ruidoso es computacionalmente intratable en la mayoría de los casos. Además, resultados recientes indican que, bajo cierto umbral de ruido, los algoritmos clásicos heurísticos superan a los dispositivos cuánticos.
• La Pregunta Clave: ¿Es posible generar muestras clásicas que repliquen el comportamiento de un circuito cuántico ruidoso (y sus soluciones de optimización) a un costo computacional menor, sin necesidad de ejecutar el circuito cuántico?

2. Metodología

Los autores proponen un algoritmo clásico de muestreo basado en redondeo aleatorizado gaussiano (inspirado en el algoritmo de Goemans-Williamson), que utiliza únicamente los márgenes de dos cuerpos (expectativas de pares de qubits) del circuito cuántico.

El Algoritmo (Algoritmo 4.1):

1. Entrada: Se obtienen los valores esperados del circuito cuántico (ruidoso o no):
   • El vector de medias $\mu_i = \langle Z_i \rangle$.
   • La matriz de covarianza $\Sigma_{ij} = \langle Z_i Z_j \rangle$.
2. Muestreo Gaussiano: Se genera una muestra $y \in \mathbb{R}^n$ de una distribución gaussiana multivariada con parámetros $\mu$ y $\Sigma$.
3. Redondeo: Cada componente $y_i$ se redondea a su signo ($z_i = \text{sign}(y_i)$) para obtener una cadena de bits $z \in \{-1, +1\}^n$.
4. Salida: La cadena de bits $z$ se utiliza como solución candidata para el problema de optimización.

Fundamento Teórico:
El método asume que para problemas como Max-Cut o QUBO, la información relevante reside en las correlaciones de dos cuerpos. El algoritmo no intenta superar al circuito cuántico, sino reproducir fielmente su distribución de salida (o la distribución del circuito ruidoso) utilizando solo sus estadísticas de segundo orden.

3. Contribuciones Clave

1. Algoritmo de Muestreo Eficiente: Presentan un método simple y polinomial que genera muestras basadas en la matriz de covarianza del circuito, evitando la simulación completa del estado cuántico.
2. Garantías Teóricas (A Priori y A Posteriori):
   • Max-Cut: Demuestran que la relación de recuperación (ratio entre el costo esperado del muestreo clásico y el del circuito cuántico) está acotada inferiormente por la constante de Goemans-Williamson ($\approx 0.878$).
   • Efecto del Ruido: Bajo ruido de despolarización local con fuerza $p$ y profundidad $D$, muestran que la relación de recuperación es $1 - O((1-p)^D)$. Esto implica que a medida que aumenta el ruido, el muestreo clásico se vuelve una aproximación cada vez mejor del circuito cuántico ruidoso, llegando a ser indistinguible en regímenes de alto ruido.
   • QUBO: Establecen un límite inferior de $2/\pi$ para el caso general, mejorando a medida que el ruido aumenta y las correlaciones decaen.
3. Marco End-to-End: Integran el muestreo con técnicas recientes de propagación de Pauli (Pauli backpropagation) [FRD+25, MAP+25]. Esto permite calcular clásicamente y eficientemente la matriz de covarianza de circuitos ruidosos en tiempo polinomial, cerrando el ciclo de un muestreador clásico completo.
4. Validación Experimental: Validan el método en hardware real de IBM (chips de 127 qubits) y simulaciones a gran escala, demostrando que el método no solo replica el valor esperado, sino toda la distribución de energía, incluyendo la cola de la distribución (valores extremos).

4. Resultados Principales

• Reproducción de la Distribución: Los experimentos en hardware IBMQ y simulaciones muestran que las muestras generadas por el redondeo aleatorizado reproducen fielmente la distribución completa de energía del circuito cuántico ruidoso, no solo su media.
• Comportamiento en el Ruido: Contrario a la intuición de que el ruido degrada la utilidad cuántica, el paper demuestra que en regímenes de ruido moderado a alto, el muestreo clásico basado en la matriz de covarianza es una proxy excelente del dispositivo cuántico.
• Superación de Límites Teóricos: En la práctica, la relación de recuperación observada supera frecuentemente los límites teóricos de peor caso (como $0.878$ para Max-Cut), especialmente en instancias reales donde las correlaciones no alcanzan el "peor caso" teórico.
• Robustez ante Tipos de Ruido: Aunque los teoremas se demuestran para ruido de despolarización, las simulaciones muestran un comportamiento similar bajo amortiguamiento de amplitud (amplitude damping), otro modelo de ruido común en hardware real.

5. Significado e Impacto

• Benchmarking Cuántico: Proporciona una herramienta robusta para establecer un punto de referencia (benchmark) para futuros dispositivos cuánticos. Si un dispositivo cuántico no puede superar a este muestreador clásico simple, no está demostrando ventaja cuántica en tareas de optimización.
• Clarificación de la Ventaja Cuántica: El trabajo delimita claramente el régimen donde los optimizadores cuánticos ruidosos pueden ser superados por métodos clásicos eficientes. Sugiere que para circuitos con suficiente ruido, la "ventaja" cuántica en optimización es ilusoria si el objetivo es solo obtener muestras de alta calidad.
• Alternativa Práctica: Ofrece una vía práctica para obtener soluciones de optimización basadas en circuitos cuánticos sin necesidad de ejecutar el hardware cuántico costoso, simplemente calculando las correlaciones clásicamente y redondeando.
• Implicaciones para NISQ: Sugiere que, en la era NISQ, la estrategia de "muestrear muchas veces y seleccionar el mejor" (CVaR) para recuperar valores sin ruido podría ser reemplazada o complementada eficazmente por este muestreador clásico, que es más escalable y menos costoso.

En resumen, el artículo demuestra que los circuitos cuánticos ruidosos para optimización combinatoria pueden ser muestreados eficientemente de forma clásica mediante la explotación de sus correlaciones de dos cuerpos, desafiando la noción de que se necesita un hardware cuántico perfecto para obtener soluciones útiles en estos problemas.