hw2.tex

\documentclass[boxes,pages,color=SeaGreen]{homework}

\hypersetup{
    colorlinks=true,
    urlcolor=SeaGreen!60!black,
    linkcolor=Bittersweet
}
\newcommand{\collab}[1]{\footnote{\href{mailto:#1}{\texttt{#1}}}}

\name{Nate Stemen}
\studentid{20906566}
\email{nate@stemen.email}
\term{Fall 2021}
\course{Theory of Quantum Information}
\courseid{QIC 820}
\hwnum{2}
\duedate{Nov 5, 2021}

\hwname{Assignment}

\usepackage{physics}
\usepackage{relsize}
\usepackage{macros}
\usepackage{cleveref}
\usepackage{multirow}
\usepackage{booktabs}
\usepackage{todonotes}

%-----------------------------------------------------------------------------%
% Macros
%-----------------------------------------------------------------------------%

\renewcommand{\vec}{\operatorname{vec}}

\newcommand{\X}{\mathcal{X}}
\newcommand{\Y}{\mathcal{Y}}
\newcommand{\Z}{\mathcal{Z}}
\newcommand{\W}{\mathcal{W}}
\newcommand{\V}{\mathcal{V}}
\newcommand{\U}{\mathcal{U}}
\renewcommand{\P}{\mathcal{P}}
\newcommand{\Fid}{\operatorname{F}}

\newcommand{\Lin}{\mathrm{L}}
\newcommand{\Trans}{\mathrm{T}}
\newcommand{\Pos}{\mathrm{Pos}}
\newcommand{\Herm}{\mathrm{Herm}}
\newcommand{\Channel}{\mathrm{C}}
\newcommand{\Unitary}{\mathrm{U}}
\newcommand{\Density}{\mathrm{D}}
\newcommand{\CP}{\mathrm{CP}}

\newcommand{\triplenorm}[1]{
  \lvert\!\lvert\!\lvert #1
  \rvert\!\rvert\!\rvert}


\begin{document}

\def\arraystretch{1.2}

%-----------------------------------------------------------------------------%

\begin{problem}
Suppose that $\X$ and $\Y$ are complex Euclidean spaces and $M\in\Lin(\Y,\X)$
is a given operator.
Define a map $\Phi\in\Trans(\X\oplus\Y)$ as
\[
    \Phi\mqty(
    X & Z \\
    W & Y
    ) = \mqty(
    X & 0 \\
    0 & Y
    )
\]
for all $X\in\Lin(\X)$, $Y\in\Lin(\Y)$, $Z\in\Lin(\Y,\X)$, and
$W\in\Lin(\X,\Y)$ (i.e., $\Phi$ zeroes out the off-diagonal blocks of a
$2\times 2$ block operator of the form suggested in the equation), and
consider the semidefinite program
\[
    \qty(
    \Phi,
    \frac{1}{2}\mqty(0 & M \\ M^* & 0),
    \mqty(\1_{\X} & 0 \\ 0 & \1_{\Y})
    ).
\]

\begin{parts}
    \part
    Express the primal and dual problems associated with this semidefinite
    program in simple, human-readable terms.
    (There is no single, well-defined answer to this part of the problem---just
    do your best to make the primal and dual problems look as simple and
    elegant as possible.)\label{part:1a}

    \part
    Prove that strong duality holds for this semidefinite program.\label{part:1b}

    \part
    What is the optimal value of this semidefinite program?\label{part:1c}

\end{parts}
\end{problem}

\noindent Solution completed in collaboration with Alev Orfi,\collab{akborfi@uwaterloo.ca} and Muhammad Usman Farooq.\collab{mu7faroo@uwaterloo.ca}

{\noindent\color{SeaGreen!30}\rule{\textwidth}{1.5pt}}

\begin{solution}
    \ref{part:1a}
    Given the nice form of $\Phi$ we can start by doing some algebra to simplify the program.
    Starting with the definition of a semidefinite program we have
    \begin{center}
        \begin{tabular}{rl}
            $\underset{X}{\text{maximize}}$: & $\left\langle \frac{1}{2}\spmqty{0 & M \\ M^* & 0}, X\right\rangle$ \\ \cmidrule(lr{1em}){2-2}
            \multirow{2}{*}{subject to:}     & $\Phi(X) = \spmqty{\1_\X           & 0 \\ 0 & \1_\Y}$                         \\
                                             & $X\in\Pos(\X\oplus\Y)$.
        \end{tabular}
    \end{center}
    Taking $X = \smqty(A & B \\ C & D)$ together with the condition that $\Phi(X) = \smqty(A & 0 \\ 0 & D) = \smqty(\1_\X & 0 \\ 0 & \1_\Y)$ we see that $A = \1_\X$ and $B = \1_\Y$.
    Since $X\in\Pos(\X)$ it must also be hermitian ($X = X^*$), and hence $C = B^*$ making $X = \smqty(\1_\X & B \\ B^* & \1_\Y)$.
    We can now expand out the inner product we are trying to maximize as follows (temporarily omitting the $\frac{1}{2}$):
    \begin{align*}
        \left\langle\spmqty{0 & M                                               \\ M^* & 0}, \spmqty{\1_\X & B \\ B^* & \1_\Y}\right\rangle & = \tr\qty[\spmqty{MB^* & M \\ M^* & M^*B}] \\
                              & = \tr(MB^*) + \tr(M^*B)                         \\
                              & = \langle B, M\rangle + \langle B^*, M^*\rangle
    \end{align*}
    This allows us to rewrite the primal problem as
    \begin{center}
        \begin{tabular}{rl}
            $\underset{B}{\text{maximize}}$: & $\frac{1}{2}\langle B, M\rangle + \frac{1}{2}\langle B^*, M^*\rangle$     \\ \cmidrule(lr{1em}){2-2}
            \multirow{2}{*}{subject to:}     & $\spmqty{\1_\X                                                        & B \\ B^* & \1_Y} \in \Pos(\X\oplus\Y)$                         \\
                                             & $B\in\Lin(\Y, \X)$.
        \end{tabular}
    \end{center}
    In order to understand the dual problem we have to first know what $\Phi^*$ is.
    This can be calculated by the definition of a adjoint map: $\langle\Phi(X), Y\rangle = \langle X, \Phi^*(Y)\rangle$.
    \begin{align*}
        \langle\Phi\spmqty{X & Z \\ W & Y}, \spmqty{A & B \\ C & D}\rangle & = \tr(\spmqty{X^*A & \cdot \\ \cdot & Y^*D}) = \tr(X^*A) + \tr(Y^*D) = \langle X, A\rangle + \langle Y , D \rangle \\
        \langle\spmqty{X     & Z \\ W & Y}, \Phi^*\spmqty{A & B \\ C & D}\rangle & = \tr(\spmqty{X^*A' + W^*C' & \cdot \\ \cdot & Z^*B' + Y^*D'})
    \end{align*}
    In order for this to be equal to $\tr(X^*A) + \tr(Y^*D)$ we must have $A' = A$, $D' = D$, as well as $C' = 0 = B'$.
    This gives us the action of $\Phi^*$ as $\Phi^*\smqty(A & B \\ C & D) = \smqty(A & 0 \\ 0 & D)$ and hence $\Phi = \Phi^*$.

    To simplify the dual problem we first write it in it's full generality:
    \begin{center}
        \begin{tabular}{rl}
            $\underset{Y}{\text{minimize}}$: & $\left\langle \spmqty{\1_\X        & 0 \\ 0 & \1_\Y}, Y\right\rangle$ \\ \cmidrule(lr{1em}){2-2}
            \multirow{2}{*}{subject to:}     & $\Phi(Y) \geq \frac{1}{2}\spmqty{0 & M \\ M^* & 0}$    \\
                                             & $Y\in\Herm(\X\oplus \Y)$.
        \end{tabular}
    \end{center}
    With a little bit of algebra, together with the fact that $Y\in\Herm(\X\oplus\Y)$ this problem transforms to
    \begin{center}
        \begin{tabular}{rl}
            $\underset{A, D}{\text{minimize}}$: & $\tr(A) + \tr(D)$                 \\ \cmidrule(lr{1em}){2-2}
            \multirow{2}{*}{subject to:}        & $\spmqty{A        & -\frac{1}{2}M \\ -\frac{1}{2}M^* & D}\in\Pos(\X\oplus \Y)$    \\
                                                & $A\in\Herm(\X)$                   \\
                                                & $D\in\Herm(\Y)$.
        \end{tabular}
    \end{center}
    First we redefine $\tilde{A} = \frac{1}{2}A$ and $\tilde{D} = \frac{1}{2}D$.
    We can also show $\tilde{A}\in\Pos(\X)$ as follows.
    Since $T = \smqty(\tilde{A} & - M \\ -M^* & \tilde{D})\in\Pos(\X\oplus\Y)$ we know $x^*Tx\geq 0$ for all $x\in\X\oplus\Y$.
    In particular this is true for $x = \smqty(x_0 \\ 0)$ and $x = \smqty(0 \\ y_0)$ separately.
    This shows $x_0^*\tilde{A}x_0 \geq 0$ for all $x_0\in\X$ and $y_0^*\tilde{D}y_0 \geq 0$ for all $y_0\in\Y$.
    Thus our final dual problem has simplified to
    \begin{center}
        \begin{tabular}{rl}
            $\underset{A, D}{\text{minimize}}$: & $\frac{1}{2}\tr(A) + \frac{1}{2}\tr(D)$      \\ \cmidrule(lr{1em}){2-2}
            \multirow{2}{*}{subject to:}        & $\spmqty{A                              & -M \\ -M^* & D}\in\Pos(\X\oplus \Y)$    \\
                                                & $A\in\Pos(\X)$                               \\
                                                & $D\in\Pos(\Y)$.
        \end{tabular}
    \end{center}

    \ref{part:1b}
    We can now apply Lemma 3.18 to our primal problem.
    This means $\smqty(\1_\X & B \\ B^* & \1_\Y)\in\Pos(\X\oplus\Y)$ if and only if $B = \sqrt{\1_\X}K\sqrt{\1_\Y} = K$ for some $K\in\Lin(\Y,\X)$ with $\norm{K}\leq 1$.
    Thus $B$ is bounded $\norm{B} \leq 1$ and since $M$ is fixed $\alpha$ (optimum value for primal problem) must be finite.
    In order to use Slater's theorem for semidefinite programs I need to show there exists a $Y\in\Herm(\X\oplus\Y)$ such that $\Phi^*(Y) \geq \frac{1}{2}\smqty(0 & M \\ M^* & 0)$.
    That is we need to show for $A\in\Herm(\X)$ and $D\in\Herm(\Y)$ that
    \begin{equation*}
        \Phi\smqty(A & B \\ C & D) - \frac{1}{2}\smqty(0 & M \\ M^* & 0) \approx \smqty(A & - M \\ -M^* & D) \in \Pos(\X\oplus\Y).
    \end{equation*}
    I've used $\approx$ to get rid of the halves.
    This if the exact condition we have in the dual problem, but I'm stuck as to where to go from here.

    \ref{part:1c}
    The optimal value for this semidefinite program is the spectral norm: $\norm{M}_1$.
\end{solution}

%-----------------------------------------------------------------------------%

\begin{problem}
Let $\X$ be a complex Euclidean space, and define
\[
    \delta(P,Q) = \sqrt{\tr(P) + \tr(Q) - 2 \Fid(P,Q)}
\]
for all positive semidefinite operators $P,Q\in\Pos(\X)$.
Prove that $\delta$ satisfies these three properties:
\begin{parts}
    \part
    $\delta(P,Q) \geq 0$ for all $P,Q\in\Pos(\X)$, with $\delta(P,Q) = 0$ if
    and only if $P = Q$.\label{part:2a}
    \part
    $\delta(P,Q) = \delta(Q,P)$ for all $P,Q\in\Pos(\X)$.\label{part:2b}
    \part
    $\delta(P,Q) \leq \delta(P,R) + \delta(R,Q)$
    for all $P,Q,R\in\Pos(\X)$.\label{part:2c}
\end{parts}
(These are the three defining properties of a \emph{metric}.)

Hint: to prove that property (c) holds, first prove that if
$\Y$ is a complex Euclidean space with $\dim(\Y)\geq\dim(\X)$,
and $u\in\X\otimes\Y$ is any vector satisfying $\tr_{\Y}(u u^{\ast}) = P$,
then
\[
    \delta(P,Q) = \min_{v\in\X\otimes\Y}\qty\big{\norm{u - v} : \tr_{\Y}(v v^*) = Q}.
\]
\end{problem}

\begin{solution}
    \ref{part:2a}
    By the symmetry of $\delta$ (proved next) we can without loss of generality take $\tr(P)\geq \tr(Q)$.
    Then, because $\tr(X) \geq 0$ for all $X\in\Pos(\X)$ we have
    \begin{align*}
        \qty(\sqrt{\tr(P)} - \sqrt{\tr(Q)})^2  & \geq 0                                    \\
        \tr(P) + \tr(Q) - 2\sqrt{\tr(P)\tr(Q)} & \geq 0                                    \\
        \tr(P) + \tr(Q)                        & \geq 2\sqrt{\tr(P)\tr(Q)}                 \\
                                               & \geq 2\Fid(P, Q) \tag{Proposition 3.12:6}
    \end{align*}
    By the last inequality we have that the radicand is greater than or equal to 0, and hence $\delta(P, Q) \geq 0$.
    In order for $\delta(P, Q) = 0$, we must have both $\tr(P) = \tr(Q)$ and $Q = \lambda P$ again by proposition 3.12:6.
    Then we have $\tr(P) = \tr(\lambda P) = \lambda \tr(P)$ and hence $\lambda = 1$ implying $P = Q$.

    \ref{part:2b}
    The symmetry of $\delta$ follows immediately from Proposition 3.12:2 which states that $\Fid(P, Q) = \Fid(Q, P)$.
    \begin{equation*}
        \delta(P, Q) = \sqrt{\tr(P) + \tr(Q) - 2\Fid(P, Q)} = \sqrt{\tr(Q) + \tr(P) - 2\Fid(Q, P)} = \delta(Q, P)
    \end{equation*}

    \ref{part:2c}
    We start by proving the hint.
    Let $u\in\X\otimes\Y$ be a purification of $P$.
    \begin{align*}
        \delta(P, Q)^2 & = \min_v\qty{\langle u - v, u - v\rangle: \tr_\Y(vv^*) = Q}        \\
                       & = \min_v \qty{\norm{u}^2 + \norm{v}^2 - 2\Re(\langle u, v\rangle)} \\
                       & = \tr(P) + \tr(Q) - 2\max_v\qty{\Re(\langle u, v\rangle)}          \\
                       & \leq \tr(P) + \tr(Q) - 2\max_v\qty{\abs{\langle u, v\rangle}}      \\
                       & = \tr(P) + \tr(Q) - 2\Fid(P, Q) \tag{\small Uhlmann's theorem}
    \end{align*}
    Thus in order for the hint to be true (which it has to, that would be illegal otherwise) we must have $\max_v\qty{\Re(\langle u, v\rangle)} = \max_v\qty{\abs{\langle u, v \rangle}}$ which I cannot see why must be true.

    With the hint proved, let $p, q, r\in\X\otimes\Y$ be a purifications of $P$, $Q$ and $R$ respectively.
    \begin{align*}
        \delta(P, Q) & = \min_{q}\qty{\norm{p - q}}                                 \\
                     & = \min_{q}\qty{\norm{p - q - r + r}}                         \\
                     & \leq \min_{q}\qty{\norm{p - r} + \norm{r - q}}               \\
                     & \leq \min_{r}\qty{\norm{p - r}} + \min_{q}\qty{\norm{r - q}} \\
                     & = \delta(P, R) + \delta(R, Q)
    \end{align*}

\end{solution}

%-----------------------------------------------------------------------------%

\begin{problem}
Let $\Phi\in\Trans(\X,\Y)$ be a map, for complex Euclidean spaces $\X$ and
$\Y$.
Prove that
\[
    \triplenorm{\Phi}_1 =
    \max_{\rho_0,\rho_1\in\Density(\X)}
    \norm{
        \qty\big( \1_{\Y} \otimes \sqrt{\rho_0} ) J(\Phi)
        \qty\big( \1_{\Y} \otimes \sqrt{\rho_1} )
    }_1.
\]
\end{problem}

\noindent Solution completed in collaboration with Mohammad Ayyash,\collab{mmayyash@uwaterloo.ca} and Nicholas Zutt.\collab{nzutt@uwaterloo.ca}

{\noindent\color{SeaGreen!30}\rule{\textwidth}{1.5pt}}

\begin{solution}
    We begin with a lemma.
    \begin{lemma}
        Let $\X = \C^\Sigma$ and $\Y = \C^\Pi$ be complex euclidean spaces.
        For all $A, B\in\Lin(\X)$ and $\Phi\in\Trans(\X, \Y)$ we have
        \begin{equation*}
            \qty(\1_\Y\otimes A^\intercal)J(\Phi)\qty(\1_\Y\otimes\overline{B}) = \qty(\Phi\otimes\1_{\Lin(\X)})(\vec(A)\vec(B)^*).
        \end{equation*}
    \end{lemma}
    \begin{proof}
        We start by expanding the Choi matrix using the definition: $J(\Phi) = \sum_{a,b\in\Sigma}\Phi(E_{a,b})\otimes E_{a,b}$.
        \begin{equation*}
            \qty(\1_\Y\otimes A^\intercal)J(\Phi)\qty(\1_\Y\otimes\overline{B}) = \sum_{a,b\in\Sigma}\Phi(E_{a,b})\otimes A^\intercal E_{a,b}\overline{B}
        \end{equation*}
        Let's calculate $A^\intercal E_{a,b}\overline{B}$ expanding $A$ and $B$ in the standard basis as $A = \sum_{a,b\in\Sigma}\alpha_{a,b}E_{a,b}$ and $B = \sum_{a,b\in\Sigma}\beta_{a,b}E_{a,b}$.
        \begin{align*}
            A^\intercal E_{a,b}\overline{B} & = \qty[\sum_{c,d\in\Sigma}\alpha_{d,c}E_{c,d}]E_{a,b}\qty[\sum_{e,f\in\Sigma}\overline{\beta_{e,f}}E_{e,f}] \\
                                            & = \sum_{c,d,e,f\in\Sigma}\alpha_{d,c}\overline{\beta_{e,f}}\,E_{c,d}\,E_{a,b}\,E_{e,f}                      \\
                                            & = \sum_{c,f\in\Sigma}\alpha_{a,c}\overline{\beta_{b,f}}E_{c,f}
        \end{align*}
        Thus together we have
        \begin{align*}
            \qty(\1_\Y\otimes A^\intercal)J(\Phi)\qty(\1_\Y\otimes\overline{B}) & = \sum_{a,b,c,f\in\Sigma}\alpha_{a,c}\,\overline{\beta_{b,f}}\;\Phi(E_{a,b})\otimes E_{c,f}                               \\
                                                                                & = \qty(\Phi\otimes\1_{\Lin(\X)})\qty[\sum_{a,b,c,f\in\Sigma}\alpha_{a,c}\,\overline{\beta_{b,f}}\;E_{a,b}\otimes E_{c,f}]
        \end{align*}
        We we must show the argument to $\Phi\otimes\1_{\Lin(\X)}$ is equal to $\vec(A)\vec(B)^*$.
        \begin{align*}
            \sum_{a,b,c,f\in\Sigma}\alpha_{a,c}\,\overline{\beta_{b,f}}\;E_{a,b}\otimes E_{c,f} & = \qty[\sum_{a,c\in\Sigma}\alpha_{a,c}\;e_a\otimes e_c]\qty[\sum_{b,f\in\Sigma}\overline{\beta_{b,f}}\;e_b^*\otimes e_f^*] \\
                                                                                                & = \qty[\sum_{a,c\in\Sigma}\alpha_{a,c}\;e_a\otimes e_c]\qty[\sum_{b,f\in\Sigma}\beta_{b,f}\;e_b\otimes e_f]^*              \\
                                                                                                & = \vec(A)\vec(B)^*
        \end{align*}
        As desired.
    \end{proof}
    By Proposition 3.44:1 we know the completely bounded trace norm can be written $\triplenorm{\Phi}_1 = \max\qty{\norm{(\Phi\otimes\1_{\Lin(\X)})(uv^*)}_1: u,v\in\mathcal{S}(\X\otimes\X)}$.
    Applying the above lemma to this statement transforms it to
    \begin{equation*}
        \triplenorm{\Phi}_1 = \max_{A,B\in\Lin(\X)}\qty{\norm{\qty(\1_\Y\otimes A^\intercal)J(\Phi)\qty(\1_\Y\otimes\overline{B})}_1 : \norm{A}_2 = 1 = \norm{B}_2}
    \end{equation*}
    because $\vec(A)\in\mathcal{S}(\X\otimes\X)$ implies $\sqrt{\sum_{a,b\in\Sigma}\alpha_{a,b}^2} = 1$ which is exactly the expression for $\norm{A}_2$.
    Applying the polar decomposition to $A$ (and $B$) we have $A = UP$ where $U\in\Unitary(\X)$ and $P\in\Pos(\X)$.
    Using the fact that $\norm{X}_2 = \sqrt{\tr(X^*X)}$ we have
    \begin{equation*}
        1 = \norm{A}_2 = \tr(A^*A) = \tr(P^*U^*UP) = \tr(P^*P).
    \end{equation*}
    Since the unitary component does not affect the norm $\norm{\cdot}_2$, we are ranging over positive semi-definite operators $\rho \defeq P^*P$ such that $\tr \rho = 1$.
    That is, the maximum is attained when ranging over density operators.
    We can then express $A$ in terms of this density operator as $A = \sqrt{\rho}$.

    Using all these facts, together with the fact that $\sqrt{\rho}^\intercal$ can always be written as $\sqrt{\rho'}$ we have the desired equality:
    \begin{equation*}
        \triplenorm{\Phi}_1 = \max_{\rho_0,\rho_1\in\Density(\X)} \norm\Big{\qty(\1_\Y\otimes\sqrt{\rho_0})J(\Phi)\qty(\1_\Y\otimes\sqrt{\rho_1})}.
    \end{equation*}
\end{solution}

\end{document}