Approximate simulation of complex quantum circuits using sparse tensors

Resumen Técnico: Simulación Aproximada de Circuitos Cuánticos Complejos Mediante Tensores Dispersos

Planteamiento del Problema
La simulación de circuitos cuánticos en computadoras clásicas es esencial para definir el límite de la ventaja cuántica verificable, resolver problemas de muchos cuerpos cuánticos y guiar el desarrollo del hardware. Si bien los métodos de redes de tensores (por ejemplo, Estados de Producto de Matrices, Grupo de Renormalización de Matriz de Densidad) se han convertido en el estado del arte para simular circuitos complejos, a menudo dependen de simetrías subyacentes o de baja dimensionalidad para lograr eficiencia. Además, la simulación clásica general está limitada por la teoría de la complejidad ($P \neq NP$), lo que impide la existencia de simuladores universales de tiempo polinomial. Los autores identifican la necesidad de herramientas de simulación que puedan aproximar estados cuánticos sin requerir la descomposición en valores singulares (SVD), simetrías subyacentes o baja dimensionalidad, apuntando específicamente a circuitos donde las redes de tensores tradicionales pueden presentar dificultades.

Metodología: Simulación de Tensores Dispersos Truncados (TruSTS)
El artículo presenta TruSTS, un método para simular aproximadamente circuitos cuánticos utilizando tensores con población dispersa. El enfoque central consiste en representar un estado cuántico de $N$ qubits $|\psi\rangle$ como un estado disperso $|\phi\rangle$, el cual es una combinación lineal de $k$ estados base ($k \le 2^N$).

• Estructura de Datos: El estado disperso se almacena utilizando dos arreglos de longitud fija de tamaño $k$:
  1. $x[x_i]$: Un arreglo de coordenadas enteras que representan las cadenas de bits binarias de los estados base.
  2. $\alpha[\alpha_i]$: Un arreglo de amplitudes de probabilidad complejas correspondientes a dichos estados base.
  3. Un puntero entero nnz rastrea el número de elementos actualmente llenos.
• Algoritmo de Contracción de Operaciones de Bits: Para aplicar una compuerta cuántica (representada como un tensor $\hat{U}$), el algoritmo emplea una estrategia de ordenación por bits inspirada en la multiplicación de matrices de Fila Dispersa Comprimida (CSR):
  1. Se define una máscara de bits para seleccionar los qubits acoplados por la compuerta.
  2. El arreglo del estado se ordena basándose en los bits "no acoplados" (el complemento de la máscara). Esto agrupa los estados base en sub-arreglos computacionalmente independientes donde la compuerta actúa de manera idéntica.
  3. La compuerta se aplica mediante contracciones de matrices de $4\times4$ independientes a cada sub-arreglo.
  4. Este proceso puede aumentar el número de términos no nulos (nnz) hasta en un factor de cuatro por cada aplicación de compuerta.
• Truncamiento: Para evitar el crecimiento exponencial de nnz, el algoritmo trunca el estado de vuelta a tamaño $k$ después de cada compuerta. El artículo compara dos estrategias de truncamiento:
  • Top-k: Conserva los $k$ términos con las mayores amplitudes de probabilidad.
  • Random-k: Conserva $k$ términos elegidos al azar.
  • Se aplica un factor de renormalización $\gamma$ a $|\phi\rangle$ para contabilizar la masa de probabilidad perdida durante el truncamiento.

Contribuciones Clave y Derivaciones Teóricas
Los autores derivan relaciones entre el parámetro de renormalización $\gamma$ y la fidelidad de la simulación $f = |\langle \psi | \phi \rangle|^2$.

• Límites de Fidelidad: Establecen que para circuitos cuánticos aleatorios, la fidelidad esperada $\bar{f}$ es aproximadamente $\gamma^2$ (la masa de probabilidad retenida), con una ligera desviación positiva debido a los términos de interferencia.
• Límites Superiores e Inferores:
  • Se deriva un límite inferior $\bar{f}_{min} \approx 1/2^N$ para el caso en que el estado se trunca a un solo estado base aleatorio.
  • Un límite superior $f_{max}$ se deriva asumiendo que la distribución de salida sigue una distribución de Porter-Thomas. Este límite representa la mejor fidelidad posible si se pudieran identificar y conservar las $k$ cadenas de bits más probables después de la ejecución del circuito, en lugar de truncar a mitad del circuito. El artículo señala que $f_{max} \approx d(1 - \ln d)$, donde $d = k/2^N$ es la fracción de truncamiento.

Result resultados
Los autores evaluaron el rendimiento de TruSTS en circuitos cuánticos aleatorios consistentes en unitarias de dos qubits de Haar-aleatorias dispuestas en capas.

• Fidelidad vs. Truncamiento: Las simulaciones en $N=24$ qubits muestran que la fidelidad del estado aproximado escala aproximadamente con el cuadrado del factor de renormalización $\gamma^2$. El truncamiento Top-k supera consistentemente al truncamiento Random-k al concentrar la probabilidad en los términos retenidos.
• Escalabilidad del Tiempo de Ejecución:
  • Versus $k$: El tiempo de ejecución por compuerta escala linealmente con el número de términos mantenidos $k$.
  • Versus $N$: Para $k \ll 2^N$, el tiempo de ejecución por compuerta es aproximadamente constante con respecto al número de qubits $N$ (probado hasta $N=64$). Esto indica que el algoritmo no introduce una sobrecarga dependiente del tamaño total del espacio de Hilbert, siempre que el estado permanezca disperso.
  • Memoria: El método evita la asignación de la memoria completa de $2^N$, almacenando únicamente $k$ términos.
• Comparación con MPS: Una comparación preliminar con Estados de Producto de Matrices (MPS) utilizando la biblioteca quimb en $N=24$ qubits (5 capas) muestra que, para los parámetros probados, MPS ofrece un compromiso más favorable entre tiempo de ejecución y fidelidad en la mayor parte del rango de datos, manteniendo una fidelidad más alta para tiempos de ejecución comparables. Sin embargo, TruSTS demuestra un decaimiento de la fidelidad constante y predecible a medida que aumenta el tiempo de ejecución, alcanzando un límite inferior cercano a $f \sim 10^{-8}$.

Significancia y Reivindicaciones
El artículo posiciona a TruSTS como una herramienta para extender las capacidades de los simuladores basados en redes de tensores, particularmente para escenarios en los que:

1. La simetría está ausente: El método no depende de simetrías subyacentes o de baja dimensionalidad.
2. Se evita la SVD: Logra el truncamiento sin el costo computacional de la Descomposición en Valores Singulares.
3. Existe una dispersión inherente: Es atractivo para estados cuánticos que son inherentemente dispersos.

Los autores afirman que TruSTS proporciona un compromiso útil entre fidelidad y tiempo de ejecución, con aplicaciones potenciales inmediatas en circuitos donde no se requiere estrictamente una alta fidelidad. Enfatizan que este trabajo sirve como base para futuras investigaciones sobre la optimización de redes de tensores dispersos y la combinación de TruSTS con estrategias de optimización del orden de contracción de redes de tensores para ampliar aún más el límite de la simulación clásica de sistemas cuánticos complejos. Los autores mantienen la modestia, señalando que la comparación rigurosa con métodos alternativos y las investigaciones utilizando cantidades medibles (como la fidelidad de entropía cruzada) son áreas importantes para el trabajo futuro.