Suavizar es optimizar

La definición $D_{\max}^{\varepsilon} = \min_{\tilde\rho} D_{\max}(\tilde\rho\|\sigma)$ es, leída con cuidado, un programa de optimización: minimizamos una función sobre un conjunto de estados. La buena noticia es que tanto la función como el conjunto son convexos y, mejor aún, representables como una SDP. El título del módulo —«suavizado y optimización»— es, en el fondo, una sola idea.

El suavizado es una optimización convexa

Desmontemos el problema en sus dos ingredientes. El primero es el objetivo, la propia $D_{\max}$ . Ya vimos en el Módulo 02 que $D_{\max}(\tilde\rho\|\sigma) = \log_2 \min\{\mu : \tilde\rho \preceq \mu\,\sigma\}$ , así que minimizarla equivale a buscar el menor $\mu$ con $\tilde\rho \preceq \mu\,\sigma$ — una restricción afín en operadores.

El segundo es el dominio, la bola $P(\rho,\tilde\rho) \le \varepsilon$ . Como $P = \sqrt{1 - F^2}$ , pedir $P \le \varepsilon$ es lo mismo que pedir $F(\rho,\tilde\rho) \ge \sqrt{1 - \varepsilon^2}$ , una cota inferior sobre la fidelidad fidelidad. Y aquí está el hecho clave: la fidelidad es representable como SDP. Existe un programa semidefinido cuyo óptimo es exactamente $F(\rho,\tilde\rho)$ , de modo que «la fidelidad es al menos $c$ » se traduce en restricciones lineales de operadores sobre variables auxiliares.

Juntando ambos ingredientes, la entropía max-relativa suavizada es el valor de una programa semidefinido SDP: minimizar $\mu$ sobre la variable $\tilde\rho \succeq 0$ sujeta a

\tilde\rho \preceq \mu\,\sigma, \qquad F(\rho, \tilde\rho) \ge \sqrt{1 - \varepsilon^2}, \qquad \operatorname{Tr}\tilde\rho \le 1.

Con esto, la dualidad fuerte dualidad, los certificados y toda la maquinaria del Módulo 01 quedan a nuestra disposición para calcular entropías suavizadas — no solo para definirlas.

El significado del error ε

Merece la pena insistir en qué es ese $\varepsilon$ . No es un artificio matemático: es el error tolerado ε error que la tarea admite. Las entropías suavizadas caracterizan las tareas de una toma con ese margen: cuántos bits se pueden comprimir permitiendo una probabilidad de error $\varepsilon$ , cuánta aleatoriedad se extrae con una desviación $\varepsilon$ respecto de la uniforme, y así sucesivamente. La versión cruda ( $\varepsilon = 0$ ) corresponde a exigir perfección; el mundo real vive en $\varepsilon > 0$ , y por eso son las cantidades suavizadas las que aparecen en los teoremas operacionales.

Ejemplos resueltos

Ejemplo resuelto 1 · El suavizado, resuelto como optimización

Problema. Con $p = (0.5,\ 0.5)$ y $q = (0.25,\ 0.75)$ , plantea el suavizado como una optimización explícita en una variable y resuélvelo para $\varepsilon = 0.1$ (distancia de traza).

El problema. Con $\tilde p = (\tilde p_0, 1 - \tilde p_0)$ y $|\tilde p_0 - 0.5| \le 0.1$ , minimizamos

g(\tilde p_0) = \log_2 \max\!\Big(\underbrace{\tfrac{\tilde p_0}{0.25}}_{\text{crece}},\ \underbrace{\tfrac{1 - \tilde p_0}{0.75}}_{\text{decrece}}\Big).

La estructura. Una rama crece con $\tilde p_0$ y la otra decrece; su máximo se minimiza donde se cruzan, en $\tilde p_0 = 0.25$ (ahí ambas valen $1$ y $g = 0$ ). Como partimos de $0.5$ y el cruce está por debajo, conviene bajar $\tilde p_0$ todo lo posible.

La solución. El presupuesto solo deja llegar a $\tilde p_0 = 0.4$ . Ahí la rama creciente domina, así que $D_{\max}^{0.1} = \log_2 \tfrac{0.4}{0.25} = \log_2 1.6 \approx 0.678$ bits (frente a $\log_2 2 = 1$ sin suavizar). El óptimo cae en el borde de la bola — la firma de que esto es, en efecto, una optimización con restricción activa.

Ejemplo resuelto 2 · Reconocer la SDP

Problema. Empareja el programa de la entropía suavizada con el programa cónico general del Módulo 01: ¿cuál es la variable, cuál el objetivo y cuáles las restricciones?

Solución. Las variables son el par $(\mu, \tilde\rho)$ con $\tilde\rho \succeq 0$ (viven, pues, en $\mathbb{R} \times \operatorname{Pos}$ ). El objetivo es lineal: minimizar $\mu$ (después tomamos $\log_2$ , que es monótono y no altera el minimizador). Las restricciones son todas de tipo cónico o afín:

$\mu\,\sigma - \tilde\rho \succeq 0$ (la parte de $D_{\max}$ );
$F(\rho,\tilde\rho) \ge \sqrt{1 - \varepsilon^2}$ (la bola), a su vez una SDP en variables auxiliares;
$\operatorname{Tr}\tilde\rho \le 1$ (subnormalización), lineal.

Todo encaja en la plantilla del programa semidefinido: objetivo lineal, cono $\operatorname{Pos}$ , restricciones afines. Suavizar es, literalmente, resolver una SDP.

Ejercicios

Ejercicio 1

Explica por qué tomar $\log_2$ al final no cambia cuál es el estado óptimo $\tilde\rho$ , y por qué eso permite trabajar con la SDP «sin logaritmo» minimizando $\mu$ .

Solución

El logaritmo es una función estrictamente creciente, así que minimizar $\mu$ y minimizar $\log_2 \mu$ se alcanzan en el mismo $(\mu, \tilde\rho)$ . Conviene resolver la SDP «sin logaritmo» —que es lineal en $\mu$ — y aplicar $\log_2$ al valor óptimo al terminar. Es el mismo truco que usamos en el Módulo 02 para escribir la min-entropía como $2^{-H_{\min}} = \min \operatorname{Tr}\tau_B$ .

Ejercicio 2

En el ejemplo resuelto 1, ¿qué habría pasado si el presupuesto hubiera sido $\varepsilon = 0.3$ en lugar de $0.1$ ?

Solución

Con $\varepsilon = 0.3$ podríamos bajar $\tilde p_0$ de $0.5$ hasta $0.2$ , pero el cruce óptimo está en $0.25$ : pasarse de largo no ayuda (la rama decreciente empezaría a subir el máximo). Nos detenemos en el cruce $\tilde p_0 = 0.25 = q_0$ , donde $\tilde p = q$ y $D_{\max}^{0.3} = 0$ . La restricción de la bola deja de estar activa: el óptimo cae en el interior.

Y de aquí, al Módulo 04. Ya tenemos una cantidad robusta y calculable. La siguiente pregunta es qué ocurre al regularizar: promediar la max-relativa suavizada sobre muchas copias y dejar $n \to \infty$ . Ahí es donde el régimen de una toma reconecta con las cantidades asintóticas de las que partimos.