An efficient Pauli decomposition algorithm for structured matrices

Resumen Técnico: Un Algoritmo Eficiente de Descomposición de Pauli para Matrices Estructuradas

Planteamiento del Problema
La descomposición de matrices clásicas de $2^n \times 2^n$ en combinaciones lineales de cadenas de Pauli es un cuello de botella crítico para las implementaciones de extremo a extremo de algoritmos cuánticos de corto plazo, particularmente en química, aprendizaje automático y finanzas. Muchos algoritmos, como el Eigensolver Cuántico Variacional (VQE) y los resolvedores de álgebra lineal, asumen que los datos de entrada se proporcionan como una Combinación Lineal de Unitarias (LCU) de cadenas de Pauli. Sin embargo, para matrices generales especificadas clásicamente, esta descomposición no se conoce de antemano.

Los algoritmos existentes para matrices densas genéricas escalan exponencialmente con el número de cúbits $n$. El enfoque más directo requiere un tiempo de $O(32^n)$, mientras que el mejor método conocido actualmente (por ejemplo, en PennyLane) escala como $O(n4^n)$. Este costo exponencial surge porque, en el peor de los casos, una matriz tiene soporte en todos los $4^n$ elementos de la base de Pauli, lo que requiere la recuperación de todos los coeficientes.

Este artículo aborda una versión con promesa del problema de la descomposición de Pauli. Supone que la matriz de entrada $M$ tiene garantizado tener soporte en solo $k = \text{poly}(n)$ cadenas de Pauli. Además, la matriz se accede a través de un modelo de consulta clásica dispersa, donde un algoritmo puede recuperar las entradas no nulas de una fila o columna específica sin construir la matriz completa de $2^n \times 2^n$ en memoria. El objetivo es recuperar la descomposición de Pauli exacta (el conjunto de cadenas de Pauli y sus coeficientes) con alta probabilidad utilizando recursos polinómicos en $n$, $k$ y $\log(1/\delta)$.

Metodología
Los autores proponen un algoritmo clásico aleatorizado que aprovecha la dispersión prometida ($k$) y la estructura de las cadenas de Pauli en su forma simpléctica binaria. El algoritmo descompone el problema en tres etapas principales:

1. Descubrimiento de las Partes Pauli-X Activas ($x$):
   Utilizando el Lema 1, que relaciona el índice de la fila $v$, el índice de la columna $u$ y la parte Pauli-X $x$ mediante $x = u \oplus v$, el algoritmo consulta filas aleatorias de la matriz. Al recolectar los índices de columna de las entradas no nulas y realizar la operación XOR con los índices de fila, el algoritmo identifica el conjunto $X$ de cadenas de bits $x$ distintas presentes en la descomposición. Este paso se basa en el principio de incertidumbre booleano (Hecho 1) para asegurar que las consultas aleatorias revelen las cadenas $x$ activas con alta probabilidad.

2. Decodificación de Cadenas $x$ Únicas:
   Para cada $x$ descubierto, el algoritmo verifica si es "único" (es decir, asociado con exactamente una cadena de Pauli, de modo que $p_x = 1$). Si es único, la función de consulta $b_x(u) = M_{x \oplus u, u}$ se reduce a un único carácter de Walsh $\beta_x(z)(-1)^{z \cdot u}$. El algoritmo recupera la parte Pauli-Z $z$ asociada y el coeficiente $\beta$ evaluando $b_x$ en el vector cero y en los vectores de la base estándar. Un paso de certificación utilizando entradas aleatorias verifica que la solución candidata no sea un caso degenerado que coincida accidentalmente con los puntos consultados.

3. Decodificación de Cadenas $x$ Degeneradas:
   Si un $x$ es "degenerado" (asociado con $p_x \geq 2$ cadenas de Pauli), el problema se reduce a la recuperación de un espectro de Walsh-Hadamard disperso. El algoritmo emplea una técnica de plegado aleatorio (random folding):

   • Mapea los índices espectrales de $n$ bits ($z$) en contenedores (bins) de $m$ bits utilizando una matriz binaria aleatoria $R$, donde $m \ll n$.
   • Este "plegado" aísla las cadenas $z$ individuales en "contenedores de un solo elemento" (singleton bins) con alta probabilidad.
   • Para un contenedor de un solo elemento, el algoritmo utiliza consultas desplazadas para determinar los bits de la cadena $z$ y su coeficiente.
   • Los términos recuperados se restan de la función residual, y el proceso se repite hasta encontrar todos los términos para ese $x$.
   • Una verificación aleatoria final asegura que no se haya omitido ningún término.

Contribuciones Clave

• Diseño del Algoritmo: El artículo presenta un algoritmo clásico aleatorizado (Algoritmo 1) que resuelve el problema de la descomposición de Pauli bajo la promesa de $k$-dispersión y acceso de consulta dispersa.
• Mejora de la Complejidad: A diferencia de los métodos existentes que escalan exponencialmente en $n$, el algoritmo propuesto logra una complejidad de consulta y de tiempo que es polinómica en $n$, $k$ y $\log(1/\delta)$.
• Garantías Teóricas: El algoritmo tiene éxito con una probabilidad de al menos $1-\delta$ para cualquier $\delta \in (0, 1)$ elegido por el usuario. Los autores proporcionan límites rigurosos para las probabilidades de fallo en cada etapa (descubrimiento, decodificación única y decodificación degenerada).
• Técnicas de Walsh-Hadamard Dispersas: El trabajo adapta técnicas de recuperación dispersa del cubo booleano (específicamente la decodificación de Walsh-Hadamard dispersa) al contexto de la descomposición de Pauli, utilizando el plegado aleatorio y la recuperación de bits basada en desplazamientos.

Resultados

• Pruebas Numéricas de Rendimiento: Los autores probaron el algoritmo en instancias aleatorias para $n = 2$ a $30$ con $k = 2^n$.
  • Para $n$ pequeño ($n < 10$), la sobrecarga del algoritmo aleatorizado lo hace más lento que la rutina PauliDecompose de PennyLane.
  • Ocurre un punto de cruce alrededor de $n=10$. Para $n > 10$, el algoritmo propuesto supera significativamente al baseline de tiempo exponencial.
  • El tiempo de ejecución y el recuento de consultas observados escalan polinómicamente con $n$, en consistencia con los límites teóricos.
  • En todas las ejecuciones probadas, el algoritmo recuperó con éxito la descomposición completa sin fallos.
• Escalabilidad: El algoritmo manejó con éxito instancias de hasta $n=30$, un régimen donde construir la matriz completa o ejecutar algoritmos de descomposición densos se vuelve computacionalmente intratable.

Significancia y Reivindicaciones
El artículo afirma que, si bien encontrar la descomposición de Pauli es exponencialmente difícil para matrices generales, se vuelve eficientemente soluble para matrices que se sabe son dispersas en la base de Pauli. Este régimen es altamente relevante para algoritmos cuánticos de corto plazo que operan sobre datos de entrada clásicos estructurados.

Los autores enfatizan que su algoritmo está diseñado específicamente para el problema de la promesa donde $k = \text{poly}(n)$. No pretenden resolver el caso denso general. La importancia radica en permitir un preprocesamiento clásico eficiente para algoritmos cuánticos que requieren descomposiciones de Pauli, eliminando potencialmente un cuello de botella importante en los flujos de trabajo cuánticos de extremo a extremo. El trabajo también destaca contextos de aplicación específicos, como matrices definidas por reglas clásicas sucintas o datos mantenidos por servidores no confiables donde solo se dispone de acceso por consulta.

El artículo concluye de manera modesta, señalando que los límites superiores derivados pueden ser holgados y que el trabajo futuro podría explorar límites más ajustados, límites inferiores y extensiones a matrices aproximadamente dispersas.