\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}