\documentclass[aps,10.4pt,twocolumn, twoside]{revtex4}

\usepackage{amsmath, amsthm, amssymb,color,url,booktabs}  
%\usepackage[pdftex]{hyperref} 

\newcommand{\nc}{\newcommand}
\nc{\rnc}{\renewcommand}

\newcommand{\bra}[1]{\left\langle #1\right|}
\newcommand{\ket}[1]{\left|#1\right\rangle}
\newcommand{\proj}[1]{\left|#1\right\rangle\left\langle #1\right|}
\newcommand{\braket}[2]{\left\langle #1\middle|#2\right\rangle}
\newcommand{\vev}[1]{\left\langle #1\right\rangle}

\DeclareMathOperator{\abs}{abs}
\DeclareMathOperator{\Bin}{Bin}
\DeclareMathOperator{\conv}{conv}
\DeclareMathOperator{\id}{id}
\DeclareMathOperator{\Img}{Im}
\DeclareMathOperator{\inj}{inj}
\DeclareMathOperator{\Par}{Par}
\DeclareMathOperator{\poly}{poly}
\DeclareMathOperator{\polylog}{polylog}
\DeclareMathOperator{\tr}{tr}
\DeclareMathOperator{\rank}{rank}
\DeclareMathOperator{\sgn}{sgn}
\DeclareMathOperator{\Sep}{Sep}
\DeclareMathOperator{\SepSym}{SepSym}
\DeclareMathOperator{\Span}{span}
\DeclareMathOperator{\supp}{supp}
\DeclareMathOperator{\swap}{SWAP}
\DeclareMathOperator{\Sym}{Sym}
\DeclareMathOperator{\ProdSym}{ProdSym}
\DeclareMathOperator{\SEP}{SEP}
\DeclareMathOperator{\Sch}{Sch}
\DeclareMathOperator{\PPT}{PPT}
\DeclareMathOperator{\Wg}{Wg}
\DeclareMathOperator{\WMEM}{WMEM}
\DeclareMathOperator{\WOPT}{WOPT}

\DeclareMathOperator{\BPP}{\mathsf{BPP}}
\DeclareMathOperator{\BQP}{\mathsf{BQP}}
\DeclareMathOperator{\cnot}{\normalfont\textsc{cnot}}
\DeclareMathOperator{\DTIME}{\mathsf{DTIME}}
\DeclareMathOperator{\NTIME}{\mathsf{NTIME}}
\DeclareMathOperator{\MA}{\mathsf{MA}}
\DeclareMathOperator{\NP}{\mathsf{NP}}
\DeclareMathOperator{\NEXP}{\mathsf{NEXP}}
\DeclareMathOperator{\Ptime}{\mathsf{P}}
\DeclareMathOperator{\QMA}{\mathsf{QMA}}
\DeclareMathOperator{\QCMA}{\mathsf{QCMA}}
\DeclareMathOperator{\BellQMA}{\mathsf{BellQMA}}

\def\sat{\text{3-SAT}}
\def\be#1\ee{\begin{equation}#1\end{equation}}
\def\bea#1\eea{\begin{eqnarray}#1\end{eqnarray}}
\def\beas#1\eeas{\begin{eqnarray*}#1\end{eqnarray*}}
\def\ba#1\ea{\begin{align}#1\end{align}}
\def\bas#1\eas{\begin{align*}#1\end{align*}}
\def\bpm#1\epm{\begin{pmatrix}#1\end{pmatrix}}
\def\non{\nonumber}
\def\nn{\nonumber}
\def\eq#1{(\ref{eq:#1})}
\def\eqs#1#2{(\ref{eq:#1}) and (\ref{eq:#2})}
%\def\eq#1{Eq.~(\ref{eq:#1})}
%\def\eqs#1#2{Eqs.~(\ref{eq:#1}) and (\ref{eq:#2})}
\def\L{\left} 
\def\R{\right}
\def\ra{\rightarrow}
\def\ot{\otimes}
\nc{\grad}{{\vec{\nabla}}}
\newcommand{\iso}[1]{\stackrel{#1}{\cong}}

\def\cA{\mathcal{A}}
\def\cB{\mathcal{B}}
\def\cC{\mathcal{C}}
\def\cD{\mathcal{D}}
\def\cE{\mathcal{E}}
\def\cF{\mathcal{F}}
\def\cG{\mathcal{G}}
\def\cH{\mathcal{H}}
\def\cI{{\cal I}}
\def\cJ{\mathcal{J}}
\def\cK{\mathcal{K}}
\def\cL{{\cal L}}
\def\cM{{\cal M}}
\def\cN{\mathcal{N}}
\def\cO{{\cal O}}
\def\cP{\mathcal{P}}
\def\cQ{\mathcal{Q}}
\def\cR{\mathcal{R}}
\def\cS{\mathcal{S}}
\def\cT{{\cal T}}
\def\cU{\mathcal{U}}
\def\cV{\mathcal{V}}
\def\cW{{\cal W}}
\def\cX{{\cal X}}
\def\cY{{\cal Y}}
\def\cZ{\mathcal{Z}}

\def\bp{\mathbf{p}}
\def\bq{\mathbf{q}}
\def\bP{{\bf P}}
\def\bQ{{\bf Q}}
\def\gl{\mathfrak{gl}}

\def\bbC{\mathbb{C}}
\DeclareMathOperator*{\E}{\mathbb{E}}
\DeclareMathOperator*{\bbE}{\mathbb{E}}
\def\bbF{\mathbb{F}}
\def\bbM{\mathbb{M}}
\def\bbN{\mathbb{N}}
\def\bbR{\mathbb{R}}
\def\bbZ{\mathbb{Z}}
\newcommand{\Real}{\textrm{Re}}

\def\benum{\begin{enumerate}}
\def\eenum{\end{enumerate}}
\def\bit{\begin{itemize}}
\def\eit{\end{itemize}}
\newcommand{\fig}[1]{Fig.~\ref{fig:#1}}
\newcommand{\secref}[1]{Section~\ref{sec:#1}}
\newcommand{\appref}[1]{Appendix~\ref{sec:#1}}
\newcommand{\lemref}[1]{Lemma~\ref{lem:#1}}
\newcommand{\thmref}[1]{Theorem~\ref{thm:#1}}
\newcommand{\propref}[1]{Proposition~\ref{prop:#1}}
\newcommand{\protoref}[1]{Protocol~\ref{proto:#1}}
\newcommand{\defref}[1]{Definition~\ref{def:#1}}
\newcommand{\corref}[1]{Corollary~\ref{cor:#1}}
\newcommand{\conref}[1]{Conjecture~\ref{con:#1}}

\newcommand{\FIXME}[1]{{\color{red}FIXME: #1}}
\nc{\todo}[1]{\textcolor{red}{todo: #1}}

\newcommand{\boxdfn}[2]{
\begin{figure}[h]\begin{center}
\noindent \framebox{\begin{minipage}{0.8\textwidth}
\begin{dfn}[{\bf #1}]\ \\ \\#2
\end{dfn}\end{minipage}}
\end{center}\end{figure}}

\newcommand{\boxproto}[2]{
\begin{figure}[h]\begin{center}
\noindent \framebox{\begin{minipage}{0.8\textwidth}
\begin{proto}[{\bf #1}]\ \\ \\#2\end{proto}
\end{minipage}}
\end{center}\end{figure}}

\def\begsub#1#2\endsub{\begin{subequations}\label{eq:#1}\begin{align}#2\end{align}\end{subequations}}
\nc\qand{\qquad\text{and}\qquad}
\nc\mnb[1]{\medskip\noindent{\bf #1}}

\usepackage{amsthm}
\usepackage{amsmath,latexsym,amssymb,verbatim,enumerate,graphicx}
%\usepackage{hyperref}
\usepackage{color}


\renewcommand{\familydefault}{ppl}
\renewcommand{\baselinestretch}{1.0}

%\usepackage{xypic}
%\usepackage{theorem}
\newtheorem{definition}{Definition} %[section]
\newtheorem{prop}[definition]{Proposition}
\newtheorem{lemma}[definition]{Lemma}
\newtheorem{algorithm}[definition]{Algorithm}
\newtheorem{fact}[definition]{Fact}
%\newtheorem{theorem}[definition]{Theorem}
\newtheorem{thm}[definition]{Theorem}
\newtheorem{corollary}[definition]{Corollary}
\newtheorem{conjecture}[definition]{Conjecture}

\newtheorem*{rep@theorem}{\rep@title}
\newcommand{\newreptheorem}[2]{%
\newenvironment{rep#1}[1]{%
 \def\rep@title{#2 \ref{##1} (restatement)}%
 \begin{rep@theorem}}%
 {\end{rep@theorem}}}
\makeatother

\newreptheorem{thm}{Theorem}
\newreptheorem{lem}{Lemma}


\def\ba#1\ea{\begin{align}#1\end{align}}
\def\ban#1\ean{\begin{align*}#1\end{align*}}

%Michal
\def\hcal{{\cal H}}

\def\tred{\textcolor{red}}


%\newcommand{\bea}{\begin{array}}
%\newcommand{\eea}{\end{array}}


\def\locHam{{\sc local Hamiltonian}}
\def\gappedlocHam{{\sc Gapped local Hamiltonian}}
\def\partition{{\sc Partition Function}}
\def\spec{{\sc Spectral Density}}
\def\BQP{{\sf{BQP}}}
\def\PH{{\sf{PH}}}
\def\COLORING{{\sf{COLORING}}}
\def\FACTORING{{\sf{FACTORING}}}
\def\MAJORITY{{\sf{MAJORITY}}}
\def\FC{\textsc{Fourier Checking}}
\def\CC{\textsc{Circuit Checking}}
%\def\FC{{\sf{Fourier \hspace{0.08 cm} Checking}}}
%\def\CC{{\sf{Circuit \hspace{0.08 cm} Checking}}}
\def\BPP{{\sf{BPP}}}
\def\QCMA{{\sf{QCMA}}}
\def\SZK{{\sf{SZK}}}
\def\QMA{{\sf{QMA}}}
\def\UQCMA{{\sf{UQCMA}}}
\def\BellQMA{{\sf{BellQMA}}}
\def\LOCCQMA{{\sf{LOCCQMA}}}
\def\BPTIME{{\sf{BPTIME}}}
\def\DQC{{\sf{DQC1}}}
\def\NP{{\sf{NP}}}
\def\UNP{{\sf{UNP}}}
\def\UcoNP{{\sf{Uco-NP}}}
\def\MA{{\sf{MA}}}
\def\A{{\sf{A}}}
\def\PSPACE{{\sf{PSPACE}}}
\def\P{{\sf{P}}}
\def\U{{\sf{U}}}
\def\PP{{\sf{PP}}}
%\def\poly{{\sf{poly}}}
\def\SAT{{\sf{SAT}}}
\def\YES{{\sf{YES}}}
\def\NO{{\sf{NO}}}
\def\RFS{{\sf{RFS }}}
\def\benum{\begin{enumerate}}
\def\eenum{\end{enumerate}}

%\renewcommand{\thetheorem}{\Roman{theorem}}

\def\lpolskie{\l}

\def\nn{\nonumber}
\def\norm#1{ {|\hspace{-.022in}|#1|\hspace{-.022in}|} }
\def\Norm#1{ {\big|\hspace{-.022in}\big| #1 \big|\hspace{-.022in}\big|} }
\def\NOrm#1{ {\Big|\hspace{-.022in}\Big| #1 \Big|\hspace{-.022in}\Big|} }
\def\NORM#1{ {\left|\hspace{-.022in}\left| #1 \right|\hspace{-.022in}\right|} }

\def\squareforqed{\hbox{\rlap{$\sqcap$}$\sqcup$}}
\def\qed{\ifmmode\squareforqed\else{\unskip\nobreak\hfil
\penalty50\hskip1em\null\nobreak\hfil\squareforqed
\parfillskip=0pt\finalhyphendemerits=0\endgraf}\fi}
\def\endenv{\ifmmode\;\else{\unskip\nobreak\hfil
\penalty50\hskip1em\null\nobreak\hfil\;
\parfillskip=0pt\finalhyphendemerits=0\endgraf}\fi}
%\newenvironment{proof}{\noindent \textbf{{Proof~} }}{\qed}
%\newenvironment{proof}[1][Proof]{\noindent \textbf{{#1~} }}{\qed}
%\newenvironment{remark}{\noindent \textbf{{Remark~}}}{\qed}
\newenvironment{example}{\noindent \textbf{{Example~}}}{\qed}

%\font\gensymbols=drgen10
%\def\male{{\gensymbols\char"1A}}
%\def\female{{\gensymbols\char"19}}

\newcommand{\exampleTitle}[1]{\textsl{}bf{(#1)}}
\newcommand{\remarkTitle}[1]{\textbf{(#1)}}
\newcommand{\proofComment}[1]{\exampleTitle{#1}}


\newcommand{\<}{\langle}
\renewcommand{\>}{\rangle}
\newcommand{\I}{{\rm I}}
\def\L{\left}
\def\R{\right}

\def\id{{\operatorname{id}}}
\DeclareMathOperator{\ad}{ad}

\def\ep{\epsilon}
\def\eps{\epsilon}
\def\ecal{{\cal E}}
\def\hcal{{\cal H}}
\def\gcal{{\cal G}}

\newcommand{\mbp}{$\spadesuit$}

% Align := properly in math mode
\mathchardef\ordinarycolon\mathcode`\:
\mathcode`\:=\string"8000
\def\vcentcolon{\mathrel{\mathop\ordinarycolon}}
\begingroup \catcode`\:=\active
  \lowercase{\endgroup
  \let :\vcentcolon
  }

\nc{\avg}[1]{\langle#1\rangle}
\def\Bra#1{{\big\langle #1 \big|  }}
\def\Ket#1{{\big| #1 \big\rangle }}
\def\BRA#1{{\left\langle #1 \right|  }}
\def\KET#1{{\left| #1 \right\rangle }}
%\rnc{\max}{\operatorname{max}} \nc{\rank}{\operatorname{rank}}
\nc{\smfrac}[2]{\mbox{$\frac{#1}{#2}$}} \nc{\Tr}{\operatorname{Tr}}
\nc{\ox}{\otimes} \nc{\dg}{\dagger} \nc{\dn}{\downarrow}
\nc{\lmax}{\lambda_{\text{max}}}
\nc{\lmin}{\lambda_{\text{min}}}




\nc{\csupp}{{\operatorname{csupp}}}
\nc{\qsupp}{{\operatorname{qsupp}}} \nc{\var}{\operatorname{var}}
\nc{\rar}{\rightarrow} \nc{\lrar}{\longrightarrow}

\nc{\Lip}{\operatorname{Lip}}
%\nc{\1}{\openone} \nc{\supp}{{\operatorname{supp}}}
%\nc{\ep}{\epsilon}
\nc{\Om}{\Omega}
\nc{\wt}[1]{\widetilde{#1}}

\def\a{\alpha}
\def\b{\beta}
\def\g{\gamma}
\def\d{\delta}
\def\e{\epsilon}
\def\ve{\varepsilon}
\def\z{\zeta}
%\def\h{\eta}
\def\t{\theta}
%\def\i{\iota}
\def\k{\kappa}
%\def\l{\lambda}
\def\m{\mu}
\def\n{\nu}
\def\x{\xi}
\def\p{\pi}
\def\r{\rho}
\def\s{\sigma}
\def\ta{\tau}
\def\u{\upsilon}
\def\ph{\varphi}
\def\ps{\psi}
\def\o{\omega}
\def\om{\omega}

\def\G{\Gamma}
\def\D{\Delta}
\def\T{\Theta}
%\def\L{\Lambda}
\def\X{\Xi}

\def\S{\Sigma}
\def\Ph{\Phi}
\def\Ps{\Psi}
\def\O{\Omega}
\def\Psd{{\Psi_{\!\delta}}}
\def\Pst{{\widetilde{\Psi}}}
\def\Pstd{{\widetilde{\Psi}_{\!\delta}}}

\nc{\glneq}{{\raisebox{0.6ex}{$>$}  \hspace*{-1.8ex} \raisebox{-0.6ex}{$<$}}}
\nc{\gleq}{{\raisebox{0.6ex}{$\geq$}\hspace*{-1.8ex} \raisebox{-0.6ex}{$\leq$}}}


%\nc{\id}{{\operatorname{id}}}

\nc{\vholder}[1]{\rule{0pt}{#1}}
\nc{\wh}[1]{\widehat{#1}}
\nc{\h}[1]{\widehat{#1}}

\nc{\ob}[1]{#1}

\def\beq{\begin {equation}}
\def\eeq{\end {equation}}

\begin{document}

\title{{\Large Quantum Conditional Mutual Information, Reconstructed States, and State Redistribution}}

\author{Fernando G.S.L. Brand\~ao$^{1}$, Aram W. Harrow$^{2}$, Jonathan Oppenheim$^{3}$, Sergii Strelchuk$^{4}$}
%\email{f.brandao@ucl.ac.uk}
\affiliation{$^{1}$ Department of Computer Science, University College London \\
$^{2}$ Institute for Theoretical Physics, Massachusetts Institute of Technology \\
$^{3}$ Department of Physics, University College London \\
$^{4}$ Department of Applied Mathematics and Theoretical Physics, University of Cambridge
}

\maketitle

\section*{SUPPLEMENTAL MATERIAL}
\subsection{Auxiliary lemmas}
\begin{lemma} \label{opmon}
If $\pi\leq 2^{\lambda} \sigma$, then $S(\rho || \pi) \geq S(\rho || \sigma) - \lambda$. 
\end{lemma}
The proof of the lemma follows directly from the operator monotonicity of the log function.\qed

Lemma 2 is due to Audenaert and Eisert:

\begin{lemma} [Theorem 3 of \cite{AE05}] \label{AudenaertE}
For all states $\rho$  and $\sigma$ on a $d$-dimensional Hilbert space, with $T = \Vert \rho - \sigma \Vert_1$ and $\beta = \lambda_{\min}(\sigma)$,
\be
S(\rho || \sigma) \leq T \log(d) + \min \left( - T \log T, \frac{1}{e}   \right) - \frac{T \log \beta}{2}.
\ee
\end{lemma}

The next lemma is due to M. Piani. It will suffice to state it for the
case where $\mathbb{M}$ is the set of all measurements. 

%Further, suppose that $K$ is closed under partial trace, so that in particular $\sigma_X \in K$

\begin{lemma} \label{Piani}
[Theorem 1 of \cite{Piani09}] Consider two systems $X$ and $Y$ with joint Hilbert space ${\cal H}_X \otimes {\cal H}_Y$, and a convex reference set $K$. Suppose the reference set $K$ is such that for all POVM elements $M_i$ and all $\sigma_{XY} \in K$, $\tr_{X}(M_i^X  \sigma_{XY}) \in P$ (up to normalization). Then for every $\rho_{XY}$,
\begin{eqnarray}
&& \min_{\sigma_{XY} \in K} S(\rho_{XY} || \sigma_{XY})
  \\ &\geq& \min_{\sigma_X \in K} \mathbb{M}S(\rho_X || \sigma_X) 
+ \min_{\sigma_Y \in K} S(\rho_Y || \sigma_Y). \nonumber
\end{eqnarray}
\end{lemma}

The following Lemma is due to Fawzi and Renner~\cite{FR14} who stated it
in a slightly more general form. It was used in their proof of
Eq. (4) in the main text.  Below is a very similar, but
somewhat shorter, proof.

\begin{lemma}\label{lem:postselect}
Suppose $\rho_{X^nY^n}$ satisfies $\rho_{X^n} = \tau_{X^n}$ and
$[\rho, P_{XY}(\pi)]=0$ for all $\pi\in \cS_n$.  Then there exists a
measure $\mu$ over states $\sigma_{XY}$ (independent of $\rho$) with
each $\sigma_X = \tau_Y$ 
and
\be
\rho_{X^nY^n} \leq n^{O(d_X^2d_Y^2)} \int \sigma^{\ot n} \mu(d\sigma),
\label{eq:constrained-post}\ee
where $d_X, d_Y$ are the dimensions of $X$ and $Y$.
\end{lemma}

\begin{proof}
First purify $\rho$ to a state $\ket{\rho}_{X^nY^nZ^n}\in\Sym^n(XYZ)$ (the symmetric subspace in $(XYZ)^{n}$)
with $d_Z = d_Xd_Y$ using Lemma 4.2.2 of \cite{Ren05}.  For $V$ an
isometry from $X \ra YZ$, define 
\be \ket{\sigma(V)}_{XYZ} = \frac{1}{\sqrt{d_X}} \sum_{i=1}^{d_X}
\ket{i} V\ket i\ee
and $\sigma(V) = \proj{\sigma(V)}$.  Observe that $\sigma(V)_X =
\tau_X$.  We will show that
\be
\proj{\rho} \leq n^{O(d_X^2d_Y^2)}
\int \sigma(V)^{\ot n} \mu(d\sigma),
\label{eq:purified-post}\ee
which will imply Eq. \eq{constrained-post}.

Our strategy will be to expand both sides of Eq. \eq{purified-post} in the
Schur basis.  Schur duality uses the following notation:
\be (\bbC^d)^{\ot n} \iso{\cU_{d} \times \cS_n}
\bigoplus_{\lambda\in\Par(n,d)} \cQ_\lambda^{d} \hat{\ot} \cP_\lambda.
\label{eq:schur-decomp}\ee
This is explained in detail in \cite{Har05}, but briefly,
$\Par(n,d)$ denotes the set of partitions of $n$ into $\leq d$
parts, $\cQ_{\lambda}^{d}$ is an irrep of the unitary group
$\cU_{d}$,
$\cP_\lambda$ is an irrep of the symmetric group $\cS_n$, $\hat\ot$
means that we interpret the tensor product as an irrep of $\cU_d
\times \cS_n$,  and
$\iso{\cU_{d} \times \cS_n}$ means that the isomorphism respects this
representation structure.
Let $U_{\Sch}$ denote the unitary transform realizing the
isomorphism in Eq. \eq{schur-decomp}.  We can write
\begin{multline} (U_{\Sch}^X \ot U_{\Sch}^{YZ})\ket\rho
= \\
 \sum_{\substack{\lambda_1\in\Par(n,d_X) \\
    \lambda_2\in\Par(n,d_Yd_Z)}}
 c_{\lambda_1,\lambda_2}
\ket{\lambda_1}_X  \ket{\lambda_2}_{YZ} 
\ket{\chi_{\lambda_1,\lambda_2}} \ket{\theta_{\lambda_1,\lambda_2}},
\label{eq:rho-decomp-first}\end{multline}
where $\sum_\lambda |c_\lambda|^2=1$,
$\ket{\chi_{\lambda_1,\lambda_2}},\ket{\theta_{\lambda_1,\lambda_2}}$
are arbitrary unit vectors in 
$\cQ_{\lambda_1}^{d_X}\ot\cQ_{\lambda_2}^{d_Yd_Z}$ and 
$\cP_{\lambda_1}\ot\cP_{\lambda_2}$ respectively.
However, the permutation invariance and Schur's Lemma mean that (following arguments
along the lines of Section 6.4.1 of \cite{Har05}) the only nonzero terms
have $\lambda_1=\lambda_2$ and $\ket{\theta_{\lambda,\lambda}} =: \ket{\Phi_\lambda}$ is the unique permutation-invariant state in
$\cP_\lambda \ot \cP_\lambda$.   Thus we can (using $d_X \leq d_Yd_Z$) rewrite 
Eq. \eq{rho-decomp-first} as 
\be (U_{\Sch}^X \ot U_{\Sch}^{YZ})\ket\rho
= \sum_{\lambda\in\Par(n,d_X)} c_{\lambda}
\ket{\lambda}_X  \ket{\lambda}_{YZ}  
\ket{\chi_{\lambda}} \ket{\Phi_{\lambda}}.
\label{eq:rho-decomp-second}\ee
To calculate $c_\lambda$ we use the
fact that $\rho_{X^n} = \tau_{X^n}$.  Thus measuring the irrep label
should yield outcome $\lambda$ with probability $\dim\cP_\lambda \dim
\cQ_{\lambda}^{d_X} / d_X^n$, and we have
\be c_\lambda = \sqrt{\frac{\dim\cP_\lambda
    \dim\cQ_{\lambda}^{d_X}}{d_X^n}}.\label{eq:c-lambda}\ee

A similar argument implies that
\begin{multline} (U_{\Sch}^X \ot U_{\Sch}^{YZ})\ket{\sigma(V)}^{\ot n}
= \\ \sum_{\lambda\in\Par(n,d_X)} c_{\lambda}
\ket{\lambda}_X \ket{\lambda}_{YZ} 
\ket{\chi_{\lambda}(V)} \ket{\Phi_{\lambda}},
\label{eq:sigma-decomp}\end{multline}
for some states $\ket{\chi_{\lambda}(V)}$.  The coefficients
$c_\lambda$ are the same as in Eq. \eq{c-lambda} because $\sigma(V)^{\ot
  n}_{A^n} = \tau_{A^n}$. 
Averaging $\sigma(V)^{\ot n}$ over all isometries $V$ yields a state
that commutes with $(U_X \ot I_{YZ})^{\ot n}$ and $(I_X \ot
U_{YZ})^{\ot n}$ for all $U_X \in \cU_{d_X}, U_{YZ} \in \cU_{d_Yd_Z}$.  Thus
\begin{multline}
(U_{\Sch}^X \ot U_{\Sch}^{YZ}) \E_V[\sigma(V)^{\ot n}] 
(U_{\Sch}^X \ot U_{\Sch}^{YZ})^\dag = \\
\sum_{\lambda\in\Par(n,d_X)} |c_{\lambda}|^2
\proj{\lambda,\lambda} 
\ot \tau_{\cQ_\lambda^{d_X}}\ot \tau_{\cQ_\lambda^{d_YdZ}}
\ot \proj{\Phi_{\lambda}}.
\label{eq:E-sigma-decomp}\end{multline}

It follows from \eqs{rho-decomp-second}{E-sigma-decomp} that
\ban
 \proj{\rho} &
\leq (\max_\lambda \dim \cQ_\lambda^{d_X}
\dim \cQ_\lambda^{d_Yd_Z}) \E_V[\sigma(V)^{\ot n}] 
\\ & = \binom{d_X + n-1}{n}\binom{d_Yd_Z + n-1}{n}
\E_V[\sigma(V)^{\ot n}] 
\\ &\leq n^{d_X}n^{d_Yd_Z}\E_V[\sigma(V)^{\ot n}] 
\\ & =n^{d_X^2d_Y^2+d_X}\E_V[\sigma(V)^{\ot n}].
\ean
\end{proof}

\subsection{The measured entropy lower bound}
To prove the inequality stated in the Eq. (17) of the main text, we first prove the following lemma which is a version of the postselection technique of~\cite{CKR09} for quantum operations. 

\begin{lemma}~\label{lem:ps-channel}
For every permutation-invariant quantum operation $\Lambda : B^n \rightarrow B^nC^n$ and every state $\pi
\in B^n$,
\begin{equation} \label{postselectionqop}
\Lambda(\pi) \leq \poly(n) \int  {\cal E}^{\otimes n}(\pi) \mu(d{\cal E}),
\end{equation}
where $\mu$ is a measure over quantum operations ${\cal E}: B \rightarrow BC$.
\end{lemma}

\begin{proof}
  Since $\Lambda : B^n \rightarrow B^nC^n$ is permutation-invariant,
  it follows that its Jamiolkowski state
  $J_{\Lambda} \in {\cal D}((\overline{B}^n \otimes B^n \otimes C^n)$
  (with $\overline{B} \cong B$) is permutation-invariant.  We now
  apply Lemma 4 in the Supplemental Material to find a distribution $\mu$ over
  $\sigma\in\cD(\overline{B} \ot B \ot C)$ with \be J_\Lambda \leq
  \poly(n) \int \sigma^{\ot n} \mu(d\sigma),\ee and each
  $\sigma_{\bar B} = \tau_{\bar B}$.  This latter condition means that
  each $\sigma$ can be also thought of as $J_{\cE}$ for some
  $\cE: B \ra BC$. We complete the proof using the relation:
\begin{eqnarray}
&&\tr_{\overline{B}^n} ( (\pi^T \otimes I_{B^nC^n}) J_{\Lambda}) \\ &\leq& \poly(n) \int \tr_{\overline{B}^n} ( (\pi^T \otimes I_{B^nC^n}) J_{{\cal E}}^{\otimes n}) \mu(d {\cal E}), \nonumber
\end{eqnarray}
and the fact that $\tr_{\overline{B}^n} ( (\pi^T \otimes I_{B^nC^n}) J_{\Lambda})  = \Lambda(\pi) / \text{dim}(B)^n$ and $\tr_{\overline{B}^n} ( (\pi^T \otimes I_{B^nC^n}) J_{{\cal E}}^{\otimes n}) = {\cal E}^{\otimes n}(\pi) / \text{dim}(B)^n$.
\end{proof}

We now turn to proving the measured entropy lower bound:

\begin{prop}[Eq. (17) in the main text]~\label{prop:measured}
For every state $\rho_{BCR}$ one has
\begin{eqnarray} 
&& \lim_{n \rightarrow \infty} \min_{\Lambda : B^n \rightarrow B^nC^n} \frac{1}{n} S(\rho_{BCR}^{\otimes n}|| \Lambda \otimes \id_{R^n}(\rho_{BR}^{\otimes n})) \nonumber \\ &\geq&  \min_{\Lambda : B \rightarrow BC}  \mathbb{M}S( \rho_{BCR} || \Lambda \otimes \id_R(\rho_{BR}) ).\label{prop2statmt}
\end{eqnarray}
\end{prop}

\begin{proof}

For $\Lambda : B^n \rightarrow B^n C^n$, define
\begin{equation}
\tilde{\Lambda}(\omega) := 
\frac{1}{n!} \sum_{\pi \in S_n} P_{BC}(\pi) \Lambda( P^{\cal y}_B(\pi)
\omega
 P_B(\pi)) P_{BC}(\pi)^{\cal y},
\end{equation}
with $P_{X}(\pi)$ a representation of a permutation $\pi$ from $S_n$
(symmetric group of order $n$) in $X^{\otimes n}$ such that $P_X(\pi)
\ket{a_1, \ldots, a_n} = \ket{a_{\pi^{-1}(1)}, \ldots,
  a_{\pi^{-1}(n)}}$. Let Sym be the set of all permutation-invariant
quantum operations, i.e. all $\Lambda$ such that $\Lambda = \tilde\Lambda$.

Using Proposition 3 in the main text and the fact that the relative entropy is doubly convex we obtain~\footnote{In more detail: $S(\rho_{BCR}^{\otimes n} || \Lambda (\rho_{BR}^{\otimes n} )) = \mathop{\mathbb{E}}_{\pi \in S_n}$  $S( P_{CBR}^{\pi} \rho_{BCR}^{\otimes n} (P_{CBR}^{\pi})^{\cal y} ||  P_{CBR}^{\pi} \Lambda ((P_{BR}^{\pi})^{\cal y} \rho_{BR}^{\otimes n} P_{BR}^{\pi}) (P_{CBR}^{\pi})^{\cal y})$ $= \mathop{\mathbb{E}}_{\pi \in S_n} S(\rho_{BCR}^{\otimes n} || P_{CB}^{\pi} \Lambda ((P_{B}^{\pi})^{\cal y} \rho_{BR}^{\otimes n} P_{B}^{\pi}) (P_{CB}^{\pi})^{\cal y}) \geq$ $ S\left ( \rho_{BCR}^{\otimes n}  || \mathop{\mathbb{E}}_{\pi \in S_n}  P_{CB}^{\pi} \Lambda ( (P_{B}^{\pi})^{\cal y} \rho_{BR}^{\otimes n} P_{B}^{\pi}) (P_{CB}^{\pi})^{\cal y} \right)$, with $P_{CBR}^{\pi} := P_{CBR}(\pi)$.}
\begin{eqnarray}
&& \lim_{n \rightarrow \infty} \min_{\Lambda : B^n \rightarrow B^nC^n} \frac{1}{n} S(\rho_{BCR}^{\otimes n}|| \Lambda \otimes \id_{R^n}(\rho_{BR}^{\otimes n})) \nonumber  \\ &\geq& \lim_{n \rightarrow \infty} \min_{  \substack{\Lambda : B^n \rightarrow B^nR^n \\   \Lambda \in \text{Sym}}   } \frac{1}{n}S(\rho_{BCR}^{\otimes n}|| \Lambda \otimes \id_{R^n}(\rho_{BR}^{\otimes n})).  \nonumber
\end{eqnarray}

Lemma~\ref{lem:ps-channel} gives that for every $\Lambda_n : B^n \rightarrow B^nC^n \in$ Sym,
\begin{eqnarray}
&& (\Lambda_n \otimes \id_{R^n})(\rho_{BR}^{\otimes n}) \\ &\leq& \poly(n) \int ({\cal E} \otimes \id_R (\rho_{BR}))^{\otimes n} \mu_n(d{\cal E}), \nonumber
\end{eqnarray}
with $\mu(d{\cal E})$ a measure over quantum operations ${\cal E} : B \rightarrow BC$. Using the previous equation and the operator monotonicity of the $\log$ (see Lemma 1 above),
\begin{eqnarray}   \label{eq21}
&& \lim_{n \rightarrow \infty} \min_{\Lambda : B^n \rightarrow B^nC^n} \frac{1}{n} S(\rho_{BCR}^{\otimes n}|| \Lambda \otimes \id_{R^n}(\rho_{BR}^{\otimes n}))  \\ &\geq& \lim_{n \rightarrow \infty} \min_{\mu_n} \frac{1}{n}S\left(\rho_{BCR}^{\otimes n} \hspace{0.1 cm} \Vert \int ({\cal E} \otimes \id_R (\rho_{BR}))^{\otimes n} \mu_n(d{\cal E})\right). \nonumber
\end{eqnarray}

To complete the proof we make use of Lemma 3 above. Consider the state $\rho_{BCR}^{\otimes n}$ and let $X$ be the first copy of $\rho_{BCR}$ in the tensor product and $Y$ the remaining $\rho_{BCR}^{\otimes n-1}$. Define
\be
K = \bigcup_{k \in \mathbb{N}} \left(\text{conv} \{ ( {\cal E} \otimes \id_R)( \rho_{BR} )^{\otimes k} \hspace{0.1 cm} : \hspace{0.1 cm} {\cal E} : B \rightarrow BC \} \right),
\ee
i.e. the convex hull of tensor products of reconstructed states. It is easy to check that $K$ satisfies the assumption of Lemma 3 above. Therefore:
\begin{eqnarray}
&& \min_{\mu_n}  S\left(\rho_{BCR}^{\otimes n} \hspace{0.1 cm} \Vert \int ({\cal E} \otimes \id_R (\rho_{BR}))^{\otimes n} \mu_n(d{\cal E})\right)  \\
&\geq& \min_{\mu}   \mathbb{M} S\left(\rho_{BCR} \hspace{0.1 cm} \Vert \int ({\cal E} \otimes \id_R (\rho_{BR})) \mu(d{\cal E})\right) \nonumber \\  &+&   \min_{\mu_{n-1}}  S\left(\rho_{BCR}^{\otimes n-1} \hspace{0.1 cm} \Vert \int ({\cal E} \otimes \id_R (\rho_{BR}))^{\otimes n-1} \mu_{n-1}(d{\cal E})\right).  \nonumber
\end{eqnarray}
Iterating the equation above $n$ times gives Eq.~\eqref{prop2statmt}.
\end{proof}


\begin{thebibliography}{10}

\bibitem{AE05}
K.~M.~R. Audenaert and J.~Eisert.
\newblock Continuity bounds on the quantum relative entropy.
\newblock {\em J. Math. Phys.}, 46(10):--, 2005,
  \href{http://arxiv.org/abs/quant-ph/0503218}{{\ttfamily
  arXiv:quant-ph/0503218}}.

\bibitem{Piani09}
M.~Piani.
\newblock Relative entropy of entanglement and restricted measurements.
\newblock {\em Phys. Rev. Lett.}, 103:160504, Oct 2009,
  \href{http://arxiv.org/abs/0904.2705}{{\ttfamily arXiv:0904.2705}}.

\bibitem{FR14}
O.~Fawzi and R.~Renner.
\newblock Quantum conditional mutual information and approximate markov chains,
  2014,  \href{http://arxiv.org/abs/1410.0664}{{\ttfamily arXiv:1410.0664}}.

\bibitem{Ren05}
R.~Renner.
\newblock {\em Security of quantum key distribution}.
\newblock PhD thesis, ETHZ, Zurich, 2005,
  \href{http://arxiv.org/abs/quant-ph/0512258}{{\ttfamily
  arXiv:quant-ph/0512258}}.

\bibitem{Har05}
A.~W. Harrow.
\newblock {\em Applications of coherent classical communication and {S}chur
  duality to quantum information theory}.
\newblock PhD thesis, M.I.T., Cambridge, MA, 2005,
  \href{http://arxiv.org/abs/quant-ph/0512255}{{\ttfamily
  arXiv:quant-ph/0512255}}.

\bibitem{CKR09}
M.~Christandl, R.~Koenig, and R.~Renner.
\newblock Post-selection technique for quantum channels with applications to
  quantum cryptography.
\newblock {\em Phys. Rev. Lett.}, 102:020504, 2009,
  \href{http://arxiv.org/abs/0809.3019}{{\ttfamily arXiv:0809.3019}}.



\end{thebibliography}

\end{document}
