Resumen Técnico: Sobre la Dureza de la Membresía Aproximada de Circuitos Cuánticos y la Optimización

1. Definición del Problema

El artículo investiga la complejidad computacional de dos problemas fundamentales en la teoría de circuitos cuánticos: Membresía Aproximada y Optimización Aproximada.

• Membresía Aproximada ($\text{ApproxMember}$): Dado un circuito cuántico $C$ sobre un conjunto de puertas $G$, un conjunto de unitarias $S$, una métrica de distancia $m$ y una tolerancia $\epsilon$, decidir si existe una unitaria $U \in S$ tal que la distancia $d_m(C, U) \le \epsilon$.
  • Un caso especial es la Identidad Aproximada ($\text{ApproxId}$), donde $S = \{I\}$.
  • El artículo considera tres conjuntos específicos para $S$:
    1. $S = \{I\}$ (Identidad).
    2. $S \subseteq S_{\text{Cliff}}$ (Unitarias implementables mediante circuitos de Clifford).
    3. $S \subseteq S_{\text{GP}}$ (Matrices de permutación generalizadas, es decir, unitarias que no crean superposición).
• Optimización Aproximada ($\text{ApproxOpt}$): Dado un circuito $C$, una función de costo $f$ y un presupuesto $k$, decidir si existe un circuito equivalente $C'$ tal que $d_m(C, C') \le \epsilon$ y $f(C') \le k$. La función de costo $f$ se caracteriza por su "conjunto libre" $S_f = \{U_{C'} \mid f(C') = 0\}$.

El estudio se centra en entradas libres de promesas (promise-free), contrastando con el trabajo previo de Janzing, Wocjan y Beth (2005), que estableció la completitud para QMA del problema de "verificación de no-identidad" bajo la promesa de que el circuito está cerca o lejos de la identidad. Este trabajo elimina esa promesa, preguntando si el problema sigue siendo difícil cuando la distancia del circuito de entrada al conjunto objetivo es desconocida.

Los autores analizan tres métricas estándar para medir la distancia entre unitarias:

1. Métrica de Seno (Sine Metric): Basada en la traza, captura diferencias en el caso promedio ($d_{\text{Sine}}$).
2. Métrica Espectral (Spectral Metric): Basada en la norma del operador, captura diferencias en el peor de los casos ($d_{\text{sp}}$).
3. Métrica de Operador (Operator Metric): La versión de la métrica espectral invariante ante la fase global ($d_{\text{op}}$).

2. Metodología

Los autores establecen la dureza mediante una reducción de la clase de complejidad PP (Tiempo Polinómico Probabilístico) al problema de membresía aproximada. El núcleo de su metodología involucra los siguientes pasos:

1. Problema Fuente: Utilizan AtMostSat, un problema PP-duro que pregunta si una fórmula proposicional $\phi$ es satisfecha por, a lo sumo, una fracción $\beta$ de sus asignaciones. Introducen una versión con promesa, PromiseAtMostSat, donde se promete que la fracción de asignaciones satisfactorias es a lo sumo $\kappa$.
2. Reducción de Promesa a Aproximación: Demuestran que PromiseApproxId (verificar si un circuito está $\epsilon$-cerca de la identidad bajo la promesa de que está $\tau$-cerca) es PP-duro. Esto se logra construyendo circuitos Clifford+T desde fórmulas $\phi$ tales que la distancia $d_m(I, C)$ es una función estrictamente creciente $g(\gamma(\phi))$ de la fracción de satisfacción $\gamma(\phi)$.
   • Para la métrica de Seno, construyen un circuito que implementa una operación controlada-XOR ($|x\rangle|b\rangle \mapsto |x\rangle|b \oplus \phi(x)\rangle$).
   • Para las métricas Espectral y de Operador, utilizan la iteración de Grover para construir circuitos con ángulos propios dependientes de $\gamma(\phi)$. Para la métrica de operador, emplean productos tensoriales de estos circuitos para controlar la longitud de arco de los ángulos propios en el círculo unitario.
3. Eliminación de la Promesa:
   • Caso $S = \{I\}$: La dureza de la versión con promesa implica directamente la dureza de la versión libre de promesa para los rangos específicos de $\epsilon$.
   • Caso $S \subseteq S_{\text{Cliff}}$: Utilizan un argumento de la desigualdad triangular (Lema 6). Demuestran que para un $\epsilon$ suficientemente pequeño (específicamente $\epsilon < \sqrt{2}/4$), si se promete que un circuito $C$ está cerca de $I$, los únicos elementos en $S_{\text{Cliff}}$ que pueden estar $\epsilon$-cerca de $C$ son aquellos a distancia 0 de $I$ (es decir, $I$ mismo). Esto se basa en acotar inferiormente la distancia mínima no nula entre $I$ y cualquier otra unitaria de Clifford.
   • Caso $S \subseteq S_{\text{GP}}$: Construyen circuitos específicos donde la distancia al conjunto de matrices de permutación generalizada es exactamente la distancia a la identidad para valores pequeños de $\gamma(\phi)$, permitiendo una reducción directa desde el problema de promesa. Esta reducción se aplica específicamente cuando la identidad $I$ está incluida en el conjunto $S$ (es decir, $I \in S \subseteq S_{\text{GP}}$).

3. Contribuciones Clave y Resultados

Teorema Principal (Teorema 1)

El artículo demuestra que ApproxMember es PP-duro para un amplio rango de parámetros, siempre que el conjunto de puertas $G$ pueda implementar exactamente Clifford+T. La dureza se mantiene para:

• Conjuntos $S$: $S=\{I\}$, $I \in S \subseteq S_{\text{Cliff}}$, e $I \in S \subseteq S_{\text{GP}}$.
• Métricas: Métricas de Seno, Espectral y de Operador.
• Tolerancia $\epsilon$:
  • Para $S=\{I\}$ y métricas basadas en la traza (Seno): PP-duro para todo $0 < \epsilon < 1$ (el diámetro completo).
  • Para $S=\{I\}$ y métricas Espectral/de Operador: PP-duro para todo $0 < \epsilon < 2$.
  • Para $I \in S \subseteq S_{\text{Cliff}}$: PP-duro para $0 < \epsilon < \sqrt{2}/4 \approx 0.3536$.
  • Para $I \in S \subseteq S_{\text{GP}}$: PP-duro para $0 < \epsilon < 1$ (Seno) y $0 < \epsilon < \sqrt{2}$ (Espectral/Operador).

Corolario 1 (Dureza de Optimización)

Los resultados implican directamente que ApproxOpt es PP-duro para minimizar la profundidad total de puertas/conteo de puertas, la profundidad de puertas no-Clifford/conteo de puertas, y la profundidad de puertas de superposición/conteo de puertas, dentro de los rangos $\epsilon$ correspondientes.

Hallazgos Técnicos Específicos

1. Dureza para Puertas Clásicas-Reversibles: Incluso cuando el conjunto de puertas $G$ consiste únicamente en puertas clásicas-reversibles (ej. X, CNOT, Toffoli) que no pueden crear superposición, el problema ApproxId bajo la métrica de Seno sigue siendo PP-duro para todo $0 < \epsilon < 1$.
2. Robustez: Los resultados de dureza se generalizan a cualquier medida de distancia derivada de las métricas de Seno, Espectral o de Operador mediante una función estrictamente creciente. Además, los problemas siguen siendo PP-duros incluso si el objetivo es solo aproximar el costo mínimo dentro de cualquier factor (constante o no), ya que la dureza se mantiene cuando el costo óptimo es 0.
3. Comparación con el Trabajo Previo: El artículo fortalece el resultado de Janzing, Wocjan y Beth (2005). Mientras que su resultado mostraba la completitud para QMA del problema de verificación de no-identidad con promesa, este trabajo muestra que el problema libre de promesa es PP-duro (una clase que se cree es estrictamente más difícil que QMA) para un conjunto más amplio de métricas y conjuntos $S$.

4. Significado y Reivindicaciones

Los autores afirman que sus resultados demuestran que la optimización aproximada de circuitos cuánticos es fundamentalmente más difícil sobre entradas libres de promesas en comparación con la completitud para QMA de la verificación de no-identidad basada en promesas.

• Independencia de Recursos: La dureza persiste independientemente de los recursos cuánticos disponibles (cualquier puerta, puertas no-Clifford o superposición).
• Independencia de la Métrica: La dureza se mantiene a través de varias métricas de distancia (basadas en la traza, espectrales y de operador).
• Implicaciones Prácticas: Dado que los conjuntos de puertas estándar (como Clifford+T) satisfacen las condiciones, estos resultados de dureza se aplican directamente a tareas reales de compilación y optimización cuántica. Los resultados indican que encontrar un circuito aproximadamente equivalente con el costo mínimo (por ejemplo, el mínimo conteo de T o profundidad) es intratable para las computadoras clásicas, incluso permitiendo errores de aproximación, a menos que la tolerancia al error sea trivialmente grande (que exceda el diámetro del espacio métrico).

El artículo concluye señalando problemas abiertos respecto a la complejidad para valores más grandes de $\epsilon$ (específicamente $\epsilon \ge \sqrt{2}/4$ para conjuntos de Clifford y $\epsilon \ge \sqrt{2}$ para conjuntos de permutación) y límites superiores coincidentes, aunque señala que para conjuntos algebraicos y la métrica de Seno en $\epsilon = \sqrt{2}/2$, el problema es PP-completo.