\documentclass[landscape]{seminar}
\slideframe{none}
\usepackage{epsf}
\usepackage{color}
\usepackage{amssymb,amsfonts}

\newcommand{\ket}[1]{\left | \, #1 \right \rangle}
\newcommand{\bra}[1]{\left \langle #1 \, \right |}
\newcommand{\proj}[1]{{\left | \, #1 \right \rangle\!\left \langle #1 \, \right |}}
\newcommand{\vpols}{\mbox{$\updownarrow$}}
\newcommand{\hpols}{\mbox{$\leftrightarrow$}}

\newcommand{\ppols}{\mbox{\small
\,\mbox{$\nearrow$}\llap{\mbox{$\swarrow$}}\,}}

\newcommand{\qpols}{\mbox{\small
\,\mbox{$\searrow$}\llap{\mbox{$\nwarrow$}}\,}}

\newcommand{\rpols}{\mbox{\raisebox{-0.66ex}{$\triangleleft$}$\!\!\supset$}}
\newcommand{\lpols}{\mbox{$\subset\!\!$\raisebox{-0.66ex}{$\triangleright$}}}

\newcommand{\rz}{{\color{red}0}}
\newcommand{\ro}{{\color{red}1}}
\newcommand{\bz}{{\color{blue}0}}
\newcommand{\bo}{{\color{blue}1}}

\newcommand{\Tr}{{\mathrm{Tr}}}

\begin{document}

\begin{slide}
\begin{center}
{\large
Additivity Questions in Quantum Information Theory
}

Peter Shor\\
Dept.\ of Mathematics\\
MIT

\end{center}

\end{slide}

\begin{slide}
{\small
There are a number of interesting, open additivity questions in 
quantum information theory.  Four important such questions are 
equivalent.  Namely, 
\begin{enumerate}
\item Additivity of the minimum entropy of the output of a quantum channel
(a completely positive trace-preserving operator, or CPT operator).
\item Additivity of the entanglement of formation $E_F$.  
\item Additivity of the Holevo channel capacity $\chi$.
\item Strong superadditivity of the entanglement of formation $E_F$
(this probably should be called complete superadditivity of the 
entanglement of formation, but it's too late to change the name).
\end{enumerate}

Two other additivity questions have also been shown to be equivalent.
\end{slide}

\begin{slide}
There are other additivity quesitons which are not known to be 
equivalent.
\begin{itemize}
\item  Additivity of the quantum capacity of a quantum channel [we know
at least one channel for which this is non-additive, but how general is
this?].
\item  Additivity of the distillable entanglement [non-additive if there
are non-distillable negative partial transpose states, so probably 
non-additive in general].
\item  Additivity of the classical capacity of a quantum channel
assisted by limited entanglement.
\end{itemize}
\end{slide}
\begin{slide}
Outline.
\begin{itemize}
\item Introduce the additivity problems we prove equivalent.
\item Introduce three techniques that we use. 
\item Sketch one of the proofs.
\end{itemize}
\end{slide}

\begin{slide}
{\large Theorem} (Holevo, Schumacher-Westmoreland)

The classical-information capacity obtainable using codewords composed of
signal states $\rho_i$, where $\rho_i$ has marginal probability $p_i$,
is 

\[
\chi(\{\rho_i\}; \{p_i\}) = H_\mathrm{vN}(\sum_i p_i\rho_i) 
- \sum_i p_i H_\mathrm{vN}(\rho_i)
\]
where $H_{\mathrm{vN}(\rho)} = -\Tr (\rho \log \rho)$.

Does this give the capacity of a quantum channel $\cal{N}$?

Possible capacity formula:\\
Maximize $\chi(\{{\cal{N}}(\rho_i)\}; \{p_i\})$ over all output states 
${\cal N}(\rho_i)$ of the channel.
\end{slide}


% \begin{slide}
% {\large Unentangled Inputs, Separate Measurements}
% 
% \epsfxsize=6in
% \epsfbox{bigfig1.eps}
% 
% Maximize over probability distributions on inputs to
% the channel $\rho_i$, $p_i$:
% \[
% I_{\mathrm{acc}}(\{{\cal N}(\rho_i)\}; \{p_i\}) 
% \]
% \end{slide}

\begin{slide}

\parbox{1.7in}{
Unentangled Inputs\\ Joint Measurements\\*[.6ex]
\epsfxsize=1.5in
\epsfbox{bigfig2.eps}
Maximize over probability distributions on inputs to
the channel $\rho_i$, $p_i$, where $\rho_i$ is in the
input space of the channel:
\[
\chi(\{{\cal{N}}(\rho_i)\}; \{p_i\})
\]
}
\hspace*{\fill}
\parbox{1.7in}{
Entangled Inputs\\ Joint Measurements\\*[.6ex]
\epsfxsize=1.5in
\epsfbox{bigfig3.eps}
Maximize over probability distributions on inputs to
the channel $\rho_i$, $p_i$ where $\rho_i$ is in the 
tensor product space of $n$ channel inputs: 
\[
\lim_{n\rightarrow \infty} \frac{1}{n}\chi(\{{\cal{N}}^{\otimes n}(\rho_i)\}; \{p_i\})
\]
}

\end{slide}

\begin{slide}
{\large Open Question}

Is channel capacity additive?

Is $
\max \ \chi({\cal N}_1 \otimes {\cal N}_2) = 
\max \ \chi({\cal N}_1) + \max \ \chi({\cal N}_2)$?

If it is, then $\chi$ gives the classical-information
 capacity of a quantum channel.

\end{slide}

\begin{slide}
Minimum entropy output {\small (of a quantum channel)}

Is
\begin{eqnarray*}
\min_\rho \ H(({\cal N}_1 \otimes {\cal N}_2)(\rho)) &=& \\
\min_\rho \ H({\cal N}_1(\rho)) &+& \min_\rho \ H({\cal N}_2(\rho))?
\end{eqnarray*}
This comes from the idea that we want to minimize the second term 
in the expression for the Holevo capacity.

\end{slide}

\begin{slide}
Additivity of channel capacity implies additivity of minimum entropy
output.

Suppose we have two channels ${\cal N}_1$ and ${\cal N}_2$ and 
we want to show that their minimum entropy output is additive.  
Consider the channels ${\cal N}_a'$ with input space augmented by
a classical variable $x$ with $1 \leq x \leq d_{\mathrm{in}}^2$ 
defined as
\[
{\cal N}'_a (\rho, x) = U_x {\cal N} (\rho) U_x'
\]
where the $U_x$ are unitary and satisfy
\[
\sum_{x=1}^{d_\mathrm{in}^2} U_x \rho U_x' = I/d \quad \forall \rho
\]
This extra variable $x$ specifies a unitary transformation to be
applied on the channel output of $U$.  
\end{slide}

\begin{slide}
Then for ${\cal N}'$ the capacity is
\[
\max \chi{\cal N}'_a = \log d_\mathrm{in} 
- \min_\rho H({\cal N}_a(\rho))
\]
since we can take any input giving minimum entropy output on
${\cal N}$, and symmetrize it so
that we get $d^2$ input states to ${\cal N}'$ whose average entropy 
output is $I/d$
and each individual output has entropy $\min_\rho H({\cal N}(\rho)$,
and similarly for the tensor product 
${\cal N}_1' \otimes {\cal N}_2'$.

Thus, if Holevo capacity is additive for ${\cal N}_1'$ and ${\cal N}_2'$,
minimimum entropy output is additive for ${\cal N}_1$ and ${\cal N}_2$.
\end{slide}


%\begin{slide}
%When are two quantum systems {\em entangled}?
%
%Given a joint density matrix $\rho_{AB}$, we could ask
%
%\begin{itemize}
%\item
%Can we create $\rho_{AB}$ in two quantum laboratories using only a 
%telephone line to communicate between them?
%\item
%Can we make measurements whose outcomes do not satisfy Bell's inequality or
%a generalization (e.g., CHSH) of it?
%\item
%Can we make EPR pairs from many copies of $\rho_{AB}$ (i.e., $\rho_{AB}^{\otimes n}$)?
%\item
%Can we use a classical channel from Alice to Bob and a supply of shared states 
%$\rho_{AB}$ to teleport quantum information?
%\end{itemize}
%\end{slide}
%
%\begin{slide}
%$\rho_{AB}$ is called {\em separable} if it can be created in two quantum laboratories
%which only use a telephone line to communicate.
%
%A separable state can be made by Alice (in one laboratory) flipping a many-sided coin, 
%sending the results to Bob, and then both Alice and Bob making a specified pure 
%state depending on the outcome.  
%
%That is, a separable state can be expressed as
%\[
%\rho_{AB} = \sum_{i=1}^k p_i \ket{v_i}\bra{v_i} \otimes \ket{w_i}\bra{w_i}.
%\]
%
%Any state which is not separable is called entangled.
%\end{slide}
%
%\begin{slide}
%If $\rho_{AB}$ is a pure state, then we have a good definition of entanglement.
%
%\[
%E_P(\rho_{AB}) = H(\Tr_A \rho_{AB}) =H(\Tr_B \rho_{AB}) 
%\]
%
%Theorem {\small (Bennett, Bernstein, Popescu, Schumacher)}
%\begin{itemize}
%\item
%$n E_P(\rho_{AB}) -o(n)$ EPR pairs can be obtained from $n$ copies of $\rho_{AB}$,
%using local quantum operations, with high probability.
%\item
%$n$ copies of a state very close to $\rho_{AB}$ can be obtained from 
%$n E_P(\rho_{AB}) + o(n)$ EPR pairs, using local quantum operations and 
%classical communication.
%\end{itemize}
%\end{slide}
%
\begin{slide}
Entanglement cost: $E_C(\rho)$
\[
E_C(\rho) = \lim_{n \rightarrow \infty} \frac{1}{n} 
\left( \parbox{2in}{Number of EPR pairs needed to make
an approximation of $\rho^{\otimes n}$.}\right) 
\]

Distillable entanglement: $E_D(\rho)$
\[
E_D(\rho) \lim_{n \rightarrow \infty} \frac{1}{n} \left( \parbox{2in}{Number of approximate EPR pairs 
obtainable from $\rho^{\otimes n}$.}\right)
\]
The protocols above may use only local operations and 
classical communication.

Entanglement of formation.
\[
E_{F} = \min_{\rho = \sum_i p_i \rho_i} \sum_i p_i E_P(\rho_i)
\]
and the $\rho_i$ are pure states (rank 1).
\end{slide}

\begin{slide}
Conjecture: entanglement of formation is additive.
\[
E_{F}(\rho_1 \otimes \rho_2)=
E_{F}(\rho_1) + E_{F}(\rho_2).
\]
where
\[
E_{F} = \min_{\rho = \sum_i p_i \rho_i} \sum_i p_i E_P(\rho_i)
\]
and the $\rho_i$ are pure states (rank 1).

This would imply that entanglement cost is equal to entanglement
of formation.
\end{slide}

\begin{slide}
Strong Superadditivity of Entanglement of Formation

Instead of
\[
E_{F}(\rho_1 \otimes \rho_2)=
E_{F}(\rho_1) + E_{F}(\rho_2),
\]
we generalize to
\[
E_{F}(\rho ) \geq
E_{F}(\Tr_2 \rho) + E_{F}(\Tr_1 \rho).
\]
Other direction ($\leq$) is easy for tensor products, not true for general
mixed states.
\end{slide}

% NEED A QUADRIPARTITE PICTURE

\begin{slide}
Entanglement of Formation and Holevo capacity

Theorem (Stinespring) Any CPT map $\rho \rightarrow {\cal N}(\rho)$ can be 
implemented by first applying a unitary embedding of $\rho$ into a larger
Hilbert space 
\[
{\cal U}(\rho) = \rho \rightarrow U (\rho \otimes \proj{0}) U^\dag
\]
and then tracing out part of the larger Hilbert space
\[
\rho \rightarrow \Tr_2 U (\rho \otimes \proj{0}) U^\dag.
\]
\end{slide}
\begin{slide}
If $\rho_i = \proj{\psi}$ is a pure state, then
\begin{eqnarray*}
H({\cal N}(\rho_i)) &=& H(\Tr_2 U (\rho_i \otimes \proj{0}) U^\dag) \\
&=& E_P({\cal U}(\rho_i)).
\end{eqnarray*}
Thus
\begin{eqnarray*}
E_F({\cal U}(\rho)) &=& \min_{\rho = \sum_i p_i \rho_i}  \,\,\, \sum_i p_i E_P({\cal U}\rho_i)\\
&=& \min_{\rho = \sum_i p_i \rho_i} \,\,\, \sum_i p_i H({\cal N}(\rho_i))
\end{eqnarray*}
This is the second term in the Holevo capacity.
\end{slide}

\begin{slide}
This shows that entanglement of formation is equivalent to
constrained Holevo capacity, where constrained Holevo capacity
is defined as 
\[
\chi_\rho({\cal N}) = \max_{\sum_i p_i \rho_i = \rho} 
H({\cal N}(\rho) )
- \sum_i p_i H({\cal N}(\rho_i))
\]
This doesn't immediately imply that entanglement of formation is
equivalent to Holevo capacity because we can't arrange for the
maximum over $\rho$ to occur at the point where ${\cal U}(\rho) = \sigma$,
where $\sigma$ is the state for which we want fo find the entanglement of
formation.
\end{slide}

\begin{slide}
{\large Linear Programming Duality}

We need to compute
\[
\min_{\rho = \sum_i p_i \proj{v_i}} \,\,\, \sum_i p_i H({\cal N}(\proj{v_i}))
\]
Consider the problem as one of finding the $p_i$ corresponding to
every possible pure state $v_i$ (so $H(\proj{v_i})$ is known). That is,
\begin{eqnarray*}
\min_{p_i \geq 0} &&\sum_i p_i H({\cal N}(\proj{v_i}))
\\
 \mathrm{subject \ to } && \sum_i p_i \proj{v_i} = \rho 
\end{eqnarray*}
This is a linear program in the $p_i$.  

\end{slide}

\begin{slide}
Every linear program has a dual linear
program which has the same optimum value.  
For
\begin{eqnarray*}
\min_{p_i \geq 0} &&\sum_i p_i H({\cal N}(\proj{v_i}))
\\
 \mathrm{subject \ to } && \sum_i p_i \proj{v_i} = \rho 
\end{eqnarray*}
The dual program is
\begin{eqnarray*}
\max_\tau && \Tr \, \tau \rho
\\
 \mathrm{subject \ to } && \bra{v} \tau \ket{v} \leq H(N(\proj{v})) 
\end{eqnarray*}
where the last inequality must hold for all $\ket{v}$, and $\tau$ is
maximized over Hermitian matrices.
\end{slide}

\begin{slide}
Showing that these two lp's give the same value has one easy 
direction: 
\begin{eqnarray*}
\min_{p_i \geq 0} \sum_i p_i H({\cal N}(\proj{v_i})) & \geq & \sum_i p_i
\bra{v_i}\tau\ket{v_i} \\
&=& \Tr \sum_i p_i \tau \proj{v_i}\\
&=& \Tr \, \tau \rho
\end{eqnarray*}

The other direction requires use of the duality theorem for LP's
\end{slide}

\begin{slide}
We now sketch the proof that additivity of the minimum entropy output 
of a quantum channel implies additivity of entanglement of formation.

This is equivalent to additivity of constrained Holevo capacity
\[
\chi_\rho({\cal N}) = \max_{\sum_i p_i \rho_i = \rho} 
H({\cal N}(\rho) )
- \sum_i p_i H({\cal N}(\rho_i))
\]

Recall by the lp formulation that there is a matrix $\tau$ such
that 
\[
\Tr \, \rho_i \tau \leq H({\cal N}(\rho_i))
\]
with equality for signal states $\rho_i$. 

\end{slide}

\begin{slide}
If we could find another channel related to ${\cal N}$ such that
\[
H({\cal N}' (\rho)) = H({\cal N}(\rho)) + C  - \Tr \, \rho_i \tau
\]
then for signal states $\rho_i$, we have equality
\[
H({\cal N}' (\rho_i)) = H({\cal N}(\rho_i)) + C  - \Tr \, \rho_i \tau \\
= C
\]
and for other states, we have inequality
\[
H({\cal N}' (\rho_i)) = H({\cal N}(\rho_i)) + C  - \Tr \, \rho_i \tau 
\geq C
\]
so the signal states for this channel are exactly the minimum
entropy output states.
\end{slide}

\begin{slide}
Now suppose we have two channels ${\cal N}_1$ and ${\cal N}_2$.  We
find ${\cal N}'_1$ and ${\cal N}'_2$ as on the previous slide.  Now,
the additivity of minimum entropy output for ${\cal N}'_1$ and
${\cal N}'_2$ implies the additivity of the constrained Holevo
capacity for ${\cal N}'_1$ and ${\cal N}'_2$.  This is because
\begin{eqnarray*}
\chi_{\rho_1 \otimes \rho_2}({\cal N}_1 \otimes {\cal N}_2)  &\geq& 
H(({{\cal N}_1 \otimes N_2)}(\rho_1 \otimes \rho_2) ) \\ && \quad- 
\min_\sigma H(({\cal N}_1 \otimes {\cal N}_2) (\sigma))
\end{eqnarray*}
which is additive by assumption of additivity of minimum entropy output.

We then will have to show (using the construction of ${\cal N}_i'$) that
additivity of constrained Holevo capacity for 
${\cal N}'_1$ and ${\cal N}'_1$ implies its additivity for
${\cal N}_1$ and ${\cal N}_1$. 
\end{slide}

\begin{slide}
We actually cannot construct ${\cal N}'$ as advertised.  We just 
construct a sequence of such ${\cal N}'$s that come close.
Recall we wanted
\[
H({\cal N}' (\rho)) = H({\cal N}(\rho)) + C  - \Tr \, \rho \tau.
\]
{\small 
We choose ${\cal N}'$ to be the channel that with probability~$q$,
outputs ${\cal N}(\rho)$, and with probability $1-q$, makes a POVM
measurement with elements ${\bf E}$ and $I-{\bf E}$.  If the measurement
outcome is  ${\bf E}$, then ${\cal N}'$ outputs a pure state signifying
the result was $\bf E$ tensored with a maximally mixed state on $k$ qubits.  
If the result is $I-{\bf E}$, it outputs only a pure state signifying
this fact.  Then
\[
H({\cal N}'(\rho)) = qH({\cal N}(\rho)) + H_2(q)  
+ (1-q) k \Tr {\bf E} \rho + (1-q) H_2(\Tr {\bf E} \rho).
\]
First term: because ${\cal N}'$ outputs ${\cal N}(\rho)$
with probability $q$.\\
Second term: coin flip with probabilities $q$ \& $1-q$\\
Third term: we output a maximally mixed state on $k$ qubits \\*[-1ex]
\phantom{Third term:} with probability 
$(1-q) \Tr \, {\bf E} \rho$.\\
Last term: from the measurement ${\bf E}$.}
\end{slide}

\begin{slide}

We wanted a channel ${\cal N}'$ with
\[
H({\cal N}' (\rho)) = H({\cal N}(\rho)) + C  - \Tr \, \rho \tau.
\]

We found a channel ${\cal N}'$ with
{\small
\begin{eqnarray*}
H({\cal N}'(\rho)) = qH({\cal N}(\rho)) + H_2(q)  
+ (1-q) k \Tr {\bf E} \rho + (1-q) H_2(\Tr {\bf E} \rho).
\end{eqnarray*}}
If it weren't for the last term, we would be able to choose ${\bf E}$
to obtain exactly what we wanted (up to a constant factor).

By taking $k$ large and $q$ close to
$1$, we can make this last term go to zero while keeping the other 
terms the right relative sizes. 

We still have to show that additivity for 
${\cal N}_1'$ and ${\cal N}_2'$ implies additivity for
${\cal N}_1$ and ${\cal N}_2$.  This is not hard, and
completes our proof that (1) $\rightarrow$ (3).
\end{slide}

\begin{slide}
{\small
Recall the four questions to be shown equivalent.
\begin{enumerate}
\item Additivity of the minimum entropy of the output of a quantum channel
(a completely positive trace-preserving operator, or CPT operator).
\item Additivity of the entanglement of formation $E_F$.  
\item Additivity of the Holevo channel capacity $\chi$.
\item Strong superadditivity of the entanglement of formation $E_F$
(this probably should be called complete superadditivity of the 
entanglement of formation, but it's too late to change the name).
\end{enumerate}
\begin{enumerate}
\item[(1) $\rightarrow$ (2)] LP duality, Stinespring dilation, 
channel extension.
\item[(2) $\rightarrow$ (4)] LP duality
\item[(2) $\rightarrow$ (3)] Stinespring dilation, 
channel extension.
\end{enumerate}
}
\end{slide}


%\begin{slide}
%The phenomenon called superdense coding lets you send two bits per qubit
%over a noiseless quantum channel if the sender and receiver share
%entanglement. 
%
%\epsfxsize=6in
%\epsfbox{superdense-color.eps}
%
%By Holevo's theorem, the bound without prior shared entanglement is
%one bit per qubit.
%
%\end{slide}
%\begin{slide}
%Suppose that we have a quantum channel ${\cal N}$.  From
%superdense coding, if 
%${\cal N}$ is a noiseless quantum channel, 
%the sender could communicate twice as much classical information to a 
%receiver if they share EPR pairs than if they don't.  How does this
%generalize to noisy channels?  We call this quantity the 
%entanglement-assisted capacity and denote it by $C_E$.
%
%\end{slide}

\begin{slide}
{\large Formula for entanglement-assisted\\ capacity}

Theorem (Bennett, Shor, Smolin, Thapliyal)\\
\[
\max_\rho H_\mathrm{vN}( {\cal{N}} (\rho))
+ H_\mathrm{vN}( \rho)
 - H_\mathrm{vN}( {(\cal{N} \otimes I)} )(\Phi_\rho))
\]
$\Phi_\rho$ is a pure state on the tensor product of the input space
of the channel and a quantum space that the sender keeps, with
\[
{\mathrm{Tr}}_B \Phi_\rho = \rho . 
\]  When the
channel is classical, this formula turns into the entropy of the input
plus the entropy of the output less the entropy of the joint system.  

\end{slide}

\begin{slide}

{\large Generalization}

Suppose that the sender and the receiver have a limited amount of
entanglement (E ebits) they share.  How much can capacity can they obtain
from a quantum channel?

If the sender is not allowed to use entanglement between different
channel uses, the answer is:

\[
\max_{\rho_i : \bar{H}(\rho_i) \leq E}
\bar{H}(\rho_i) + H({\cal N}(\bar{\rho_i}))
- \bar{H}( {(\cal{N} \otimes I)} \Phi_{\rho_i})
\]

Here $\bar{H}$ means average over the entropy, and $\bar{\rho_i}$ means 
average over the state;  $\Phi_{\rho_i}$ is the pure entangled state 
(shared between sender and receiver) whose partial traces are $\rho_i$.  
This formula interpolates between the Holevo-Schumacher-Westmoreland
capacity and the entanglement-assisted capacity.
\end{slide}
\begin{slide}
Is this quantity additive?  We can reduce this question to that
of whether the quantity
\[
\max_\rho \lambda H(\rho) - H({\cal E}(\rho))
\]
is additive, where ${\cal E}$ is a CPT map.  If $\lambda = 0$, this
is the additivity of the minimum entropy output of a
quantum channel.  If $\lambda = 1$, this is the additivity of 
entanglement-assisted capacity.  For $0 < \lambda < 1$, this may be
a stronger conjecture than the other additivity conjectures.
\end{slide}
\end{document}
