Membership in the cone of quantum states over time is NP-hard

Resumen Técnico: La pertenencia al cono de estados cuánticos en el tiempo es NP-duro

Planteamiento del problema
El artículo aborda la complejidad computacional de caracterizar el cono convexo $\mathcal{Q}$ de los "estados sobre el tiempo" (stotes, por sus siglas en inglés). Un stote se define como un operador hermítico, generalmente no positivo, en un sistema bipartito $H_A \otimes H_B$ construido a partir de un estado inicial $\rho$ y un canal cuántico $E$ mediante la prescripción del producto de Jordan:
$$Q = (\rho \otimes \mathbb{1}) \star J_E = \frac{1}{2}((\rho \otimes \mathbb{1})J_E + J_E(\rho \otimes \mathbb{1}))$$
donde $J_E$ es el operador de Jamiołkowski del canal $E$. El conjunto $\mathcal{Q}$ es el cono convexo generado por todos tales operadores. El problema abierto central, planteado en [HCW26], es caracterizar las propiedades de pertenencia de este cono y de su dual $\mathcal{Q}^*$. Específicamente, el artículo investiga si determinar si un operador pertenece a $\mathcal{Q}$ (pertenencia exacta) o si está cerca de $\mathcal{Q}$ (pertenencia débil) puede resolverse en tiempo polinomial.

Metodología
El autor emplea una reducción del problema de la separabilidad cuántica, el cual es conocido por ser NP-duro. La estrategia técnica central consiste en construir un embebedimiento facial del cono de estados separables en el cono de estados sobre el tiempo.

1. Construcción del embebedimiento facial:
   El autor define un sistema de salida específico $H_B = H_{A'} \otimes H_R$, donde $H_{A'}$ es una copia del espacio de entrada $H_A$ y $H_R$ es un registro auxiliar. Construyen un operador testigo $W_0 = (d\mathbb{1}_{AA'} - S_{AA'}) \otimes \mathbb{1}_R$, donde $S_{AA'}$ es el operador de intercambio (swap).
   Demuestran que $W_0$ pertenece al cono dual $\mathcal{Q}^*$ y que la cara expuesta de $\mathcal{Q}$ definida por el hiperplano ortogonal a $W_0$ (es decir, $\{Q \in \mathcal{Q} : \text{Tr}[W_0 Q] = 0\}$) es isomórfica al cono de estados separables $\text{SEP}^+(A:R)$.

2. El mapa de embebedimiento:
   Se define un mapa lineal racional inyectivo y explícito $L$ tal que, para cualquier operador hermítico $\sigma$ en $A \otimes R$:
   $$\sigma \in \text{SEP}^+(A:R) \iff L(\sigma) \in \mathcal{Q}(A:A'R)$$
   El mapa $L$ se construye utilizando el mapa de simetrización $\Gamma(X) = \frac{1}{2}\{X \otimes \mathbb{1}, S\}$ tensorado con la identidad en $R$.

3. Estabilidad y robustez:
   Para extender el resultado de dureza de la pertenencia exacta a la pertenencia débil (la noción de complejidad estándar para conjuntos convexos), el autor deriva un límite de estabilidad cuantitativo (Proposición 3.6). Este límite relaciona la distancia de la norma de traza de un operador $Y \in \mathcal{Q}$ respecto a la cara expuesta con el valor $\text{Tr}[W_0 Y]$. Esto asegura que si un operador está lejos del cono separable, su imagen bajo $L$ permanece lejos del cono de stotes, incluso tras contabilizar las instancias de "NO" en un problema de promesa.

4. Paso de mezcla (Mixing step):
   Para manejar los casos límite requeridos para las reducciones de pertenencia débil, el autor introduce un paso de mezcla $T_\theta(X) = (1-\theta)X + \theta \mathbb{1}/N$. Esto desplaza la imagen del cono separable hacia el interior relativo de la base de traza uno de $\mathcal{Q}$, preservando al mismo tiempo la separación para entradas no separables.

Contribuciones clave y resultados

• NP-dureza de la pertenencia exacta:
  El Teorema 4.1 establece que decidir si un operador hermítico racional pertenece a $\mathcal{Q}$ es NP-duro. Esto se demuestra mediante la equivalencia exacta entre la separabilidad y la pertenencia a la cara expuesta de $\mathcal{Q}$.

• NP-dureza de la pertenencia débil y optimización:
  El Teorema 4.2 demuestra que la pertenencia débil (determinar si un operador está a una distancia polinomialmente pequeña de $\mathcal{Q}$ o lejos de él) es fuertemente NP-dura. En consecuencia, la optimización débil sobre $\mathcal{Q}$ y su dual también es NP-dura. Esto implica que no existen pruebas de pertenencia en tiempo polinomial para $\mathcal{Q}$ a menos que P = NP.

• No representabilidad por SDP finito:
  El Teorema 4.5 demuestra que, para dimensiones $d, r \ge 2$ con $d+r > 5$, el cono $\mathcal{Q}(A:A'R)$ no admite una representación de programación semidefinida (SDR) finita. La prueba se basa en el hecho de que las caras expuestas y las imágenes lineales de sombras espectrales son, en sí mismas, sombras espectrales. Dado que el cono separable es conocido por no admitir una SDR finita (según el teorema de Fawzi [Faw21]), y $\mathcal{Q}$ contiene una copia lineal de este como una cara, $\mathcal{Q}$ no puede ser finamente representable por SDR.

• Propiedades geométricas:
  El artículo establece que $\mathcal{Q}$ es un cono cerrado, apuntado y generador (spanning). También proporciona un límite de estabilidad cuantitativo que muestra que la distancia a la cara separable escala con la raíz cuadrada del valor del testigo ($\sqrt{\eta}$), lo cual se demuestra como óptimo.

Significado y afirmaciones

El artículo afirma resolver el estatus de complejidad del problema de pertenencia para los estados sobre el tiempo, una estructura central para la inferencia bayesiana cuántica, la retrodicción y el transporte óptimo cuántico.

• Barrera de complejidad: La principal significación es la demostración de que caracterizar el cono de estados sobre el tiempo es computacionalmente intratable en el caso general. Esto descarta la existencia de algoritmos eficientes (en tiempo polinomial) para las pruebas de pertenencia u optimización sobre este cono, asumiendo que P $\neq$ NP.
• Limitaciones en las jerarquías de SDP: El resultado de no representabilidad implica que el cono no puede describirse exactamente mediante un número finito de restricciones semidefinidas. Esto sugiere que, si bien las jerarquías de SDP (como la jerarquía de Doherty-Parrilo-Spedalieri para la separabilidad) pueden converger, no pueden proporcionar una caracterización exacta de nivel finito del cono.
• Distinción de trabajos previos: El autor aclara que sus resultados de dureza no contradicen las pruebas semidefinidas previas para la compatibilidad de estados multitemporales (ej. [GBB26]), ya que dichas pruebas abordan un conjunto diferente que permite correlaciones sistema-entorno y memoria, en lugar del cono convexo específico generado por pares estado-canal definido aquí.

El artículo concluye señalando que, aunque la dureza se ha establecido para dimensiones de salida específicas ($B = A' \otimes R$), la complejidad para dimensiones arbitrarias fijas o brechas constantes sigue siendo una cuestión abierta. También destaca que el exponente de estabilidad derivado es óptimo, lo que limita la precisión de los posibles algoritmos de aproximación.