Complexity of detecting large coefficients in the Pauli basis

Resumen Técnico: Complejidad de la detección de coeficientes grandes en la base de Pauli

Definición del Problema
Este artículo aborda el problema computacional de determinar si un estado cuántico $\rho$, preparado por un circuito cuántico sucinto $C$, posee un coeficiente "grande" en la base de Pauli. Formalmente, dado un circuito de preparación de estados $C$ y un umbral $\epsilon > 0$, la tarea consiste en decidir si existe una matriz de Pauli no identidad $P \in \mathcal{P}_n \setminus \{I^{\otimes n}\}$ tal que $|\text{Tr}(P\rho)| \ge \epsilon$. El problema se plantea como un problema de promesa: el algoritmo debe devolver "Sí" si tal $P$ existe, y "No" si para todo $P$ no identidad, $|\text{Tr}(P\rho)| \le \epsilon/2$. El estado $\rho$ se define como la traza parcial de un estado puro generado por $C$, aunque el artículo también considera el caso donde $\rho$ es puro (sin qubits descartados).

Metodología
La metodología central implica una reducción de complejidad desde el problema $\lambda$-Gap Minimum-Weight Codeword ($\lambda$-GapMWC), un problema conocido por ser difícil para los códigos lineales clásicos.

1. Construcción de la Reducción: Los autores construyen un mapeo desde una instancia $(G, t)$ de $\lambda$-GapMWC (donde $G$ es una matriz generadora y $t$ es un umbral) hacia una instancia del problema de Coeficiente de Pauli Grande (LPC, por sus siglas en inglés).

   • Definen una variable aleatoria $V$ muestreando uniformemente columnas de una versión con relleno (padded) de $G$.
   • Construyen una matriz de densidad $\rho_{G,t}$ como la esperanza de $|V\rangle\langle V|$ sobre $k$ copias independientes de $V$, creando efectivamente un estado diagonal en la base computacional.
   • Utilizando el Lema 3.2, establecen un vínculo algebraico directo entre el peso de Hamming de los codewords $xG$ y los valores de esperanza de los operadores de Pauli diagonales $Z^x$ sobre $\rho_{G,t}$:
     $$\text{Tr}(Z^x \rho_{G,t}) = \left(1 - \frac{2\text{wt}(xG)}{N}\right)^k$$
   • Al elegir cuidadosamente los parámetros $N$ (tamaño de relleno) y $k$ (número de muestras), aseguran que si existe un codeword con peso $\le t$, la esperanza de Pauli correspondiente exceda $\epsilon$, mientras que si todos los codewords tienen peso $> \lambda t$, todas las esperanzas permanecen por debajo de $\epsilon/2$.

2. Extensión a Estados Puros: Para abordar el caso en el que $\rho$ debe ser un estado puro, los autores emplean una técnica de "ocultación" (hiding). Utilizan un operador unitario $U$ (garantizado por los Lemas 3.3 y 3.4 mediante argumentos de concentración de medida) que suprime los valores de esperanza de los operadores de Pauli no identidad que actúan sobre un "registro de muestra" auxiliar. Esto permite que la reducción incruste la lógica de estado mixto en un estado puro $|\Psi_{G,t}\rangle$ sin introducir coeficientes grandes espurios.

3. Análisis de Complejidad:

   • Pertenencia: El artículo demuestra que LPC está en QCMA. Un testigo clásico consiste en la descripción de la matriz de Pauli $P$. Un verificador cuántico puede estimar $\text{Tr}(P\rho)$ mediante mediciones de Pauli repetidas. Si $\epsilon$ es inversamente polinómica en el tamaño del circuito, esta verificación se ejecuta en tiempo polinomial.
   • Dureza: La reducción de $\lambda$-GapMWC a LPC se realiza en tiempo polinomial determinista. Dado que $\lambda$-GapMWC es difícil para NP (específicamente, resolverlo en BQP implica que $\text{NP} \subseteq \text{BQP}$), la dureza se transfiere a LPC.

Contribuciones Clave y Resultados

• Pertenencia a QCMA: Se demuestra que el problema está en QCMA, confirmando que una descripción clásica del operador de Pauli es suficiente para la verificación.
• Dureza para NP bajo BQP: El resultado principal es que si LPC estuviera en BQP (resoluble por un algoritmo cuántico de tiempo polinomial), entonces NP $\subseteq$ BQP. Esto implica que, bajo el supuesto estándar de que $\text{NP} \not\subseteq \text{BQP}$, no existe un algoritmo cuántico eficiente para detectar coeficientes de Pauli grandes para estados generales.
• Dureza de Estado Puro: El resultado de dureza se mantiene incluso cuando el estado de entrada se restringe a ser puro, resolviendo la cuestión de si descartar qubits (estados mixtos) es la fuente de la dificultad.
• Dureza BQP: El artículo demuestra además que LPC es BQP-duro. Esto sugiere que el problema probablemente no esté en NP (a menos que $\text{BQP} \subseteq \text{NP}$), indicando que una caracterización puramente clásica de testigos es poco probable.
• Umbral Constante: La dureza se mantiene incluso cuando $\epsilon$ es una constante independiente del tamaño de la entrada, descartando la posibilidad de que la dificultad surja únicamente de requerir una detección de alta precisión.

Significado y Reivindicaciones
El artículo afirma resolver una pregunta abierta sobre la existencia de procedimientos tomográficos eficientes para encontrar los coeficientes más grandes de un estado cuántico en la base de Pauli. Los resultados indican que tales procedimientos eficientes no existen bajo supuestos de complejidad estándar.

Los autores señalan que, si bien establecen la pertenencia a QCMA y la dureza para NP (y la dureza BQP), no prueban un límite ajustado (por ejemplo, la completitud de QCMA). Sin embargo, argumentan que los resultados son suficientes para aclarar el panorama: los algoritmos destinados a encontrar grandes coeficientes de Pauli con recursos polinomiales deben depender de supuestos estructurales adicionales sobre el estado, tales como la escasez de Pauli (Pauli sparsity), comportamiento tipo estabilizador, bajo rango, localidad o bajo entrelazamiento. Sin tales restricciones, el problema general sigue siendo computacionalmente intratable.