Resumen Técnico: Complejidad de Extensión Semidefinida del Conjunto Separable

1. Planteamiento del Problema

El artículo aborda la complejidad computacional de aproximar la probabilidad máxima de aceptación de un operador de medición de dos resultados $Q$ sobre el conjunto de estados separables, denotado como $\text{Sep}(d:d)$. Este problema de optimización, definido como $h_{\text{Sep}}(Q) = \max_{\sigma \in \text{Sep}(d:d)} \text{Tr}(Q\sigma)$, es central para la clase de complejidad $\text{QMA}(2)$ (Quantum Merlin-Arthur con dos pruebas no entrelazadas).

El enfoque específico es la complejidad de extensión semidefinida del conjunto separable dentro del marco establecido por Harrow, Natarajan y Wu (HNW). Los autores investigan el tamaño mínimo $r$ de un programa semidefinido (SDP) requerido para aproximar $h_{\text{Sep}}$ bajo las siguientes restricciones:

• Región Factible Común: Todos los operadores de medición $Q$ comparten una única región factible de SDP $\mathcal{P}$ (un espectroedro de matrices PSD de $r \times r$).
• Incrustación Independiente del Objetivo: Existe un mapa fijo $\iota$ que incrusta estados producto puros en $\mathcal{P}$ de tal manera que el objetivo del SDP $\Phi_Q$ reproduce la probabilidad de aceptación $\text{Tr}(Q\tau)$ para cada estado producto, independientemente de $Q$.
• Aproximación: El SDP debe aproximar $h_{\text{Sep}}$ dentro de un error aditivo $a$ o una brecha relativa $\varrho$.

El artículo también aplica estos límites inferiores a los desentrelazadores aproximados, canales cuánticos $\Lambda: \mathcal{L}(\mathbb{C}^D) \to \mathcal{L}(\mathbb{C}^d \otimes \mathbb{C}^d)$ que mapean entradas arbitrarias a estados cercanos a estados separables y cubren todos los estados separables. El objetivo es determinar la dimensión de entrada mínima $D$ requerida para tales canales.

2. Metodología

Los autores emplean una combinación de límites inferiores de matrices de patrones, técnicas de pseudo-densidad y geometría espectroédrica.

2.1 El Marco HNW y el Rango PSD

La técnica central se basa en el teorema de Lee–Raghavendra–Steurer (LRS), que relaciona el tamaño de una formulación de SDP con el rango PSD de una matriz no negativa específica (la "matriz de holgura" o slack matrix).

• Construcción de la Matriz de Holgura: Los autores construyen una matriz $M$ donde las filas corresponden a "testigos" (operadores bloque-positivos $W_T$) y las columnas corresponden a "estados" (estados producto $\sigma_S$). Las entradas son $M(T, S) = \text{Tr}(W_T \sigma_S)$.
• Factorización: Un SDP de tamaño $r$ con una región factible común implica una factorización PSD de esta matriz de tamaño $r+1$. Por lo tanto, un límite inferior en el rango PSD de $M$ proporciona un límite inferior en el tamaño del SDP.

2.2 La Matriz de Patrón de la Mochila (Knapsack)

A diferencia del trabajo previo (HNW) que utilizaba un protocolo QMA(2) basado en la 3-colorabilidad de grafos, este artículo construye una matriz basada en el polinomio central de la mochila:
$$f_m(x) = \frac{1}{m^2} \left[ \left( \sum_{i=1}^m x_i - \frac{m}{2} \right)^2 - \frac{1}{4} \right]$$
donde $m$ es un entero impar. En el hipercubo booleano $\{0,1\}^m$, $f_m(x) \geq 0$. Sin embargo, el funcional de pseudo-expectativa $\mathcal{G}_m$ de Grigoriev asigna un valor negativo a $f_m$ (específicamente $-1/4m^2$) al tratar la capa de peso de Hamming inexistente $m/2$ como válida.

2.3 Amplificación mediante Polinomios de Chebyshev

Para manejar errores de aproximación más grandes (constantes o inverso-polinómicos) en comparación con el régimen de error exponencialmente pequeño de HNW, los autores aplican una amplificación de Chebyshev-Hadamard:

• Aplican una transformación polinómica $P_\ell(u) = (1 + T_\ell(2u-1))/2$ a las entradas de la matriz.
• Esta transformación preserva la no negatividad de las entradas en el rango $[0,1]$ pero amplifica el valor de la pseudo-expectativa negativa en el punto "formal" negativo por un factor de $\ell^2$.
• Crucialmente, los autores utilizan la identidad $P_\ell(u) = u Q_\ell(u)^2$ para acotar el aumento del rango PSD, demostrando que el costo del rango crece solo linealmente con el grado del polinomio, lo que permite que el argumento escale con parámetros de error más grandes.

2.4 Construcción de Testigos y Estados

La Proposición 4.1 construye explícitamente:

• Estados Producto: $\sigma_S$ que codifican subconjuntos $S \subseteq [N]$ utilizando una superposición específica de vectores de base.
• Testigos Bloque-Positivos: $W_T$ construidos a partir de proyectores diagonales y un término de penalización que involucra el operador de intercambio (swap) $F$. Estos testigos están diseñados para ser no negativos en estados producto, pero pueden ser negativos en estados entrelazados, con un límite de norma de $O(m)$ independiente de la dimensión ambiente.

3. Contribuciones Clave y Resultados

3.1 Límites Inferiores para Formulaciones SDP

El artículo establece un nuevo límite inferior para el tamaño $r$ de las formulaciones SDP que aproximan $h_{\text{Sep}}$.

• Teorema 5.4: Para cualquier $\theta < 2/7$ fijo, existen constantes $c_\theta, a_\theta > 0$ tales que, para un $d$ suficientemente grande y un error de aproximación $a \leq a_\theta$, cualquier SDP que aproxime $h_{\text{Sep}}$ con un error aditivo $a$ tiene un tamaño:
  $$r \geq d^{c_\theta \min\{a^{-1/3}, d^\theta\}}$$
• Comparación con HNW: HNW demostró un límite inferior de $d^{\log d / \text{polylog} \log d}$ para un error de $O(1/d^2)$. El nuevo límite se aplica a errores constantes y mejora el límite de HNW a exponencial en una potencia de $d$ (específicamente $d^{\Omega(d^\theta)}$) cuando el error es suficientemente pequeño ($a \leq d^{-3\theta}$).
• Interpretación Geométrica: El Corolario 5.6 extiende esto a las sombras espectroédricas, demostrando que cualquier conjunto convexo de estados que contenga $\text{Sep}(d:d)$ y se encuentre dentro de la distancia de traza $a$ de este, requiere un levantamiento espectroédrico de tamaño al menos $d^{c_\theta \min\{(2a)^{-1/3}, d^\theta\}}$. Esto proporciona un contraparte cuantitativo al teorema de Fawzi de que el conjunto separable no tiene representación semidefinida exacta.

3.2 Límites Inferiores para Desentrelazadores Aproximados

Los autores aplican los límites inferiores de SDP a la dimensión de entrada $D$ de los desentrelazadores aproximados.

• Teorema 1.1: Para un desentrelazador $(\varepsilon, \delta)$-aproximado con error total $a = \varepsilon + \delta$, la dimensión de entrada $D$ satisface:
  $$\log D \geq c M_a \log(2 + R_a)$$
  donde $M_a$ y $R_a$ son funciones de $d$ y $a$ derivadas de los límites de SDP.
• Corolario 1.2 (Crecimiento Cuantitativo):
  • Si $a \leq n^{-c}$ (inverso-polinómico en el número de qubits $n = \log d$), entonces $\log D = \Omega(n^{1+c/3})$. Esto fuerza un número superlineal de qubits de entrada.
  • Si $a$ es del orden de $(\log d)^{18/7} / d^{6/7}$, entonces $\log D = \Omega(d^{2/7} / (\log d)^{6/7})$.
• Implicación para QMA(2): Estos resultados descartan la estrategia de desentrelazador para probar $\text{QMA} = \text{QMA}(2)$ cuando la brecha de promesa es superpolinómicamente pequeña ($n^{-\omega(1)}$), ya que tal estrategia requeriría un número superpolinómico de qubits de entrada.

3.3 Separabilidad Bosónica

El Corolario 5.7 extiende los límites inferiores al cuerpo separable bosónico de dos partículas (estados de la forma $|\psi\rangle\langle\psi|^{\otimes 2}$), mostrando que los mismos límites de complejidad se aplican.

4. Significado y Reivindicaciones

El artículo reclama la siguiente significancia:

1. Límites Inferiores Específicos de SDP: El trabajo proporciona los primeros límites inferiores informacionales incondicionales para formulaciones de extensión SDP generales de $h_{\text{Sep}}$ que aproximan el conjunto separable dentro de una distancia de traza constante o inverso-polinómica. El trabajo concurrente de Bostanci et al. [BGH+26] establece límites inferiores más fuertes para desentrelazadores aproximados mediante una separación de oráculo cuántico (superando los límites de desentrelazador en el Teorema 1.1), pero su reducción no se aplica a las formulaciones de SDP generales. Por lo tanto, los límites inferiores específicos de SDP (Teorema 5.4 y Corolario 5.5) siguen siendo la contribución principal de este trabajo en el contexto de la complejidad semidefinida.
2. Mejora Cuantitativa: Los límites mejoran significativamente los resultados de HNW, pasando de límites cuasi-polinomiales a límites exponenciales en $d$ para errores constantes o inverso-polinómicos.
3. Refutación de la Estrategia de Desentrelazador: Los resultados demuestran que la estrategia de desentrelazador no puede simular $\text{QMA}(2)$ usando un canal con un número polinómico de qubits de entrada si el error del canal es suficientemente pequeño en relación con la brecha de promesa, específicamente en el régimen donde se aplican los límites de SDP.
4. Avance Metodológico: El trabajo introduce una aplicación refinada del teorema LRS utilizando el polinomio de la mochila y la amplificación de Chebyshev, permitiendo un control más ajustado sobre los parámetros de error y los costos de rango PSD en comparación con las construcciones basadas en protocolos anteriores.

Los autores reconocen el trabajo concurrente de Bostanci et al. [BGH+26], que utiliza una separación de oráculo cuántico para probar límites inferiores más fuertes para desentrelazadores ($\log D = \Omega(\sqrt{d})$ para error constante); sin embargo, señalan que la reducción de Bostanci et al. no se aplica a las formulaciones de SDP generales, dejando los límites inferiores específicos de SDP (Teorema 5.4 y Corolario 5.5) como la contribución principal de este trabajo. Los resultados están respaldados por pruebas formales en Lean.