Optimising the relative entropy under semidefinite constraints

Resumen Técnico: Optimización de la Entropía Relativa bajo Restricciones Semidefinidas

Planteamiento del Problema
El problema central abordado es la minimización de la entropía relativa cuántica $D(\rho\|\sigma) = \text{tr}[\rho(\log \rho - \log \sigma)]$ sujeta a restricciones semidefinidas. Esta optimización surge en diversas tareas de información cuántica, notablemente en la estimación de tasas de claves secretas para la Distribución de Claves Cuánticas (QKD) a partir de estadísticas de medición de dispositivos reales. La formulación matemática busca encontrar:
$$\inf D(\rho\|\sigma) \quad \text{sujeto a} \quad h_i(\rho, \sigma) \ge 0, \quad \mu\sigma \le \rho \le \lambda\sigma, \quad \rho, \sigma \in \mathcal{S}(\mathcal{H})$$
donde $h_i$ son mapas afines que representan las restricciones de medición. Aunque el problema es convexo, es altamente no lineal debido al logaritmo de matrices, lo que hace que los resolvedores de optimización convexa estándar sean ineficaces para instancias generales. Los métodos existentes suelen tener problemas de estabilidad numérica, carecen de garantías de convergencia probables o están restringidos a tipos específicos de restricciones (por ejemplo, solo restricciones de igualdad).

Metodología
Los autores proponen un método basado en una representación integral recientemente introducida de la entropía relativa cuántica (Frenkel, 2023; Jenčová, 2015). Para estados que satisfacen $\mu\sigma \le \rho \le \lambda\sigma$, la entropía relativa se expresa como:
$$D(\rho\|\sigma) = \int_{\mu}^{\lambda} \frac{ds}{s} \text{tr}_+[\sigma s - \rho] + \log \lambda + 1 - \lambda$$
donde $\text{tr}_+[A]$ denota la parte positiva de la traza de $A$. La innovación técnica central es la discretización de esta integral para transformar el problema no lineal en una secuencia de Programas Semidefinidos (SDP).

1. Discretización y Formulación SDP: La integral se aproxima sobre una cuadrícula $t = (t_1, \dots, t_r)$. Al utilizar la propiedad de que $\text{tr}_+[A]$ puede formularse como un SDP (específicamente, $\text{tr}_+[A] = \sup_{0 \le P \le 1} \text{tr}[PA]$), los autores derivan una cota inferior de la entropía relativa. Esto resulta en un problema de minimización sobre variables auxiliares $\mu_k$ sujetas a desigualdades matriciales lineales.
2. Cotas Superior e Inferior: El método proporciona tanto cotas inferiores ($c_l(t)$) como cotas superiores ($c_u(t)$) sobre el valor óptimo.
   • Cota Inferior: Derivada mediante interpolación convexa (rectas secantes) del integrando, formulada como un SDP.
   • Cota Superior: Derivada mediante interpolación convexa desde arriba, también formulada como un SDP.
3. Estimación de la Brecha (Gap): La diferencia $\Delta(t) = c_u(t) - c_l(t)$ sirve como una estimación rigurosa de la brecha respecto al óptimo en cualquier etapa de la iteración.
4. Refinamiento de la Cuadrícula: Los autores establecen una estrategia de construcción de cuadrícula recursiva (Corolario 1) que asegura una convergencia sublineal. Los puntos de la cuadrícula se eligen de tal manera que el error disminuye como $O(\sqrt{\lambda/\epsilon})$, donde $\epsilon$ es la precisión objetivo.

Contribuciones Clave

• Cotas Probables: El trabajo proporciona una secuencia de SDPs que arrojan cotas superiores e inferiores rigurosas y probables para el problema de minimización de la entropía relativa.
• Garantías de Convergencia: El artículo demuestra la convergencia sublineal del esquema de discretización. Específicamente, demuestra que el número de puntos de la cuadrícula necesarios para alcanzar un error $\epsilon$ escala como $O(\sqrt{\lambda/\epsilon})$.
• Cuantificación de la Brecha: A diferencia de muchos heurísticos numéricos existentes, este método permite el cálculo explícito de la brecha respecto al óptimo en cada paso, permitiendo criterios de terminación basados en la precisión deseada.
• Generalización a f-Divergencias: La metodología se generaliza a $f$-divergencias arbitrarias, no solo a la entropía relativa de Umegaki, aprovechando las propiedades de convexidad de la función $g(s) = \text{tr}_+[\sigma s - \rho]$.
• Eficiencia de Recursos: El enfoque mantiene la eficiencia en términos de las dimensiones de las matrices SDP, evitando la escala $d^2 \times d^2$ requerida por los métodos que computan directamente los logaritmos de matrices.

Resultados
Los autores validan su método mediante pruebas comparativas numéricas:

• Tasas de Clave QKD: Aplicado a escenarios de QKD basados en entrelazamiento, el método computa con éxito la aleatoriedad extraíble (tasas de clave) para dimensiones locales de hasta 8 (3 cúbits por parte). Los resultados se obtienen en segundos en una computadora personal estándar.
• Comportamiento de Convergencia: Los experimentos numéricos confirman la tasa de convergencia sublineal predicha. El error disminuye a medida que aumenta el número de puntos de la cuadrícula, de forma consistente con las cotas teóricas derivadas en el Corolario 1.
• Desempeño Comparativo: Al compararse con métodos de vanguardia (específicamente [12] y [14]):
  • El método logra una precisión comparable a [12] para instancias pequeñas, pero es estrictamente superado en precisión por el resolvedor especializado [14] para la programación de entropía relativa.
  • En términos de tiempo de ejecución, el método propuesto muestra una clara mejora sobre [12] pero sigue siendo más lento que [14].
  • Una ventaja distintiva es la capacidad de proporcionar tanto cotas superiores como inferiores y cuantificar la brecha, mientras que [12] proporciona solo cotas superiores y [14] está restringido a conos específicos y carece de la flexibilidad de la representación integral para ciertos escenarios de información independiente del dispositivo.

Significado y Reivindicaciones
El artículo afirma que su principal significancia radica en proporcionar una herramienta práctica y eficiente en recursos que cierra la brecha entre las herramientas numéricas ejecutables y las cotas teóricas. Al convertir la difícil optimización no lineal en una secuencia de SDPs con convergencia demostrable, el método permite pruebas de seguridad fiables para la QKD y otras tareas de información cuántica donde las cotas inferiores rigurosas sobre la aleatoriedad extraíble son esenciales.

Los autores enfatizan que, si bien su método puede no ser el más rápido en términos de tiempo de ejecución bruto en comparación con resolvedores especializados como [14], su capacidad para manejar restricciones afines generales (desigualdades) y proporcionar estimaciones de brecha rigurosas lo hace único para aplicaciones que requieren cotas certificadas, como la QKD independiente del dispositivo y la estimación de capacidades de canales. El trabajo también abre la puerta a algoritmos numéricamente aplicables para acotar la entropía relativa de los canales, un problema abierto en las teorías de recursos.