## Friday, 3 January 2014

### When a channel is "optimal"

Let $\X$ and $\Y$ be complex Euclidean spaces and let $H\in\Herm(\Y\otimes\X)$ be an arbitrary Hermitian operator. Consider the problem of maximizing the value
$\ip{H}{J(\Phi)}$
over all choices of a channel $\Phi\in\Channel(\X,\Y)$.

One may observe that there must always exist at least one choice of a channel $\Psi\in\Channel(\X,\Y)$ such that
$\ip{H}{J(\Psi)} = \sup\{\ip{H}{J(\Phi)}\,:\,\Phi\in\Channel(\X,\Y)\},$
by virtue of the fact that $\Channel(\X,\Y)$ is a compact set and $\Phi\mapsto\ip{H}{J(\Phi)}$ is a continuous function. For any channel $\Psi\in\Channel(\X,\Y)$ satisfying the identity above, let us say that $\Psi$ is optimal with respect to $H$.

Theorem:

$\Phi\in\Channel(\X,\Y)$ is optimal with respect to $H$ if and only if
$\I_{\Y} \otimes \tr_{\Y} ( H J(\Phi)) - H \in \Pos(\Y\otimes\X).$

Proof:

Let $\Z=\X\otimes\Y$. If $\Phi\in\Channel(\X,\Y)$, then the Choi representation $J (\Phi)$ satisfies
$J(\Phi)\in\Pos(\Z) \ \text{and} \ \tr_{\Y} (J(\Phi)=\I_{\Y}.$
Consider the semidefinite program defined by the triple $(\Omega, H, \I_{\X})$, where $H\in\Herm(\Z), \I_{\X}\in\Herm{\X}$, and $\Omega\in\Channel(\Z,\X)$ is defined as $\Omega(Z)=\tr_{\Y}(Z)$ so that $\Omega^*\in\Channel(\X,\Z)$ is given as $\Omega^*(X)=\I_{\Y}\otimes X$. Then the primal and dual problems can be expressed as
\begin{align*} Primal & & & &Dual& \\ &\max\ip{H}{J(\Phi)} & & & &\min\ip{\I_{\X}}{X} \\ \text{subject to:} \ & \tr_{\Y}(J(\Phi), & & &\text{subject to:} \ & \I_{\Y}\otimes X \geq H, \\ & J(\Phi)\in\Pos(\Z) &&&& X\in\Herm(\X) \end{align*}
Define the primal and dual feasible sets $\mathcal{A}$ and $\mathcal{B}$, respectively, as
$\mathcal{A}:=\{Z\in\Pos(\Z) : \Omega(Z)=\I_{\X}\} \ \text{and} \ \mathcal{B}:=\{ X\in\Herm(\X) : \Omega^*(X)\geq H\}.$
Also define the optimate values associated to the primal and dual problems as
$\alpha:=\sup\{\ip{H}{Z} : Z\in\mathcal{A}\} \ \text{and} \ \beta:=\inf\{\ip{\I_{\X}}{X} : X\in\mathcal{B}\}.$

Since there always exists some $\Psi\in\Channel(\X,\Y)$ that is optimal with respect to $H$ as claimed in the problem statement, the primal feasible set is nonempty.Thus, $\alpha$ is finite. Now, consider the spectral decomposition of $H$ and its spectrum of eigenvalues $spec(H)$. Let $\lambda=\max\{spec(H)\}$ be the largest eigenvalue, and consider the operator $\lambda\I_{\X}\in \Herm(\X)$. Then $\Omega^*(\lambda\I_{\X})=\I_{\Y}\otimes\lambda\I_{\X}>H$.  Therefore, strong duality holds by Slater's theorem (Theorem 1.11). This implies that $\alpha=\beta$ and there exists $Z\in\mathcal{A}$ such that $\ip{H}{Z}=\alpha$. Then by complementary slackness (Proposition 1.12), if $Z\in\mathcal{A}$ and $\X\in\mathcal{B}$ satisfy $\ip{H}{Z}=\ip{\I_{\X}}{X}$, it holds that $\Omega^*(X)Z=HZ$.

Now suppose that $\Phi\in\Channel(\X,\Y)$ is optimal with respect to $H$ so that $\ip{H}{J(\Phi)}=\alpha$, and that $\ip{H}{J(\Phi)}=\ip{\I_{\X}}{X}$ for some $X\in\mathcal{B}$.  Then by complementary slackness it follows that
\begin{align*} \Omega^*(X)J(\Phi)&=HJ(\Phi) \\ (\I_{\Y}\otimes X)J(\Phi)&=HJ(\Phi) \\ \tr_{\Y}((\I_{\Y}\otimes X)J(\Phi))&=\tr_{\Y}(HJ(\Phi)) \\ X&=\tr_{\Y}(HJ(\Phi)), \end{align*}
since $\tr_{\Y}(J(\Phi))=\I_{\X}$. Therefore, since $X\in\mathcal{B}$ satisfies $X\in\Herm(\X)$ and $\Omega^*(X)\geq H$. This implies that $\Omega^*(J(\Phi))=\I_{\Y}\otimes \tr_{\Y}(HJ(\Phi))\geq H$. That is, $\I_{\Y}\otimes \tr_{\Y}(HJ(\Phi))-H\geq 0$, or in other words $\I_{\Y}\otimes \tr_{\Y}(HJ(\Phi))-H\in\Pos(\Z)=\Pos(\Y\otimes\X)$.

Suppose instead that $\I_{\Y}\otimes \tr_{\Y}(HJ(\Phi))-H\in\Pos(\Z)=\Pos(\Y\otimes\X)$ holds for some $\Phi\in\Channel(\X,\Y)$. This is equivalent to writing $\I_{\Y}\otimes \tr_{\Y}(HJ(\Phi))\geq H$ or $\Omega^*(\tr_{\Y}(HJ(\Phi))\geq H$. Moreover, since $J(\Phi)\in\Pos(\Z)\subset\Herm(\Z)$ and $H\in\Herm(Z)$, the product $HJ(\Phi)\in\Herm(\Z)$ as well. Also, because $\tr_{\Y}\in\Channel(\Z,\X)$ is Hermiticity-preserving, this implies that $\tr_{\Y}(HJ(\Phi)\in\Herm(\X)$. Hence, $\tr_{\Y}(HJ(\Phi)\in\mathcal{B}$ as it satisfies the conditions for being dual feasible. The quantity $\ip{\I_{\X}}{\tr_{\Y}(HJ(\Phi)}$ therefore places an upper bound on the possible values of $\ip{H}{Z}$ for any primal feasible $Z\in\mathcal{A}$. Thus, $\ip{H}{Z}\leq\ip{\I_{\X}}{\tr_{\Y}(HJ(\Phi)}$. However, observe that
\begin{align*} \ip{\I_{\X}}{\tr_{\Y}(HJ(\Phi)}=\tr_{\X}(\tr_{\Y}(HJ(\Phi))=\tr_{\Y\otimes\X}(HJ(\Phi))=\ip{H}{J(\Phi)}, \end{align*}
which actually implies that $\ip{H}{Z}=\ip{\I_{\X}}{\tr_{\Y}(HJ(\Phi)}$. Hence, it must be the case that $\tr_{\Y}(HJ(\Phi)$ is a solution to the dual problem, and that $J(\Phi)$ is a solution to the primal problem since $J(\Phi)\in\mathcal{A}$ by virtue of $\Phi\in\Channel(\X,\Y)$. Thus, $\Phi\in\Channel(\X,\Y)$ is optimal with respect to $H$.

It has now been shown that $\Phi\in\Channel(\X,\Y)$ is optimal with respect to $H$ if and only if $\I_{\Y}\otimes \tr_{\Y}(HJ(\Phi))-H\in\Pos(\Y\otimes\X)$.