the qudits in ${(\cup_{j=1}^{\ell}I_{j})^{c}}$. The state tuple
$({|{q_{1}}\rangle}{\langle{q_{1}}|}^{\otimes I_{j}})_{j=1}^{\ell}$ is a
solution of the maximization problem

$\displaystyle\max_{({|{\psi_{j}}\rangle}{\langle{\tilde{\psi}_{j}}|}_{I_{j}})_{j=1}^{\ell}}|||\;(\prod_{j=1}^{\ell}{|{\psi_{j}}\rangle}{\langle{\tilde{\psi}_{j}}|}_{I_{j}}\otimes\mathds{1}^{\otimes
I_{j}^{c}})\mathds{1}_{\cup_{j=1}^{\ell}I_{j}}\otimes\tilde{R}_{(\cup_{j=1}^{\ell}I_{j})^{c}}\;|||,$
(4.7.3)

where the variable tuple
$({|{\psi_{j}}\rangle}{\langle{\tilde{\psi}_{j}}|}_{I_{j}})_{j=1}^{\ell}$ is
of normalized operators.

###### Proof.

We proceed via induction on the number of sets $\ell$. If $\ell=1$, then all
choices of ${|{\psi_{1}}\rangle}{\langle{\tilde{\psi_{1}}}|}_{I_{1}}$ yield
the same objective value, proving the base case. For $\ell>1$, define
$A_{j}:={|{\psi_{j}}\rangle}{\langle{\tilde{\psi}_{j}}|}_{I_{j}}\otimes\mathds{1}^{\otimes
I_{j}^{c}}$ for $j\in[\ell]$, and $J:=I_{1}\cap I_{2}$. If $J=\emptyset$, then
$A_{1}A_{2}={|{\psi_{1}}\rangle}{\langle{\tilde{\psi}_{1}}|}_{I_{1}}\otimes{|{\psi_{2}}\rangle}{\langle{\tilde{\psi}_{2}}|}_{I_{2}}\otimes\mathds{1}^{\otimes(I_{1}\cup
I_{2})^{c}}$ and the number of sets is reduced to $\ell-1$. Otherwise, we
consider the Schmidt decompositions:

$\displaystyle{|{\tilde{\psi}_{1}}\rangle}_{I_{1}}$
$\displaystyle=\sum_{i}\sqrt{\lambda_{i}}{|{\gamma_{i}}\rangle}_{J}{|{\alpha_{i}}\rangle}_{I_{1}\setminus
J}\;,\;{|{\psi_{2}}\rangle}_{I_{2}}=\sum_{j}\sqrt{\mu_{j}}{|{\delta_{j}}\rangle}_{J}{|{\beta_{j}}\rangle}_{I_{2}\setminus
J}.$ (4.7.4)

We expand

$\displaystyle
A_{1}A_{2}=\sum_{i,j}\sqrt{\lambda_{i}}\sqrt{\mu_{j}}\innerproduct{\gamma_{i}}{\delta_{j}}\underbrace{{|{\psi_{1}}\rangle}_{I_{1}}{|{\beta_{j}}\rangle}_{I_{2}\setminus
J}{\langle{\alpha_{i}}|}_{I_{1}\setminus
J}{\langle{\tilde{\psi_{2}}}|}_{I_{2}}}_{{B_{i,j}}}\otimes\mathds{1}^{\otimes(I_{1}\cup
I_{2})^{c}}.$ (4.7.5)

Observe that $B_{i^{\prime},j^{\prime}}^{*}B_{i,j}=0$ if $j\neq j^{\prime}$.
Define $C^{2}=(A_{1}A_{2})^{*}A_{1}A_{2}$ and notice that in the expression

$\displaystyle
C^{2}=(\sum_{i,i^{\prime}}\sqrt{\lambda_{i}}\sqrt{\lambda_{i^{\prime}}}\;\underbrace{{\langle{\gamma_{i}}|}(\sum_{j}\mu_{j}{|{\delta_{j}}\rangle}{\langle{\delta_{j}}|}){|{\gamma_{i^{\prime}}}\rangle}}_{\rho_{i^{\prime},i}}\;{|{\alpha_{i^{\prime}}}\rangle}{\langle{\alpha_{i}}|}_{I_{1}\setminus
J})\otimes{|{\tilde{\psi_{2}}}\rangle}{\langle{\tilde{\psi_{2}}}|}_{I_{2}}\otimes\mathds{1}^{\otimes(I_{1}\cup
I_{2})^{c}}$ (4.7.6)

the factor acting on the qudits in $I_{1}\setminus J$ is a Hadamard product of
two states

$\displaystyle\rho=\sum_{i^{\prime},i}\rho_{i^{\prime},i}{|{\alpha_{i^{\prime}}}\rangle}{\langle{\alpha_{i}}|}\text{
and
}\sigma=\sum_{i^{\prime},i}\sqrt{\lambda_{i^{\prime}}\lambda_{i}}{|{\alpha_{i^{\prime}}}\rangle}{\langle{\alpha_{i}}|}.$
(4.7.7)

By the Schur product theorem, $\rho\odot\sigma\geq 0$. Moreover, by Schur-
concavity of the square root and the fact that
$\lambda(\cdot)\succeq\text{diag}(\cdot)$,

$\displaystyle\tr(\sqrt{\rho\odot\sigma})\leq\tr(\sqrt{\text{diag}(\rho\odot\sigma)}))\leq\sum_{i}\sqrt{\lambda_{i}}\sqrt{\rho_{i,i}}\leq
1.$ (4.7.8)

Hence, the positive square root

$\displaystyle C=\tilde{C}_{I_{1}\setminus
J}\otimes{|{\tilde{\psi_{2}}}\rangle}{\langle{\tilde{\psi_{2}}}|}_{I_{2}}\otimes\mathds{1}^{\otimes(I_{1}\cup
I_{2})^{c}}$ (4.7.9)

satisfies $\tilde{C}\geq 0$ and $\tr(\tilde{C})\leq 1$. Since unitarily
invariant norms satisfy $|||\;\cdot\;|||=|||\;|\cdot|\;|||$, $A_{1}A_{2}$ can
be replaced by $C$. Since $C$ is a sub-convex combination of terms of the form
${|{c}\rangle}{\langle{c}|}_{I_{1}\setminus
J}\otimes{|{\tilde{\psi_{2}}}\rangle}{\langle{\tilde{\psi_{2}}}|}_{I_{2}}\otimes\mathds{1}^{\otimes(I_{1}\cup
I_{2})^{c}}$ the statement follows by the triangle inequality and the
inductive hypothesis. ∎

Finally, we are ready to put it all together and prove Lem. 4.7.1.

###### Proof.

Without loss of generality
$(T_{I_{j}})_{j=1}^{\ell}=({|{\psi_{j}}\rangle}{\langle{\tilde{\psi}_{j}}|}_{I_{j}})_{j=1}^{\ell}$.
Let $U=\cup_{j=1}^{\ell}I_{j}$ and let $\tilde{Q}_{U^{c}}$ denote the products
of factors of $Q$ supported on $U^{c}$. By using the staircase decomposition
of $Q$ and expanding sums over products in $U$, the operator product in Eq.
4.7.1 can be written as a positive sum of terms that have the form

$\displaystyle(\prod_{j=1}^{\ell}{|{\psi_{j}}\rangle}{\langle{\tilde{\psi}_{j}}|}_{I_{j}}\otimes
P_{U\setminus I_{j}})\otimes\tilde{Q}_{U^{c}}.$ (4.7.10)

where $P_{U\setminus I_{1}},P_{U\setminus I_{2}},\ldots,P_{U\setminus
I_{\ell}}$ are tensor products of the various perfectly aligned single-qudit
projectors decomposing $Q$. Since

$\displaystyle(\prod_{j=1}^{\ell}{|{q_{1}}\rangle}{\langle{q_{1}}|}^{\otimes
I_{j}}\otimes P_{U\setminus
I_{j}})\otimes\tilde{Q}_{U^{c}}=(\prod_{j=1}^{\ell}{|{q_{1}}\rangle}{\langle{q_{1}}|}^{\otimes
I_{j}}\otimes\mathds{1}_{U\setminus I_{j}})\otimes\tilde{Q}_{U^{c}},$ (4.7.11)

by Cor. 4.7.3 and Lem. 4.7.4,
$|||(\prod_{j=1}^{\ell}{|{\psi_{j}}\rangle}{\langle{\tilde{\psi}_{j}}|}_{I_{j}}\otimes
P_{U\setminus I_{j}})\otimes\tilde{Q}_{U^{c}}|||$ is maximized at
$({|{q_{1}}\rangle}{\langle{q_{1}}|}^{\otimes I_{j}})_{j=1}^{\ell}$. Finally,
notice that $(\prod_{j=1}^{\ell}{|{q_{1}}\rangle}{\langle{q_{1}}|}^{\otimes
I_{j}}\otimes P_{U\setminus
I_{j}})\otimes\tilde{Q}_{U^{c}}={|{q_{1}}\rangle}{\langle{q_{1}}|}^{\otimes
U}\otimes\tilde{Q}_{U^{c}}$. That is, not only are all the summands maximized
at $({|{q_{1}}\rangle}{\langle{q_{1}}|}^{\otimes I_{j}})_{j=1}^{\ell}$, they
are also proportional to each other with positive proportionality constants
there. Therefore, the statement follows by the triangle inequality for the
norm $|||\cdot|||$. ∎

###  4.8 On the relationship between the sum of two projectors and their
product

In this appendix, we prove lemmas necessary to elucidate the relationship
between a non-negative linear combination $s_{1}P_{1}+s_{2}P_{2}$ of two
projectors $P_{1},P_{2}\in\mathcal{S}(\mathcal{K})$ and their product
$P_{1}P_{2}$. By [47], $\mathcal{K}$ may be decomposed into a direct sum of
subspaces, each of dimension at most $2$, that are invariant under the action
of both $P_{1}$ and $P_{2}$. Moreover, when restricted to each invariant
subspace, the two projectors have rank at most 1. So, we may write
$\mathcal{K}$ as an orthogonal direct sum of one- and two-dimensional minimal
invariant subspaces

$\displaystyle\mathcal{K}=\bigoplus_{i_{1}=1}^{m_{1}}\mathcal{K}_{i_{1}}^{(1)}\oplus\bigoplus_{i_{2}=1}^{m_{2}}\mathcal{K}_{i_{2}}^{(2)},$
(4.8.1)

where the $K_{i}^{(1)}$ are one-dimensional and the $K_{i}^{(2)}$ are two
dimensional. By minimality, the latter contain no proper nonzero invariant
subspace. For each $i_{2}\in[m_{2}]$, we notate

$\displaystyle
P_{1}|_{\mathcal{K}_{i_{2}}^{(2)}}=:{|{\alpha_{i_{2}}}\rangle}{\langle{\alpha_{i_{2}}}|}\;,\;P_{2}|_{\mathcal{K}_{i_{2}}^{(2)}}=:{|{\beta_{i_{2}}}\rangle}{\langle{\beta_{i_{2}}}|}.$
(4.8.2)

$P_{1}$ and $P_{2}$ commute if and only if $m_{2}=0$. The difficulty in
reasoning about the eigenvalues of a linear combination of two projectors lies
in these subspaces where they do not commute.

When restricted to $\bigoplus_{i_{2}=1}^{m_{2}}\mathcal{K}_{i_{2}}^{(2)}$, the
nonzero singular of $P_{1}P_{2}$ are
$(|\innerproduct{\alpha_{i_{2}}}{\beta_{i_{2}}}|)_{i_{2}=1}^{m_{2}}$. The
eigenvalues of the restriction
$(s_{1}P_{1}+s_{2}P_{2})|_{\mathcal{K}_{i_{2}}^{(2)}}$ may be computed as

$\displaystyle\frac{1}{2}((s_{1}+s_{2})\pm\sqrt{(s_{1}-s_{2})^{2}+4s_{1}s_{2}|\innerproduct{\alpha_{i_{2}}}{\beta_{i_{2}}}|^{2}}).$
(4.8.3)

Hence, the eigenvalues of $s_{1}P_{1}+s_{2}P_{2}$ are a function of the
singular values of the product $P_{1}P_{2}$. We show next that it is in fact a
strictly isotone function (see page 41 of Ref. [15]). A strictly isotone
function $G$ is one that preserves the majorization ordering in the sense that
if $v\succeq w$, then $G(v)\succeq G(w)$. That is, the less dispersed the
singular values of $P_{1}P_{2}$, the less dispersed the eigenvalues of
$s_{1}P_{1}+s_{2}P_{2}$. This is a consequence of the fact that for $a,b\geq
0$, the map $x\mapsto\sqrt{a+bx^{2}}$ is convex on $\mathbb{R}_{\geq 0}$.

######  Lemma 4.8.1.

Let $A\subseteq\mathbb{R}$ be convex and $g:A\rightarrow\mathbb{R}_{\geq 0}$
be a convex function. For $t\in\mathbb{R}$, define the mapping
$G:A^{m}\rightarrow\mathbb{R}^{2m}$ with action

$\displaystyle(v_{1},\ldots,v_{m})\mapsto(t+g(v_{1}),\ldots,t+g(v_{m}))\oplus(t-g(v_{1}),\ldots,t-g(v_{m})).$
(4.8.4)

Then, $G$ is strictly isotone.

###### Proof.

Let $v,w\in A^{m}$ be such that $v\succeq w$. Observe that for $k\in[m]$,

$\displaystyle\sum_{j=1}^{k}G(v)^{\downarrow}_{j}=kt+\sum_{j=1}^{k}g(v)_{j}^{\downarrow}\geq
kt+\sum_{j=1}^{k}g(w)_{j}^{\downarrow}=\sum_{j=1}^{k}G(w)^{\downarrow}_{j},$
(4.8.5)

where the inequality follows from the convexity of $g$ and the doubly-
stochastic characterization of majorization (see, for example, Theorem II.3.3
on page 41 of [15]). If $k>m$, then

$\displaystyle\sum_{j=1}^{k}G(v)^{\downarrow}_{j}$
$\displaystyle=kt+\sum_{j=1}^{m}g(v)_{j}^{\downarrow}-\sum_{j=1}^{k-m}g(v)_{j}^{\uparrow}=kt+\sum_{j=1}^{2m-k}g(v)_{j}^{\downarrow}$
(4.8.6) $\displaystyle\geq
kt+\sum_{j=1}^{2m-k}g(w)_{j}^{\downarrow}=\sum_{j=1}^{k}G(w)^{\downarrow}_{j}.$
(4.8.7)

Since $\sum_{j=1}^{2m}G(\cdot)_{j}=2mt$, $G(v)\succeq G(w)$. ∎

The following lemma exhibits the maximal elements in the majorization order in
a superset of the possible tuples of nonzero singular values of
$P_{1}P_{2}|_{\bigoplus_{i_{2}=1}^{m_{2}}\mathcal{K}_{i_{2}}^{(2)}}$.

######  Lemma 4.8.2.

Given $m\in\mathbb{N},e\geq 0$, elements of the set

$\displaystyle S_{e}:=\\{x\in\mathbb{R}^{m}\;|\;\forall
i\in[m],x_{i}\in[0,1],\sum_{i=1}^{m}x_{i}=e\\}$ (4.8.8)

The element $(\underbrace{1,\ldots,1}_{\lfloor
e\rfloor\;\text{times}},e-\lfloor e\rfloor,0,\ldots,0)\in S_{e}$ majorizes
every element of $S_{e}$.

###### Proof.

Let $x\in S_{e}$ be arbitrary. For $k\in[m]$, $k\leq\lfloor e\rfloor$, observe
that $\sum_{i=1}^{k}x^{\downarrow}_{i}\leq\sum_{i=1}^{k}1=k$. And for
$k>\lfloor e\rfloor$,
$\sum_{i=1}^{k}x^{\downarrow}_{i}\leq\sum_{i=1}^{m}x^{\downarrow}_{i}\leq e$.
∎

##  Chapter 5 Quantum erasure simulation and probabilistic error correction

###  5.1 Introduction

Quantum erasure is a good error model for architectures suffering from
leakage. For example, in a trapped-ion architecture, each information-carrying
qubit is ideally encoded in a subspace, called the computational subspace,
that is spanned by a particular set of electronic states of each ion [18].
These states are chosen for their long coherence times. However, due to
interactions with its environment, the state of an ion may leak out of the
computational subspace. This process may be modeled as an erasure because it
is possible, at least in principle, to make a measurement to find out if and
where an error occurred. See [38] for other practical reasons to consider
quantum erasure.

######  Definition 5.1.1.

(Quantum erasure channel) Let $\mathcal{H}$ be an inner product space and
denote $\tilde{\mathcal{H}}:=\mathcal{H}\oplus\mathbb{C}$. Let
$\iota:\mathcal{B}(\mathcal{H})\rightarrow\mathcal{B}(\tilde{\mathcal{H}})$ be
an isometric channel and let ${|{e}\rangle}$ be a unit vector spanning the
kernel of $\iota(\mathds{1}_{\mathcal{H}})$. For $q\in[0,1]$, a quantum
erasure channel
$\mathcal{E}_{q}:\mathcal{B}(\mathcal{H})\rightarrow\mathcal{B}(\tilde{\mathcal{H}})$
acts in the following way:

$\displaystyle\mathcal{E}_{q}(\cdot)=(1-q)\iota(\cdot)+q\tr(\cdot){|{e}\rangle}{\langle{e}|}.$
(5.1.1)

The state ${|{e}\rangle}$ is called the error flag and $q$ is called the
erasure probability.

The structure of this chapter is as follows. In Section 5.2, we motivate
erasure as an error model and review the relevant literature. In Section 5.3,
we recall some notation and mathematical background. In Section 5.4, we define
quantum simulation and show how it is related to probabilistic error
correction. We also introduce Hastings’ problem. In Section 5.5, we give a
complete characterization of quantum channels that can contribute to a convex
decomposition of erasure. In Section 5.6, we report our latest progress on
Hastings’ problem. Finally, we conclude in Section 5.7 with some ideas for
further research.

###  5.2 Motivation and history

The quantum and classical capacities of quantum erasure channels were derived
as explicit functions of the erasure probability by Bennett et al. in Ref.
[14]. In particular, they proved that

$\displaystyle\mathcal{Q}(\mathcal{E}_{q})=\max(0,(1-2q)\log
d_{\mathcal{H}}).$ (5.2.1)

As is standard in quantum information, the logarithm base is $2$ and the
capacity is measured in qubits. Crucial to their proof is the fact that the
quantum capacity of a symmetric channel, which is one that is isometrically
equivalent to its complementary channel, is zero. They used this to show that
the quantum capacity of a quantum erasure channel vanishes when its erasure
probability exceeds $\frac{1}{2}$. We include a proof of the latter statement
for completeness.

######  Proposition 5.2.1.

If $q\geq\frac{1}{2}$, then the quantum capacity of $\mathcal{E}_{q}$ is zero.

###### Proof.

First, we reduce to the case where the erasure probability is exactly equal to
$\frac{1}{2}$. For $q>\frac{1}{2}$, there exists a channel
$\tilde{\mathcal{E}}_{\frac{1}{2}\rightarrow
q}:\mathcal{B}(\tilde{\mathcal{H}})\rightarrow\mathcal{B}(\tilde{\mathcal{H}})$
such that $\tilde{\mathcal{E}}_{\frac{1}{2}\rightarrow
q}\circ\mathcal{E}_{\frac{1}{2}}=\mathcal{E}_{q}$. It is

$\displaystyle\tilde{\mathcal{E}}_{\frac{1}{2}\rightarrow
q}(\cdot)=(1-\tilde{q})\mathrm{id}_{\tilde{\mathcal{H}}}(\cdot)+\tilde{q}\tr(\cdot){|{e}\rangle}{\langle{e}|},$
(5.2.2)

where $\tilde{q}=2(q-\frac{1}{2})$. This shows that if the quantum capacity of
$\mathcal{E}_{q}$ for some $q>\frac{1}{2}$ is nonzero, then the quantum
capacity of $\mathcal{E}_{\frac{1}{2}}$ is nonzero.

We argue by contradiction. The following isometry gives an isometric extension
of $\mathcal{E}_{\frac{1}{2}}$. For all ${|{\phi}\rangle}\in\mathcal{H}$,

$\displaystyle
U_{\frac{1}{2}}({|{\phi}\rangle})=\frac{1}{\sqrt{2}}({|{\phi}\rangle}_{1}\otimes{|{e}\rangle}_{2}+{|{e}\rangle}_{1}\otimes{|{\phi}\rangle}_{2}).$
(5.2.3)

This says in particular that $\mathcal{E}_{\frac{1}{2}}$ is isometrically
equivalent to its complementary. That is, it is a symmetric channel. If its
quantum capacity is nonzero, then there exists, in particular, a sequence
$(\mathcal{V}_{n},\mathcal{D}_{n})_{n\in\mathbb{N}}$ of encoding and decoding
channels such that
$\text{dom}(\mathcal{V}_{n})=\text{codom}(\mathcal{D}_{n})=\mathcal{H}$ and

$\displaystyle(\mathcal{D}_{n})_{1}\otimes(\mathcal{D}_{n})_{2}\circ\mathcal{U}_{\frac{1}{2}}^{\otimes
n}\circ\mathcal{V}_{n}(\rho)=\rho\otimes\rho+\xi_{n},$ (5.2.4)

for all $\rho\in\mathcal{B}(\mathcal{H})$, and $||\xi_{n}||_{1}\rightarrow 0$
as $n\rightarrow\infty$. This implies that
$\lim_{n\rightarrow\infty}(\mathcal{D}_{n})_{1}\otimes(\mathcal{D}_{n})_{2}\circ\mathcal{U}_{\frac{1}{2}}^{\otimes
n}\circ\mathcal{V}_{n}$ is a linear cloning machine. This cannot be. ∎

In [38], Grassl et al. show that the smallest single erasure correcting qubit
code has length $4$ and give the example of the $[[4,1,2]]_{2}$ stabilizer
code. The authors of [86] used a Rényi divergence approach to show that
sequences of Haar random codes for entanglement generation at a rate above the
capacity of the quantum erasure channel have exponentially decaying
entanglement fidelity.

In [43], Hastings initiates the study of the problem of simulating quantum
erasure channels (see Def. 5.3.2) using other quantum erasure channels. In
particular, he showed that for $m\in\mathbb{N}$, the channel
$\mathcal{E}_{1-\frac{1}{m}}$ cannot be used to simulate a channel
$\mathcal{E}_{q}$ for $q<1-\frac{1}{m}$. He conjectured that quantum erasure
channels with zero quantum capacity cannot be used to simulate better quantum
erasure channels. More details and progress on this are provided below.

In [50], Kukulski et al. systematically study probabilistic quantum error
correction. It is not the first study of probabilistic recovery of quantum
information (see [57] for example). However, this does seem to be the first
place where the optimal probability of recovery is formulated as the value of
a semi-definite program parameterized by Kraus operators of the channel in
question. We reached similar conclusions independently. Notably, Kukulski et
al. give a class of channels for which isometric encodings are sub-optimal for
maximizing the probability of recovery.

###  5.3 Preliminaries

We recall some notation and mathematical notions. Let $\mathcal{H}_{A}$ be a
given inner product space and let $\mathcal{H}_{R}\cong\mathcal{H}_{A}$. Let
${|{\beta}\rangle}_{RA}=\sum_{i=1}^{d_{\mathcal{H}}}{|{i}\rangle}_{A}\otimes{|{i}\rangle}_{R}$
be an unnormalized maximally entangled state. The value of a super-operator
$\mathcal{T}:\mathcal{B}(\mathcal{H}_{A})\rightarrow\mathcal{B}(\mathcal{H}_{B})$
under the Choi isomorphism $\sigma_{\beta}$ is given by
$\sigma_{\beta}(\mathcal{T})_{RB}=(\mathrm{id}_{R}\otimes\mathcal{T}_{A})({|{\beta}\rangle}{\langle{\beta}|}_{RA})$.
From now on, we use $\sigma$ to denote $\sigma_{\beta}$ for some fixed
${|{\beta}\rangle}$. For a code $\mathcal{C}$, $\mathcal{U}_{\mathcal{C}}$
denotes an isometry whose image is $\mathcal{C}$, and $P_{\mathcal{C}}$
denotes the projector onto $\mathcal{C}$. For natural $n$, $[n]$ denotes the
set $\\{1,2,...,n\\}$ and $\binom{[n]}{\ell}$ denotes the family of
$\ell$-sets in $[n]$. We argue based on the notion of typicality (see, for
example, Ch.14 of [84]) to prove Thm. 5.6.8 below. Specifically, we consider
strongly typical binary strings relative to a Bernoulli distribution. These
strings represent subsets of qudits that are not erased.

######  Definition 5.3.1.

(Typical weights) Given $u\in(0,1),\delta>0$, and $n\in\mathbb{N}$, the set of
$\delta$-typical weights relative to $u$ is

$\displaystyle
T^{(n)}_{u,\delta}=\\{\ell\in[n]\cup\\{0\\}\;\big{|}\;|\frac{\ell}{n}-u|\leq\delta\\}.$
(5.3.1)

A subset $S\subseteq[n]$ is called $\delta$-typical relative to $u$ if $|S|\in
T^{(n)}_{u,\delta}$. If $u\in\\{0,1\\}$, then by definition only one weight is
$\delta$-typical relative to $u$ and it is $0$ if $u=0$ and $n$ if $u=1$.

Let $u\in[0,1]$. For each $n\in\mathbb{N}$, let $X^{n}=X_{1},\ldots,X_{n}$ be
independent realizations of a binary random variable $X$ with
$\text{Pr}(X=1)=u$. It is a consequence of the law of large numbers that for
all $\delta>0$, $\text{Pr}(X^{n}:|X^{n}|\in T^{(n)}_{u,\delta})\rightarrow 1$
as $n\rightarrow\infty$.

######  Definition 5.3.2.

(Exact channel simulation) Given a pair of channels $\mathcal{M}_{1}$ and
$\mathcal{M}_{2}$, if there exists two channels $\mathcal{T}$ and
$\mathcal{R}$ such that

$\displaystyle\mathcal{M}_{1}=\mathcal{R}\circ\mathcal{M}_{2}\circ\mathcal{T},$
(5.3.2)

then $\mathcal{M}_{1}$ is exactly simulable with $\mathcal{M}_{2}$. The
channel $\mathcal{M}_{1}$ is the target of the simulation and the channel
$\mathcal{M}_{2}$ is the resource. When clear from context, we may say that
$\mathcal{M}_{1}$ can be simulated with $\mathcal{M}_{2}$ if $\mathcal{M}_{1}$
is exactly simulable with $\mathcal{M}_{2}^{\otimes n}$ for some
$n\in\mathbb{N}$.

In quantum error correction, the goal is to simulate the identity channel by
the error channel. Following the terminology of quantum error correction, we
use the term encoder to refer to someone with access and control of the input
to the resource channel and the term decoder to refer to someone with access
to the output of the resource channel. If a channel $\mathcal{M}_{1}$ is
exactly simulable with $\mathcal{M}_{2}^{\otimes n}$, then it is exactly
simulable with $\mathcal{M}_{2}^{\otimes m}$ for $m\geq n$. The encoding
channels $\mathcal{T}$ may be assumed to be isometric at the cost of
increasing the number of resource channel uses.

######  Proposition 5.3.3.

If $\mathcal{M}_{1}$ is exactly simulable by $\mathcal{M}_{2}^{\otimes n}$ for
some $n\in\mathbb{N}$, then

$\displaystyle\mathcal{M}_{1}=\tilde{\mathcal{R}}\circ\mathcal{M}_{2}^{\otimes
n+t}\circ\mathcal{U},$ (5.3.3)

where $\tilde{\mathcal{R}}$ is a channel, $\mathcal{U}$ is an isometric
channel, and $t\leq n+1$.

###### Proof.

By assumption, there exist channels $\mathcal{T}$ and $\mathcal{R}$ such that
$\mathcal{M}_{1}=\mathcal{R}\circ\mathcal{M}_{2}^{\otimes n}\circ\mathcal{T}$.
For $\mathcal{T}$, there exists a Kraus decomposition $\\{T_{i}\\}_{i=1}^{t}$
with $t\leq d_{\mathcal{H}}d_{\mathcal{H}}^{n}$ [21]. Let
$U_{\mathcal{T}}:\mathcal{H}\rightarrow\mathcal{H}^{\otimes(n+\lceil\log_{d_{\mathcal{H}}}(t)\rceil)}$
be defined by the action

$\displaystyle\mathcal{H}\ni{|{\phi}\rangle}\mapsto
U_{\mathcal{T}}{|{\phi}\rangle}:=\sum_{i=1}^{t}T_{i}{|{\phi}\rangle}\otimes{|{i}\rangle}_{\text{aux}},$
(5.3.4)

where $\\{{|{i}\rangle}_{\text{aux}}\\}_{i=1}^{t}$ are orthonormal. Then,
$\mathcal{U}\sim\\{U_{T}\\}$ is an isometric extension of $\mathcal{T}$ [78].
After $\mathcal{M}^{\otimes n+t}$, the systems in
$[n+\lceil\log_{d_{\mathcal{H}}}(t)\rceil]\setminus[n]$ are discarded and then
$\mathcal{R}$ is applied to the systems in $[n]$. That is,
$\tilde{\mathcal{R}}:=\mathcal{R}\circ\tr_{[n+\lceil\log_{d_{\mathcal{H}}}(t)\rceil]\setminus[n]}$.
∎

Other kinds of quantum channel simulation may be considered. For example, we
may consider approximate simulation where
$\mathcal{R}\circ\mathcal{M}_{2}\circ\mathcal{T}$ is required to be
$\epsilon$-close, say in diamond norm distance, to $\mathcal{M}_{1}$. We say
that a target channel $\mathcal{M}_{1}$ is asymptotically faithfully simulable
with a resource channel $\mathcal{M}_{2}$ if there exists a sequence of
simulations $(\mathcal{R}_{n}\circ\mathcal{M}_{2}^{\otimes
n}\circ\mathcal{T}_{n})_{n\in\mathbb{N}}$ and a sequence of non-negative
numbers $(\epsilon_{n})_{n\in\mathbb{N}}$ such that
$\mathcal{R}_{n}\circ\mathcal{M}_{2}^{\otimes n}\circ\mathcal{T}_{n}$ is
$\epsilon_{n}$-close to $\mathcal{M}_{1}$ in diamond norm distance and
$\epsilon_{n}\rightarrow 0$ as $n\rightarrow\infty$. Another kind of
simulation to consider is resource-assisted simulation, where the encoder and
decoder have access to auxiliary joint resources such as classical
communication or entanglement. Quantum channel simulation is a special type of
resource conversion as studied in the context of quantum resource theory [28].

Following the same reasoning as in the proof of Prop. 5.2.1, one can verify
that if $q\leq p$, then $\mathcal{E}_{p}$ is exactly simulable with
$\mathcal{E}_{q}$. If $q\leq\frac{1}{2}$, then the forward coding theorem for
quantum erasure channels [14, 27] says that the identity is asymptotically
faithfully simulable by $\mathcal{E}_{q}$ at a nonzero rate. Specifically, it
says that there is a sequence of codes $(\mathcal{C}_{n})_{n\in\mathbb{N}}$,
where $\mathcal{C}_{n}\leq\mathcal{H}^{\otimes n}$, and recovery channels
$(\mathcal{R}_{n})_{n\in\mathbb{N}}$ such that
$\mathcal{R}_{n}\circ\mathcal{E}_{q}^{\otimes
n}\circ\mathcal{U}_{\mathcal{C}_{n}}$ differs from $\mathrm{id}^{\otimes
k_{n}}$ by $\epsilon_{n}$ and $\lim_{n\rightarrow\infty}\frac{k_{n}}{n}>0$ and
$\lim_{n\rightarrow\infty}\varepsilon_{n}=0$. Even in the setting of exact
simulation, where it is clear that $\mathrm{id}$ is not simulable by
$\mathcal{E}_{q}^{\otimes n}$ for any $q>0$ and $n\in\mathbb{N}$, quantum
error correcting codes may be used to improve quantum erasure channels. Here,
improve means that the channel may be used to simulate another with a strictly
lower erasure probability. Here is a simple example of that.

######  Example 5.3.4.

Consider the following code in $(\mathbb{C}^{2})^{\otimes 4}$:

$\displaystyle\mathcal{C}_{[[4,1,2]]_{2}}=\text{span}({|{0}\rangle}_{L}\propto{|{0000}\rangle}+{|{1111}\rangle},{|{1}\rangle}_{L}\propto{|{1001}\rangle}+{|{0110}\rangle}).$
(5.3.5)

This is a $[[4,1,2]]_{2}$ stabilizer code, the smallest code capable of
correcting the erasure of a single qubit [38]. Notably, it does not correct
the erasure of any two qubits. To see this, observe that $Z\otimes Z\otimes
I\otimes I$ acts as a logical $Z$ operator when restricted to the code. The
same is true for $Z\otimes I\otimes Z\otimes I$, $I\otimes Z\otimes I\otimes
Z$ and $I\otimes I\otimes Z\otimes Z$. So, erasure of qubit pairs
$(1,2),(1,3),(2,4)$ and $(3,4)$ cannot be corrected. Similarly, observe that
$X\otimes I\otimes I\otimes X$ and $I\otimes X\otimes X\otimes I$ act as a
logical $X$. Hence, there is no recovery from the erasure of qubit pairs
$(1,4)$ or $(2,3)$.

Figure 5.1: This is a plot of the difference of erasure probabilities
$q_{4}-q$ vs the erasure probability of the resource channel $q$. As $q$
increases, high-weight erasures become more likely. These are erasures that
the code $\mathcal{C}_{[[4,1,2]]_{2}}$ cannot correct.

This code may be used along with $\mathcal{E}_{q}^{\otimes 4}$ and the
following recovery procedure. If there is one error, correct and output the
state. Otherwise, output the error flag ${|{e}\rangle}$. Let
$\mathcal{R}_{[[4,1,2]]_{2}}$ denote the channel implementing this procedure.
Then,

$\displaystyle\mathcal{R}_{[[4,1,2]]_{2}}\circ\mathcal{E}_{q}^{\otimes
4}\circ\mathcal{U}_{\mathcal{C}_{[[4,1,2]]_{2}}}=\mathcal{E}_{q_{4}},$ (5.3.6)

where $q_{4}=\sum_{k=2}^{4}\binom{4}{k}q^{k}(1-q)^{4-k}$. Fig. 5.1 shows a
plot of the difference of erasure probabilities $q_{4}-q$ versus $q$. As long
as $q$ is small enough, precisely below $\frac{1}{6}(5-\sqrt{13})$, the
simulated channel $\mathcal{E}_{q_{4}}$ is better than $\mathcal{E}_{q}$. We
show later on that $\mathcal{E}_{q_{4}}$ is in fact the best erasure channel
that $\mathcal{E}_{q}^{\otimes 4}$ can be used to simulate with this code.

Our main concern will be the more interesting case where $q\geq\frac{1}{2}$.
Clearly, for such $q$, $\mathcal{E}_{q}^{\otimes n}$ cannot be used to
simulate $\mathcal{E}_{p}$ for $p<\frac{1}{2}$ no matter how large $n$ is.
Otherwise, $\mathcal{E}_{q}$ would have nonzero quantum capacity. The next
question to ask is this: can these channels be improved at all? This question
was studied by Hastings [43]. Using an argument based on the no-cloning
theorem, he showed that for each $m\in\mathbb{N}$, the channel
$\mathcal{E}_{1-\frac{1}{m}}$ cannot be improved.

######  Conjecture 5.3.5.

(Hastings’ conjecture). For $q\in[\frac{1}{2},1]$ and $p<q$, it is not
possible to simulate $\mathcal{E}_{p}$ with $\mathcal{E}_{q}$.

Hastings’ conjecture is the inspiration for this chapter. In the original
statement of the conjecture, “simulation” referred to asymptotically faithful
simulation. We are primarily concerned with exact simulation of erasure. That
is, we consider all simulations of erasure

$\displaystyle\mathcal{E}_{p}=\mathcal{R}\circ\mathcal{E}_{q}^{\otimes
n}\circ\mathcal{T},$ (5.3.7)

with the aim of finding non-trivial lower bounds for $p$. Given that we
suspect that Conj. 5.3.5 holds, we may take $n$ as large as needed and so by
Prop. 5.3.3 from now on we take the encoding channels to be isometric. For an
isometric encoding channel $\mathcal{U}_{\mathcal{C}_{n}}$ and a decoding
channel $\mathcal{R}$, we may expand sums over tensor products and use the
linearity of channels to get

$\displaystyle\mathcal{R}\circ\mathcal{E}_{q}^{\otimes
n}\circ\mathcal{U}_{\mathcal{C}_{n}}=\sum_{S\subseteq[n]}q^{n-|S|}(1-q)^{|S|}\mathcal{R}\circ(\iota^{\otimes
S}\otimes{|{e}\rangle}{\langle{e}|}^{\otimes
S^{c}}\tr_{S^{c}})\circ\mathcal{U}_{\mathcal{C}_{n}}.$ (5.3.8)

Here, $S^{c}\subseteq[n]$ is the set of erased systems, which following [43],
we call an erasure pattern. We show in Section 5.5 that we may as well take
$\mathcal{R}\circ(\iota^{\otimes S}\otimes{|{e}\rangle}{\langle{e}|}^{\otimes
S^{c}}\tr_{S^{c}})\circ\mathcal{U}_{\mathcal{C}_{n}}$ to be an erasure channel
$\mathcal{E}_{1-\gamma_{S}(\mathcal{C}_{n})}$. Here,
$\gamma_{S}(\mathcal{C}_{n})$ is the optimal probability of recovery of
quantum information conditional on the occurrence of erasure pattern $S^{c}$
for the code $\mathcal{C}_{n}$. We show that it can be computed via a semi-
definite program in Section 5.4. Therefore, the problem becomes finding non-
trivial upper bounds for the optimal overall recovery probability

$\displaystyle
r_{q,n}=\mathrm{sup}_{\mathcal{C}_{n}}\sum_{S\subseteq[n]}q^{n-|S|}(1-q)^{|S|}\gamma_{S}(\mathcal{C}_{n})$
(5.3.9)

for all $n\in\mathbb{N}$. Since $(r_{q,n})_{n\in\mathbb{N}}$ is monotonically
non-decreasing, it suffices to bound from above
$r_{q}=\lim_{n\rightarrow\infty}r_{q,n}$. According to Conj. 5.3.5, $r_{q}\leq
1-q$ for $q\in[\frac{1}{2},1]$.

###  5.4 Erasure simulation and probabilistic error correction

In this section, we collect a few observations about probabilistic recovery of
quantum information and how it relates to exact simulation of erasure. By
probabilistic recovery, we mean recovery procedures where decoding super-
operators are trace non-increasing. This scenario was considered by Nayak and
Sen in the context of quantum state encryption [57]. They state a
characterization of what they call invertible quantum operations—those are
completely-positive maps with a completely-positive inverse—pointed out to
them by Jon Tyson (see Theorem 2.2 in [57]). More recently, Kukulski et al.
systematically studied this scenario in [50] and noted that the optimal
recovery probability for a given encoding map is a solution to a semi-definite
program parameterized by the error channel. We arrived at this observation
independently.

Since we established in Prop. 5.3.3 that we may consider isometric encoding
channels without loss of generality, we formulate the conditions for
probabilistic recovery using codes. For a more general formulation, see [50].

######  Definition 5.4.1.

Let a channel
$\mathcal{M}:\mathcal{B}(\mathcal{H})\rightarrow\mathcal{B}(\mathcal{K})$ be
given. We say that $\mathcal{C}\leq\mathcal{H}$ is a
$(\mathcal{M},t)$-correcting code if there is a completely-positive, trace
non-increasing
$\mathcal{R}:\mathcal{B}(\mathcal{K})\rightarrow\mathcal{B}(\mathcal{H})$ such
that

$\displaystyle\mathcal{R}\circ\mathcal{M}\circ(P_{\mathcal{C}}(\cdot)P_{\mathcal{C}})=tP_{\mathcal{C}}(\cdot)P_{\mathcal{C}},$
(5.4.1)

where the proportionality constant $t$ is the probability of recovery.

If the action of the channel on the code is not one-to-one, then recovery with
positive probability is not possible. The converse statement is not true. For
example, for $0<p<\frac{4}{3}$, the partially-depolarizing qubit channel
$\Delta_{2,p}$ (Eq. 2.3.3) is one-to-one on $\mathcal{B}(\mathbb{C}^{2})$.
However, if $p>0$, then the maximum probability of recovery is zero by Lem.
5.6.3. The following proposition gives necessary and sufficient conditions for
probabilistic recovery in terms of the code and Kraus operators of the error
channel.

######  Proposition 5.4.2.

Let a channel
$\mathcal{M}:\mathcal{B}(\mathcal{H})\rightarrow\mathcal{B}(\mathcal{K})$ with
Kraus decomposition $\\{M_{\alpha}\\}_{\alpha=1}^{M}$ be given. A code
$\mathcal{C}\leq\mathcal{H}$ is $(\mathcal{M},t)$-correcting if and only if
there exist a positive semi-definite operator $\Pi\in\mathcal{B}(\mathcal{K})$
satisfying $\Pi\leq\mathds{1}_{\mathcal{K}}\;$ and an $M\times M$ matrix $T$
satisfying $\tr(T)=t$, such that

$\displaystyle P_{\mathcal{C}}M_{\beta}^{*}\Pi
M_{\alpha}P_{\mathcal{C}}=T_{(\alpha,\beta)}P_{\mathcal{C}}$ (5.4.2)

holds for all $\alpha,\beta\in[M]$.

###### Proof.

For necessity, we argue as in Theorem 10.1 of Ref. [60]. Suppose that
$\mathcal{R}\circ\mathcal{M}(P_{\mathcal{C}}(\cdot)P_{\mathcal{C}})=tP_{\mathcal{C}}(\cdot)P_{\mathcal{C}}$
for some $\mathcal{R}\sim\\{R_{\ell}\\}_{\ell=1}^{L}$. By theorem 8.2 of Ref.
[60], this implies the existence of a set of complex coefficients
$\\{u_{(\ell,\alpha)}\\}_{\alpha=1,\ell=1}^{\alpha=M,\ell=L}$ such that
$R_{\ell}M_{\alpha}P_{\mathcal{C}}=u_{(\ell,\alpha)}P_{\mathcal{C}}$ for all
$\alpha\in[M]$ and $\ell\in[L]$. Multiplying on the left by
$P_{\mathcal{C}}M^{*}_{\beta}R^{*}_{\ell}$ and summing over $\ell$ yields

$\displaystyle
P_{\mathcal{C}}M_{\beta}^{*}(\sum_{\ell}R_{\ell}^{*}R_{\ell})M_{\alpha}P_{\mathcal{C}}=(\sum_{\ell}u_{(\ell,\beta)}^{*}u_{(\ell,\alpha)})P_{\mathcal{C}}=T_{(\alpha,\beta)}P_{\mathcal{C}}.$
(5.4.3)

Let $\Pi=\sum_{\ell=1}^{L}R_{\ell}^{*}R_{\ell}$ and observe that $\tr(T)=t$.
For sufficiency, let $\Pi\geq 0$ be given and let $\xi$ be any operator
satisfying $\xi^{*}\xi=\Pi$ such as $\sqrt{\Pi}$ for example. Observe that
$\mathcal{C}$ satisfies the quantum error correction conditions Eq. 2.3.1 for
the error super-operator $\xi\mathcal{M}(\cdot){\xi^{*}}$ and so there exists
a recovery channel $\mathcal{R}$ for it. Hence, the completely-positive, trace
non-increasing map $\tilde{\mathcal{R}}=\mathcal{R}\circ\xi(\cdot)\xi^{*}$
satisfies
$\tilde{\mathcal{R}}\circ\mathcal{M}(P_{\mathcal{C}}(\cdot)P_{\mathcal{C}})=\tr(T)P_{\mathcal{C}}(\cdot)P_{\mathcal{C}}.$
∎

We call the positive semi-definite operator $\Pi$ a recovery operator for the
channel $\mathcal{M}$ and the code $\mathcal{C}$. On the decoder side,
$\sqrt{\Pi}(\cdot)\sqrt{\Pi}$ can be realized as part of a channel with the
aid of an auxiliary qubit. Namely, the decoder may implement the following
isometry:

$\displaystyle\mathcal{K}\ni{|{\phi}\rangle}\mapsto\sqrt{\Pi}{|{\phi}\rangle}\otimes{|{0}\rangle}_{\text{aux}}+\sqrt{\mathds{1}-\Pi}{|{\phi}\rangle}\otimes{|{1}\rangle}_{\text{aux}}$
(5.4.4)

By measuring this auxiliary qubit in the computational basis, the decoder can
ascertain whether $\sqrt{\Pi}$ occurred or not. If the result of the
measurement is $0$, then a channel may be applied to recover the quantum
information. Otherwise, the decoder may declare the occurrence of an error by
outputting an error flag. This occurs with probability $1-\tr(T)$. This proves
the following corollary.

######  Corollary 5.4.3.

A code $\mathcal{C}$ is $(\mathcal{M},t)$-correcting for a channel
$\mathcal{M}$ if and only if $\mathcal{M}$ can be used to simulate an erasure
channel with erasure probability $1-t$ with $\mathcal{U}_{\mathcal{C}}$ as an
encoding channel.

Next, we observe that for a given code and error channel, the set of recovery
operators is convex and contains the zero operator. A more general version of
the following corollary is on page 4 of Ref. [50].

######  Corollary 5.4.4.

Given a channel $\mathcal{M}\sim\\{M_{k}\\}_{k=1}^{M}$ and a code
$\mathcal{C}$, the maximum recovery probability for $\mathcal{M}$ with
$\mathcal{C}$ is the value of the following semi-definite program

max $\displaystyle\tr(T),$ (5.4.5) subject to: $\displaystyle
0\leq\Pi\leq\mathds{1},$ (5.4.6) $\displaystyle
P_{\mathcal{C}}M_{k^{\prime}}^{*}\Pi
M_{k}P_{\mathcal{C}}=T_{k,k^{\prime}}P_{\mathcal{C}},\quad\forall
k,k^{\prime}\in[M].$ (5.4.7)

If the value of the program above is $t_{\text{opt}}$, then the best erasure
channel that $\mathcal{M}$ can be used to simulate with the code $\mathcal{C}$
is $\mathcal{E}_{1-t_{opt}}$.

Given a channel $\mathcal{M}$, a code $\mathcal{C}$, and a recovery operator
$\Pi$, a geometric interpretation of the recovery of quantum information with
nonzero probability is obtained by considering a Kraus decomposition of
$\mathcal{M}$ where the coefficient matrix $T$—a positive semi-definite
matrix—is diagonal. That this decomposition exists follows from theorem 8.2 of
Ref. [60]. Since $\tr(T)>0$, then for some Kraus operator in this
decomposition, say $M_{1}$, it holds that $P_{\mathcal{C}}M_{1}^{*}\Pi
M_{1}P_{\mathcal{C}}=T_{(1,1)}P_{\mathcal{C}}$ and $T_{(1,1)}\neq 0$. Hence,
$\sqrt{\Pi}M_{1}|_{\mathcal{C}}$ is invertible. Since $T$ is diagonal, then
the image of $\mathcal{C}$ under $\sqrt{\Pi}M_{1}$ is orthogonal to its image
under $\sqrt{\Pi}M_{k}$ for $k\neq 1$. This is possible only if the subspace
$M_{1}\mathcal{C}$, which necessarily has dimension $\text{dim}(\mathcal{C})$,
and the subspace $\sum_{k\neq 1}M_{k}\mathcal{C}$ are linearly independent.
That is, $M_{1}\mathcal{C}\cap\sum_{k\neq 1}M_{k}\mathcal{C}=\\{0\\}$. To see
this, observe that if there is a nonzero vector in the intersection, then the
orthogonality relations in Eq. 5.4.2 do not hold. Conversely, if
$M_{1}|_{\mathcal{C}}$ is invertible and the intersection is trivial, then
there exists an operator $\xi$ such that $\xi
M_{1}|_{\mathcal{C}}=t\mathds{1}$, with $t>0$, and
$\text{ker}(\xi)\geq\sum_{k\neq 1}M_{k}\mathcal{C}$. This implies the
following corollary.

######  Corollary 5.4.5.

A code $\mathcal{C}$ is $(\mathcal{M},t)$ correcting for some $t>0$ if and
only if $\mathcal{M}$ admits a Kraus decomposition $\\{M_{k}\\}_{k=1}^{M}$
such that for some $k_{0}\in[M]$, the following holds:

  1. 1.

$M_{k_{0}}$ is invertible on $\mathcal{C}$.

  2. 2.

$M_{k_{0}}\mathcal{C}\cap\sum_{k\neq k_{0}}M_{k}\mathcal{C}=\\{0\\}$.

###  5.5 Structure of channels contributing to a convex decomposition of
erasure

In this section, we characterize the possible ways an erasure channel can be
written as a convex combination of channels. Specifically, we give necessary
and sufficient conditions for a channel to contribute to a convex
decomposition of an erasure channel in terms of its Choi operator.
Furthermore, we give an explicit characterization of the extremal points of
this set, which include the isometry $\iota$ and the probability one erasure
channel ${|{e}\rangle}{\langle{e}|}\tr$. In particular, we show that every
non-extremal erasure channel can be written as a convex combination of two
channels neither of which is an erasure channel itself. This is a surprising
fact, given that at a first glance, it might seem like this set is entirely
comprised of erasure channels.

In this section, we suppress the inclusion map $\iota$ and write
$\tilde{\mathcal{H}}=\mathcal{H}\oplus\mathbb{C}{|{e}\rangle}$. Given a super-
operator
$\mathcal{T}:\mathcal{B}(\mathcal{H})\rightarrow\mathcal{B}(\tilde{\mathcal{H}})$,
its Choi operator can be written in block form:

$\displaystyle\sigma(\mathcal{T})=\begin{pmatrix}A(\mathcal{T})&&B(\mathcal{T})^{*}\\\
B(\mathcal{T})&&C(\mathcal{T})\end{pmatrix}$ (5.5.1)

where $A(\mathcal{T})\in\mathcal{B}(\mathcal{H}_{R}\otimes\mathcal{H})$,
$B(\mathcal{T}):\mathcal{H}_{R}\otimes\mathcal{H}\rightarrow\mathcal{H}_{R}\otimes\mathbb{C}{|{e}\rangle}$
and
$C(\mathcal{T})\in\mathcal{B}(\mathcal{H}_{R}\otimes\mathbb{C}{|{e}\rangle})$.
If $\sigma(\mathcal{T})\geq 0$, then it necessarily holds that
$A(\mathcal{T})\geq 0$ and $C(\mathcal{T})\geq 0$. For an erasure channel
$\mathcal{E}_{\alpha}$, it is clear that
$A(\mathcal{E}_{\alpha})=(1-\alpha){|{\beta}\rangle}{\langle{\beta}|},B(\mathcal{E}_{\alpha})=0$
and
$C(\mathcal{E}_{\alpha})=\alpha\mathds{1}\otimes{|{e}\rangle}{\langle{e}|}_{\mathcal{}}$.

######  Proposition 5.5.1.

Consider a convex decomposition of an erasure channel,

$\displaystyle\mathcal{E}_{\alpha}=\sum_{k}r_{k}\mathcal{M}_{k},$ (5.5.2)

where $\alpha\in[0,1]$ and for each $k$, $r_{k}>0$ and $\mathcal{M}_{k}$ is a
channel. With respect to the block structure of Eq. 5.5.1, the Choi operators
of $\mathcal{M}_{k}$ satisfy

$\displaystyle A(\mathcal{M}_{k})$
$\displaystyle=(1-\alpha_{k}){|{\beta}\rangle}{\langle{\beta}|},$ (5.5.3)
$\displaystyle C(\mathcal{M}_{k})$
$\displaystyle=\alpha_{k}\mathds{1}\otimes{|{e}\rangle}{\langle{e}|},$ (5.5.4)
$\displaystyle B(\mathcal{M}_{k})$
$\displaystyle=\eta_{k}{|{\delta_{k}}\rangle}{\langle{\beta}|},$ (5.5.5)

where $\alpha_{k}\in[0,1]$,
${|{\delta_{k}}\rangle}\in\mathcal{H}_{R}\otimes\mathbb{C}{|{e}\rangle}$ has
unit norm, and $\eta_{k}\geq 0$ satisfies
$\eta_{k}\leq\sqrt{\alpha_{k}(1-\alpha_{k})}$.

###### Proof.

By the linearity of the Choi isomorphism, we have
$\sum_{k}r_{k}A(\mathcal{M}_{k})=A(\mathcal{E}_{\alpha})=(1-\alpha){|{\beta}\rangle}{\langle{\beta}|}$,
which has rank at most 1. The result of a positive combination of positive
semi-definite operators has rank at most 1 if and only if each operator in the
sum is proportional to the result. That is,
$A(\mathcal{M}_{k})=(1-\alpha_{k}){|{\beta}\rangle}{\langle{\beta}|}$ for some
$\alpha_{k}\in[0,1]$. Since each $\mathcal{M}_{k}$ is trace-preserving,

$\displaystyle\tr_{\tilde{\mathcal{H}}}(\sigma(\mathcal{M}_{k}))=\tr_{\mathcal{H}}(A(\mathcal{M}_{k}))+\tr_{\mathbb{C}{|{e}\rangle}}(C(\mathcal{M}_{k}))=\mathds{1}_{R}.$
(5.5.6)

Therefore,
$C(\mathcal{M}_{k})=\alpha_{k}\mathds{1}\otimes{|{e}\rangle}{\langle{e}|}$. If
$\alpha_{k}\in\\{0,1\\}$, then $B(\mathcal{M}_{k})=0$. To see this, notice
that if $\alpha_{k}=0$, then $C(\mathcal{M}_{k})=0$. In this case, the off-
diagonal blocks have to be zero, or else $\sigma(\mathcal{M}_{\alpha})$ has a
negative eigenvalue. The same is true for the case where $\alpha_{k}=1$ as
that implies $A(\mathcal{M}_{k})=0$. If $\alpha_{k}\in(0,1)$, then the Schur
complement of $\sigma(\mathcal{M}_{k})/C(\mathcal{M}_{k})$ must be positive
semi-definite for $\sigma(\mathcal{M}_{k})$ to be positive semi-definite. That
is,

$\displaystyle(1-\alpha_{k}){|{\beta}\rangle}{\langle{\beta}|}-\alpha_{k}^{-1}|B(\mathcal{M}_{k})|^{2}\geq
0.$ (5.5.7)

Hence, $B(\mathcal{M}_{k})$ is an operator whose support is spanned by
${|{\beta}\rangle}$ and whose largest singular value is no larger than
$\sqrt{\alpha_{k}(1-\alpha_{k})}$. ∎

It follows from this proposition that $\mathcal{E}_{\alpha}$, with
$\alpha\in(0,1)$, can be written as a convex combination of two channels whose
Choi states have nonzero off-diagonal block matrices. That is, neither of the
two is an erasure channel. For example, for a unit vector
${|{0}\rangle}\in\mathcal{H}_{R}$, consider the two channels with the
following Choi operators

$\displaystyle\sigma(\mathcal{M}_{\alpha,\pm})=\begin{pmatrix}(1-\alpha){|{\beta}\rangle}{\langle{\beta}|}&&\pm\sqrt{\alpha(1-\alpha)}{|{\beta}\rangle}{\langle{e}|}\otimes{\langle{0}|}\\\
\pm\sqrt{\alpha(1-\alpha)}{|{0}\rangle}\otimes{|{e}\rangle}{\langle{\beta}|}&&\alpha\mathds{1}\otimes{|{e}\rangle}{\langle{e}|}\end{pmatrix}.$
(5.5.8)

We have
$\frac{1}{2}(\mathcal{M}_{\alpha,+}+\mathcal{M}_{\alpha,-})=\mathcal{E}_{\alpha}$.
More notably, the set of channels satisfying Eqs. 5.5.3, 5.5.4 and 5.5.5 is
the preimage of the set of erasure channels under left composition with
decoherence of $\mathcal{H}$ and $\mathbb{C}{|{e}\rangle}$. That, composition
the channel with Kraus operators
$\mathds{1}_{\tilde{\mathcal{H}}}-{|{e}\rangle}{\langle{e}|}$ and
${|{e}\rangle}{\langle{e}|}$. Erasure channels are invariant under left
composition with this channel. Hence, if Eq 5.3.7 holds, then without loss of
generality, it may be assumed that

$\displaystyle\mathcal{R}\circ(\iota^{\otimes
S}\otimes{|{e}\rangle}{\langle{e}|}^{\otimes
S^{c}}\tr_{S^{c}})\circ\mathcal{T}=\mathcal{E}_{1-\gamma_{S}}$ (5.5.9)

for each erasure pattern $S^{c}\subseteq[n]$.

In the next proposition, we show that the set of extremal channels among
channels satisfying Eqs. 5.5.3, 5.5.4 and 5.5.5 consists of $\iota$ and
channels $\mathcal{M}$ where the Schur complement
$\sigma(\mathcal{M})/C(\mathcal{M})$ vanishes.

######  Proposition 5.5.2.

Suppose that $\mathcal{M}\neq\iota$ is a channel that satisfies (5.5.3),
(5.5.4) and (5.5.5) for some $\alpha,\eta,{|{\delta}\rangle}$. Then,
$\mathcal{M}$ is an extremal channel if and only if the Schur complement of
$C(\mathcal{M})$ vanishes.

###### Proof.

Suppose that the Schur complement of $C(\mathcal{M})$ vanishes. That is,
$\eta=\sqrt{\alpha(1-\alpha)}$. If
$\sigma(\mathcal{M})=\sum_{k}r_{k}\sigma(\mathcal{M}_{k})$, such that for all
$k$, $r_{k}>0$, then each $\mathcal{M}_{k}$ satisfies (5.5.3), (5.5.4) and
(5.5.5) as argued before. Let the relevant parameters be $\alpha_{k},\eta_{k}$
and ${|{\delta_{k}}\rangle}$ for each channel $\mathcal{M}_{k}$. Then it
follows from the linearity of $\sigma$ that

$\displaystyle\sum_{k}r_{k}\alpha_{k}$ $\displaystyle=\alpha,$ (5.5.10)
$\displaystyle\sum_{k}r_{k}\eta_{k}{|{\delta_{k}}\rangle}$
$\displaystyle=\sqrt{\alpha(1-\alpha)}{|{\delta}\rangle}.$ (5.5.11)

Observe the chain of inequalities

$\displaystyle\sqrt{\alpha(1-\alpha)}=||\sqrt{\alpha(1-\alpha)}{|{\delta}\rangle}||_{2}$
$\displaystyle=||\sum_{k}r_{k}\eta_{k}{|{\delta_{k}}\rangle}||_{2}$ (5.5.12)
$\displaystyle\leq\sum_{k}r_{k}\eta_{k}$ (5.5.13)
$\displaystyle\leq\sum_{k}r_{k}\sqrt{\alpha_{k}(1-\alpha_{k})}$ (5.5.14)
$\displaystyle\leq\sqrt{\alpha(1-\alpha)}.$ (5.5.15)

Each inequality has to be satisfied with equality. The first inequality is the
triangle inequality for $||\cdot||_{2}$ and so is saturated if and only if
${|{\delta_{k}}\rangle}={|{\delta}\rangle}$ for all $k$. The second inequality
is saturated if and only if $\eta_{k}=\sqrt{\alpha_{k}(1-\alpha_{k})}$ for all
$k$. The third inequality is saturated if and only if $\alpha_{k}=\alpha$ all
$k$ by the strict concavity of the function $f(t)=\sqrt{t(1-t)}$ on $(0,1)$.
Therefore, $\mathcal{M}_{k}=\mathcal{M}$ for each $k$ and so $\mathcal{M}$ is
extremal.

Conversely, suppose that $\mathcal{M}$ is extremal. Consider the following
pair of operators

$\displaystyle\begin{pmatrix}A(\mathcal{M})&&(1\pm\epsilon)B(\mathcal{M})^{*}\\\
(1\pm\epsilon)B(\mathcal{M})&&C(M)\end{pmatrix},$ (5.5.16)

where $\epsilon>0$. The extremal Choi operator $\sigma(\mathcal{M})$ is an
average of these two operators. Under the Choi isomorphism, the two correspond
with trace-preserving super-operators as their value under a partial trace of
$\tilde{\mathcal{H}}$ is $\mathds{1}_{R}$. Since $\mathcal{M}$ is an extremal
channel, the corresponding super-operators cannot be both completely positive.
Therefore, one of the two operators above must have a negative eigenvalue.
This implies in particular that $(1+\epsilon)^{2}\eta^{2}>\alpha(1-\alpha)$
for all $\epsilon\in(0,1)$. This implies $\eta=\sqrt{\alpha(1-\alpha)}$ and
the Schur complement of $C(\mathcal{M})$ vanishes. ∎

###  5.6 Progress on Hastings’ conjecture

In this section, we restrict our attention to isometric encoding channels into
a sequence of codes $(\mathcal{C}_{n})_{n\in\mathbb{N}}$. As stated before,
this comes at no loss of generality for the purposes of Hastings’ conjecture
as we argue in the large $n$ limit. The output of $\mathcal{E}_{q}^{\otimes
n}$ is a convex combination of orthogonal states. The decoder may start with a
projective measurement whose outcome corresponds with the occurring erasure
pattern. This does not disturb the state and so causes no loss of information.
The decoder may then tailor a recovery procedure for each erasure pattern.

######  Lemma 5.6.1.

Let a code $\mathcal{C}\leq\mathcal{H}^{\otimes n}$ be given. For
$S\subseteq[n]$, let $\sigma_{S^{c}}\in\mathcal{D}(\mathcal{K}^{S^{c}})$ be
given. There exists an optimal recovery operator for
$\tr_{S^{c}}\otimes\sigma_{S^{c}}$ and $\mathcal{C}$ of the form
$A_{S}\otimes\mathds{1}_{S^{c}}$.

###### Proof.

Let $\Pi\in\mathcal{P}(\mathcal{H}^{\otimes S})$ be an optimal recovery
operator for $\tr_{S^{c}}$ and $\mathcal{C}$. Then,
$\Pi_{S}\otimes\mathds{1}_{S^{c}}$ is a recovery operator for
$\tr_{S^{c}}\otimes\sigma_{S^{c}}$ and $\mathcal{C}$. If
$\Pi_{S}\otimes\mathds{1}_{S^{c}}$ were not optimal, then the decoder may
tensor multiply $\sigma_{S^{c}}$ to the output of $\tr_{S^{c}}$ and find a
strictly better recovery procedure for $\tr_{S^{c}}$. ∎

From now on, $\Pi_{S}(\mathcal{C})\in\mathcal{P}(\tilde{\mathcal{H}}^{\otimes
S})$ denotes an operator such that
$\Pi_{S}(\mathcal{C})\otimes\mathds{1}_{S^{c}}$ is an optimal recovery
operator—that is, an optimal point for the program 5.4.5 for a given code
$\mathcal{C}$—for the erasure pattern $S^{c}\subseteq[n]$. The channel
$\tr_{S^{c}}\otimes{|{e}\rangle}{\langle{e}|}^{S^{c}}$ admits a Kraus
decomposition $\\{\mathds{1}_{S}\otimes(M_{i})_{S^{c}}\\}_{i=1}^{m}$, where
$(M_{i})_{S^{c}}:\mathcal{H}^{\otimes
S^{c}}\rightarrow\tilde{\mathcal{H}}^{\otimes S^{c}}$ for each $i\in[m]$. It
is clear that the optimal recovery operator
$\Pi_{S}(\mathcal{C})\otimes\mathds{1}_{S^{c}}$ commutes with all of these
Kraus operators. From Eq. 5.4.2, we get

$\displaystyle\sum_{i=1}^{m}P_{\mathcal{C}}((\iota^{*})^{\otimes
S}\otimes(M_{i})_{S^{c}}^{*})(\Pi_{S}(\mathcal{C})\otimes\mathds{1}_{S^{c}})(\iota^{\otimes
S}\otimes(M_{i})_{S^{c}})P_{\mathcal{C}}$
$\displaystyle=\sum_{i=1}^{m}T_{(i,i)}P_{\mathcal{C}}$ (5.6.1) $\displaystyle
P_{\mathcal{C}}((\iota^{*})^{\otimes S}\Pi_{S}(\mathcal{C})(\iota)^{\otimes
S}\otimes\mathds{1}_{S^{c}})\sum_{i=1}^{m}(\mathds{1}_{S}\otimes(M_{i})_{S^{c}}^{*}(M_{i})_{S^{c}})P_{\mathcal{C}}$
$\displaystyle=\gamma_{S}(\mathcal{C})P_{\mathcal{C}}$ (5.6.2) $\displaystyle
P_{\mathcal{C}}((\iota^{*})^{\otimes S}\Pi_{S}(\mathcal{C})(\iota)^{\otimes
S}\otimes\mathds{1}_{S^{c}})P_{\mathcal{C}}$
$\displaystyle=\gamma_{S}(\mathcal{C})P_{\mathcal{C}},$ (5.6.3)

where $\gamma_{S}(\mathcal{C})$ denotes the optimal recovery probability for
the code $\mathcal{C}$. From now on, we suppress the symbol $\iota$. When
clear from context, we write $\Pi_{S}$ to mean
$\Pi_{S}(\mathcal{C})\otimes\mathds{1}_{S^{c}}$ and $\gamma_{S}$ to mean
$\gamma_{S}(\mathcal{C})$ for some code $\mathcal{C}\leq\mathcal{H}^{\otimes
n}$. From the third equation in Eqs. 5.6.1, we see that when restricted to the
code, the action of $\sqrt{\Pi_{S}}$ is, up to a multiplicative factor,
isometric.

Let $T_{A},T_{B}\subseteq[n]$ be disjoint sets and suppose that both
$\Pi_{T_{A}}$ and $\Pi_{T_{B}}$ are optimal recovery operators for some code
$\mathcal{C}$. Let decoder $A$ be in control of the systems in $T_{B}$ and
decoder $B$ be in control of the systems in $T_{B}$. Both may implement
isometries as in Eq .5.4.4 to recover the quantum information. If upon
measuring their auxiliary qubit, decoder $A$ finds that they can recover the
quantum information, then it must be the case that decoder $B$ cannot recover
with any positive probability. Otherwise, the two can construct a linear
cloning machine. The same holds with $A$ and $B$ reversed. Hence, it must be
the case that $\mathcal{C}\leq\text{ker}(\Pi_{T_{A}}\Pi_{T_{B}})$. This has
consequences for the optimal recovery probabilities associated with these
patterns.

######  Proposition 5.6.2.

Let $\\{S_{i}\\}_{i\in I}$ be a partitioning of $[n]$. Then, it holds that

$\displaystyle 1\geq\sum_{i\in I}\gamma_{S_{i}}.$ (5.6.4)

###### Proof.

First observe that $\\{\Pi_{S_{i}}\\}_{i\in I}$ is a set of mutually commuting
positive semi-definite operators. Hence,

$\displaystyle P_{C}\prod_{i\in I}(\mathds{1}-\Pi_{S_{i}})P_{C}\geq 0.$
(5.6.5)

Expand the product and notice that $P_{\mathcal{C}}\prod_{j\in
J}\Pi_{S_{j}}P_{\mathcal{C}}=0$ whenever $|J|>1$. This along with Eq. 5.6.1
imply the desired inequality. ∎

Another observation to be made is the following. If $S$ contains one element,
then recovery or lack thereof is deterministic. An intuitive explanation for
this fact is that there is not enough room in a single qudit for the encoded
quantum information and the classical information about whether recovery is
possible. This is a consequence of the following lemma.

######  Lemma 5.6.3.

A completely positive map
$\mathcal{M}:\mathcal{B}(\mathcal{H})\rightarrow\mathcal{B}(\mathcal{H})$ has
a completely positive inverse if and only if $\mathcal{M}\sim\\{M\\}$ for some
invertible operator $M\in\mathcal{B}(\mathcal{H})$.

###### Proof.

It is clear that the map $M(\cdot)M^{*}$ has the completely positive inverse
$M^{-1}(\cdot)(M^{-1})^{*}$ whenever $M$ is invertible. For the other
direction, suppose that $\mathcal{R}\sim\\{R_{\ell}\\}_{\ell=1}^{r}$ is a
completely positive inverse of $\mathcal{M}\sim\\{M_{k}\\}_{k=1}^{m}$. Without
loss of generality, $M_{k}\neq 0$ for all $k\in[m]$ and $R_{\ell}\neq 0$ for
all $\ell\in[r]$. Notice that for each unit vector
${|{\alpha}\rangle}\in\mathcal{H}$,

$\displaystyle{|{\alpha}\rangle}{\langle{\alpha}|}=\sum_{\ell=1}^{r}\sum_{k=1}^{m}R_{\ell}M_{k}{|{\alpha}\rangle}{\langle{\alpha}|}M_{k}^{*}R_{\ell}^{*}.$
(5.6.6)

This is a sum of positive semi-definite operators that equals a rank-1
projector. Hence, for all $\ell\in[r]$ and $k\in[m]$, there exists a complex
coefficient $c_{k,\ell,\alpha}$ such that
$R_{\ell}M_{k}{|{\alpha}\rangle}=c_{k,\ell,\alpha}{|{\alpha}\rangle}$. This
implies that the operator $R_{\ell}M_{k}$ is normal and diagonal in every
basis. Hence, it must be proportional to the identity. That is,
$c_{k,\ell,\alpha}$ does not depend on $\alpha$. Therefore, for each
$k\in[m]$, $M_{k}$ is proportional to an inverse of $R_{1}$. Since inverses
are unique, $M_{k}\propto M_{k^{\prime}}$ for all $k,k^{\prime}\in[m]$. ∎

######  Proposition 5.6.4.

If $S\subseteq[n]$ is a singleton, then $\gamma_{S}\in\\{0,1\\}$.

###### Proof.

Without loss of generality, let $S=\\{1\\}$. If $\gamma_{1}>0$, then the
channel
$\mathcal{M}_{1}:=\tr_{[n]\setminus\\{1\\}}\circ\;\mathcal{U}_{\mathcal{C}}:\mathcal{B}(\mathcal{H})\rightarrow\mathcal{B}(\mathcal{H})$
satisfies the conditions in Eq. 5.4.2 for some nonzero recovery operator
$\Pi\in\mathcal{B}(\mathcal{H})$, where the code in this instance is
$\mathcal{H}$. $\mathcal{M}_{1}$ has a completely positive inverse. Since it
is also trace-preserving, then it is unitary by Lem 5.6.3. Hence,
$\gamma_{1}=1$ and
$\mathcal{C}=\mathcal{H}\otimes\mathbb{C}{|{\alpha}\rangle}$ for some
${|{\alpha}\rangle}\in\mathcal{H}^{\otimes n-1}$. ∎

We can use this proposition along with Prop. 5.6.2 to show that erasure
channels with erasure probability at least a half cannot be improved with four
uses. In particular, for an encoding into $4$ qudits where the information is
encoded into one qudit, then the optimal recovery probability is exactly
$(1-q)$. Otherwise, for $i\in[4]$, $\gamma_{i}=0$ by Prop. 5.6.4. In such a
case, the probability of recovery can be bounded from above as follows

$\displaystyle r_{4}(q)$
$\displaystyle=q^{4}(0)+q^{3}(1-q)(0)+q^{2}(1-q)^{2}(3)+q(1-q)^{3}(4)+(1-q)^{4},$
(5.6.7) $\displaystyle=(1-q)^{2}(3q^{2}+4q(1-q)+(1-q)^{2})$ (5.6.8)

where we used the fact that $\gamma_{\emptyset}=0$, the fact that
$\gamma_{i}=0$, and Prop. 5.6.2 to bound from the above the coefficient of
$q^{2}(1-q)^{2}$. For the last point, there are $3$ distinct partitions of a
set of $4$ elements into two sets of two elements each. The zeros of the
polynomial $r_{4}(q)-(1-q)$ are $0$, $\frac{1}{2}$, and $1$. It is negative
when $q$ is close to $1$. Hence, it is non-positive on $[\frac{1}{2},1]$. This
implies the following corollary.

######  Corollary 5.6.5.

For $n\leq 4$ and $q\in[\frac{1}{2},1]$, if
$\mathcal{R}\circ\mathcal{E}_{q}^{\otimes
n}\circ\mathcal{U}_{\mathcal{C}}=\mathcal{E}_{p}$, then $p\geq q$.

In order to progress further, we consider the problem for a special class of
quantum error correcting codes. We say that a code is deterministic if the
associated tuple of recovery probabilities $(\gamma_{S})_{S\subseteq[n]}$
satisfies $\gamma_{S}\in\\{0,1\\}$ for all erasure patterns
$S^{c}\subseteq[n]$. In [43], Hastings considers a slightly different
restriction. He restricted the decoding procedure to output an error flag
whenever an erasure pattern $S^{c}\subseteq[n]$ occurs where the probability
of recovery is less than 1. Restricting the encoding procedure is more natural
as the optimal decoding procedure is known for any given encoding (see Prog.
5.4.5). Moreover, the class of deterministic codes includes ubiquitously
studied codes such as stabilizer codes.

######  Proposition 5.6.6.

Let $\mathcal{C}\leq\mathcal{H}^{\otimes n}$ be a stabilizer code. If
$\gamma_{S}<1$, then $\gamma_{S}=0$.

###### Proof.

Let $G_{\mathcal{C}}$ denote the stabilizer group of the code. Since
$\gamma_{S}<1$, the code $\mathcal{C}$ is not $(\tr_{S^{c}},1)$-correcting.
This implies that there is an element of
$\text{Centraliser}(G_{\mathcal{C}})\setminus G_{\mathcal{C}}$ of the form
$\mathds{1}_{S}\otimes E_{S^{c}}$. This is a non-identity logical operator for
$\mathcal{C}$. Hence, there exist two distinct
${|{\phi}\rangle},{|{\psi}\rangle}\in\mathcal{C}$ such that
${|{\phi}\rangle}=\mathds{1}_{S}\otimes E_{S^{c}}{|{\psi}\rangle}$. This
implies

$\displaystyle\tr_{S^{c}}({|{\phi}\rangle}{\langle{\phi}|})\otimes(\frac{\mathds{1}}{d})^{\otimes
S^{c}}$ $\displaystyle\propto\int\mu_{U}\mathds{1}_{S}\otimes
U_{S}{|{\phi}\rangle}{\langle{\phi}|}\mathds{1}_{S}\otimes U_{S}^{*}$ (5.6.9)
$\displaystyle=\int\mu_{U}\mathds{1}_{S}\otimes
U_{S}E_{S}{|{\psi}\rangle}{\langle{\psi}|}\mathds{1}_{S}\otimes(U_{S}E_{S})^{*}$
(5.6.10) $\displaystyle=\>\int\mu_{U}\mathds{1}_{S}\otimes
U_{S}{|{\psi}\rangle}{\langle{\psi}|}\mathds{1}_{S}\otimes U_{S}^{*},$
(5.6.11)

where the $\mu_{U}$ is the Haar measure of the unitary group on the systems in
$S$. Therefore, $\tr_{S^{c}}\otimes(\frac{\mathds{1}}{d})^{\otimes S^{c}}$ is
not one-to-one on $\mathcal{C}$ and so $\gamma_{S}=0$. ∎

For a code $\mathcal{C}$, denote the contributing family
$\mathcal{F}_{\mathcal{C}}:=\\{S\subseteq[n]\;\big{|}\;\gamma_{S}(\mathcal{C})>0\\}$.
From Prop. 5.6.2, the family
$\mathcal{F}_{\mathcal{C},1}:=\\{S\subseteq[n]\;\big{|}\;\gamma_{S}(\mathcal{C})=1\\}$
is intersecting. Moreover, any $T\in\mathcal{F}_{\mathcal{C}}$ must intersect
with every member of $\mathcal{F}_{\mathcal{C},1}$. For a deterministic code
$\mathcal{C}$, $\mathcal{F}_{\mathcal{C}}=\mathcal{F}_{\mathcal{C},1}$. The
following two propositions are based on the observation that intersecting
families of small sets cannot have too many members. This is made precise by
the Erdös-Ko-Rado theorem [31] for intersecting families. It says that an
intersecting family of $\ell$-sets, where $\ell\leq\lfloor\frac{n}{2}\rfloor$,
has at most $\binom{n-1}{\ell-1}$ members.

######  Proposition 5.6.7.

Let $\mathcal{C}\leq\mathcal{H}^{\otimes n}$ be a deterministic code. For
$\ell\in[n]$, consider the channel

$\displaystyle\mathcal{N}_{\ell}(\cdot)=\frac{1}{\binom{n}{\ell}}\sum_{S\in\binom{[n]}{\ell}}\tr_{S^{c}}(\cdot)\otimes{|{e}\rangle}{\langle{e}|}^{\otimes
S^{c}}.$ (5.6.12)

If $\ell\leq\lfloor\frac{n}{2}\rfloor$ and $\mathcal{C}$ is
$(\mathcal{N}_{\ell},t)$-correcting, then $t\leq\frac{\ell}{n}$.

###### Proof.

Since $\mathcal{F}_{\mathcal{C}}$ is intersecting and
$\ell\leq\lfloor\frac{n}{2}\rfloor$,
$\frac{1}{\binom{n}{\ell}}\sum_{S\in\binom{[n]}{\ell}}\gamma_{S}\leq\frac{1}{\binom{n}{\ell}}\binom{n-1}{\ell-1}=\frac{\ell}{n}.$
∎

By appealing to a typicality argument, we can lift this result to show a
similar upper bound for $\mathcal{E}_{q}^{\otimes n}$.

######  Theorem 5.6.8.

Let $(\mathcal{C}_{n})_{n\in\mathbb{N}}$ be a sequence of deterministic codes.
If $q\in(\frac{1}{2},1)$, then the asymptotic recovery probability is bounded
from above as follows

$\displaystyle\lim_{n\rightarrow\infty}\sum_{S\subseteq[n]}q^{n-|S|}(1-q)^{|S|}\gamma_{S}(\mathcal{C}_{n})\leq(1-q).$
(5.6.13)

###### Proof.

Set $\delta=\frac{1}{2}(\frac{1}{2}-(1-q))$ and consider the intersecting
families

$\displaystyle\mathcal{F}_{\mathcal{C}_{n}}^{(\ell)}=\mathcal{F}_{\mathcal{C}_{n}}\cap\binom{[n]}{\ell},$
(5.6.14)

where $\ell\in T^{(n)}_{1-q,\delta}$ (see Def 5.3.1). Denote the atypical
summand of the recovery probability by $\varepsilon(n)$ and consider

$\displaystyle\sum_{S\subseteq[n]}q^{n-|S|}(1-q)^{|S|}\gamma_{S}$
$\displaystyle=\sum_{\ell\in
T^{(n)}_{1-q,\delta}}\sum_{|S|=\ell}q^{n-|S|}(1-q)^{|S|}\gamma_{S}+\varepsilon(n)$
(5.6.15) $\displaystyle=\sum_{\ell\in
T^{(n)}_{1-q,\delta}}\sum_{S\in\mathcal{F}_{\mathcal{C}_{n}}^{(\ell)}}q^{n-|S|}(1-q)^{|S|}+\varepsilon(n)$
(5.6.16) $\displaystyle\leq\sum_{\ell\in
T^{(n)}_{1-q,\delta}}q^{n-\ell}(1-q)^{\ell}\binom{n-1}{\ell-1}+\varepsilon(n)$
(5.6.17) $\displaystyle\leq(1-q)+\varepsilon(n).$ (5.6.18)

The claim follows from the fact that
$\lim_{n\rightarrow\infty}\varepsilon(n)=0$. ∎

###  5.7 Concluding remarks

We have provided a systematic study of exact simulation of quantum erasure
channels. We showed that it is closely related to the notion of probabilistic
recovery of quantum information. We showed that the best erasure channel
simulable by a given resource channel and a given code can be ascertained by
solving a simple semi-definite program Prog. 5.4.5. We showed that Conj. 5.3.5
holds in the case where $n\leq 4$ and the case where the encoding channel is
an isometric encoding into some deterministic code.

We speculate about a possible path towards a resolution of Conj. 5.3.5.
Suppose that for a code $\mathcal{C}\leq\mathcal{H}^{\otimes n}$ it holds that
$\gamma_{S}+\gamma_{S^{c}}=1$ for some $S\subseteq[n]$. If both $\gamma_{S}$
and $\gamma_{S^{c}}$ are nonzero, then for ${|{c}\rangle}\in\mathcal{C}$, it
holds that ${|{c}\rangle}={|{c_{S}}\rangle}+{|{c_{S^{c}}}\rangle}$, where
${|{c_{S}}\rangle}$ is contained in the support of $\Pi_{S}$ and
${|{c_{S^{c}}}\rangle}$ is contained in the support of $\Pi_{S^{c}}$. The
following is a simple example of such an encoding.

$\displaystyle\mathcal{H}\ni{|{\alpha}\rangle}\mapsto\frac{1}{\sqrt{2}}({|{\alpha}\rangle}\otimes{|{0}\rangle}\otimes{|{0}\rangle}\otimes{|{0}\rangle}+{|{0}\rangle}\otimes{|{1}\rangle}\otimes{|{\alpha}\rangle}\otimes{|{1}\rangle}),$
(5.7.1)

where the second and fourth qudit carry the classical information about where
the quantum information was encoded. The probability of recovery is zero if
both of these qubits are erased. In a code that is not deterministic,
classical information is encoded along with every erasure pattern where
recovery is not deterministic. In the example above, there’s a whole bit
encoded along with the quantum information. Perhaps there is not enough room
for both the quantum and the classical information if there are too many such
erasure patterns. Even more simply, can we bound from above the cardinality of
the set $\\{S\in\binom{[n]}{k}\;\big{|}\;\gamma_{S}>0\\}$ for
$k\leq\lfloor\frac{n}{2}\rfloor$ by appealing to a packing argument? It is
clear from the example above that it can exceed $\binom{n-1}{k-1}$. Still, an
upper bound might come with some insights that would aid in proving Conj.
5.3.5.

## References

  * [1] Antonio Acín and Lluis Masanes.  Certified randomness in quantum physics.  Nature, 540(7632):213–219, Dec 2016.
  * [2] Mohammad A. Alhejji and Graeme Smith.  A tight uniform continuity bound for equivocation.  In 2020 IEEE International Symposium on Information Theory (ISIT), pages 2270–2274, 2020.
  * [3] R Alicki and M Fannes.  Continuity of quantum conditional information.  Journal of Physics A: Mathematical and General, 37(5):L55–L57, jan 2004.
  * [4] T. Ando.  Majorizations and inequalities in matrix theory.  Linear Algebra and its Applications, 199:17–67, 1994.  Special Issue Honoring Ingram Olkin.
  * [5] S. Arimoto.  An algorithm for computing the capacity of arbitrary discrete memoryless channels.  IEEE Transactions on Information Theory, 18(1):14–20, 1972.
  * [6] S. Arimoto.  Information measures and capacity of order $\alpha$ for discrete memoryless channels.  Topics in Information Theory, 1977.
  * [7] Barry C. Arnold.  Inequality and majorization : Robin Hood in unexpected places.  Calcutta Statistical Association Bulletin, 63(1-4):71–80, 2011\.
  * [8] Guillaume Aubrun and Ion Nechita.  The multiplicative property characterizes $\ell_{p}$ and $l_{p}$ norms.  Confluentes Mathematici, 03(04):637–647, dec 2011.
  * [9] Koenraad M R Audenaert.  A sharp continuity estimate for the von Neumann entropy.  Journal of Physics A: Mathematical and Theoretical, 40(28):8127–8136, jun 2007.
  * [10] Simeon Ball, Aina Centelles, and Felix Huber.  Quantum error-correcting codes and their geometries.  Ann. Institut Henri Poincaré D, February 2023.
  * [11] H. Barnum, E. Knill, and M.A. Nielsen.  On quantum fidelities and channel capacities.  IEEE Transactions on Information Theory, 46(4):1317–1329, 2000\.
  * [12] Howard Barnum, M. A. Nielsen, and Benjamin Schumacher.  Information transmission through a noisy quantum channel.  Phys. Rev. A, 57:4153–4175, Jun 1998.
  * [13] Charles H. Bennett, Herbert J. Bernstein, Sandu Popescu, and Benjamin Schumacher.  Concentrating partial entanglement by local operations.  Phys. Rev. A, 53:2046–2052, Apr 1996.
  * [14] Charles H. Bennett, David P. DiVincenzo, and John A. Smolin.  Capacities of quantum erasure channels.  Phys. Rev. Lett., 78:3217–3220, Apr 1997.
  * [15] Rajendra Bhatia.  Matrix Analysis, volume 169.  Springer, 1997.
  * [16] R. Blahut.  Computation of channel capacity and rate-distortion functions.  IEEE Transactions on Information Theory, 18(4):460–473, 1972.
  * [17] James V. Bondar.  Schur majorization inequalities for symmetrized sums with applications to tensor products.  Linear Algebra and its Applications, 360:1–13, 2003.
  * [18] Kenneth R. Brown, John Chiaverini, Jeremy M. Sage, and Hartmut Häffner.  Materials challenges for trapped-ion quantum computers.  Nature Reviews Materials, 6(10):892–905, Oct 2021.
  * [19] David Carlson.  What are Schur complements, anyway?  Linear Algebra and its Applications, 74:257–275, 1986.
  * [20] Sarah S Chehade and Anna Vershynina.  Quantum entropies.  Scholarpedia, 14:53131, 2019.
  * [21] Man-Duen Choi.  Completely positive linear maps on complex matrices.  Linear Algebra and its Applications, 10(3):285–290, 1975.
  * [22] Matthias Christandl and Andreas Winter.  “squashed entanglement”: An additive entanglement measure.  Journal of Mathematical Physics, 45(3):829–840, 2004.
  * [23] Thomas M. Cover and Joy A. Thomas.  Elements of Information Theory (Wiley Series in Telecommunications and Signal Processing).  Wiley-Interscience, New York, NY, USA, 2006.
  * [24] Toby Cubitt, David Elkouss, William Matthews, Maris Ozols, David Pérez-García, and Sergii Strelchuk.  Unbounded number of channel uses may be required to detect quantum capacity.  Nature Communications, 6(1), Mar 2015.
  * [25] Toby S. Cubitt, Mary Beth Ruskai, and Graeme Smith.  The structure of degradable quantum channels.  Journal of Mathematical Physics, 49(10):102104, 2008.
  * [26] Peter W. Day.  Rearrangement inequalities.  Canadian Journal of Mathematics, 24(5):930–943, 1972.
  * [27] I. Devetak.  The private classical capacity and quantum capacity of a quantum channel.  IEEE Transactions on Information Theory, 51(1):44–55, 2005.
  * [28] Igor Devetak, Aram W. Harrow, and Andreas J. Winter.  A resource framework for quantum shannon theory.  IEEE Transactions on Information Theory, 54(10):4587–4618, 2008\.
  * [29] Mario Diaz, Peter Kairouz, Jiachun Liao, and Lalitha Sankar.  Theoretical guarantees for model auditing with finite adversaries, 2019\.
  * [30] Peter Elias.  The noisy channel coding theorem for erasure channels.  The American Mathematical Monthly, 81(8):853–862, 1974.
  * [31] P. Erdös, C. Ko, and R. Rado.  Intersection theorems for systems of finite sets.  The Quarterly Journal of Mathematics, 12(1):313–320, 01 1961.
  * [32] Ky Fan.  On a theorem of Weyl concerning eigenvalues of linear transformations i*.  Proceedings of the National Academy of Sciences, 35(11):652–655, 1949.
  * [33] M. Fannes.  A continuity property of the entropy density for spin lattice systems.  Comm. Math. Phys., 31(4):291–294, 1973.
  * [34] Andrew R. Francis and Henry P. Wynn.  Subgroup majorization.  Linear Algebra and its Applications, 444:53 – 66, 2014.
  * [35] C. A. Fuchs and J. van de Graaf.  Cryptographic distinguishability measures for quantum-mechanical states.  IEEE Transactions on Information Theory, 45(4):1216–1227, May 1999\.
  * [36] A. Giovagnoli and H.P. Wynn.  G-majorization with applications to matrix orderings.  Linear Algebra and its Applications, 67:111 – 135, 1985.
  * [37] Daniel Gottesman.  Stabilizer Codes and Quantum Error Correction.  PhD thesis, California Institute of Technology, Pasadena, California, 1997\.
  * [38] M. Grassl, Th. Beth, and T. Pellizzari.  Codes for the quantum erasure channel.  Phys. Rev. A, 56:33–38, Jul 1997.
  * [39] Eric P. Hanson and Nilanjana Datta.  Tight uniform continuity bound for a family of entropies, 2017.
  * [40] Eric P. Hanson and Nilanjana Datta.  Maximum and minimum entropy states yielding local continuity bounds.  Journal of Mathematical Physics, 59(4):042204, 2018.
  * [41] G.H. Hardy, J.E. Littlewood, and G. Pólya.  Some simple inequalities satisfied by convex functions.  Messenger Math., 58:145–152, 1929.
  * [42] M. B. Hastings.  Superadditivity of communication capacity using entangled inputs.  Nature Physics, 5(4):255–257, Apr 2009.
  * [43] M. B. Hastings.  Notes on some questions in mathematical physics and quantum information, 2014.
  * [44] S. Ho and R. W. Yeung.  The interplay between entropy and variational distance.  IEEE Transactions on Information Theory, 56(12):5906–5929, Dec 2010\.
  * [45] Michael G. Jabbour and Nilanjana Datta.  A tight uniform continuity bound for the arimoto-rényi conditional entropy and its extension to classical-quantum states.  IEEE Transactions on Information Theory, 68(4):2169–2181, 2022\.
  * [46] A. Jamiołkowski.  Linear transformations which preserve trace and positive semidefiniteness of operators.  Reports on Mathematical Physics, 3(4):275–278, 1972.
  * [47] Camille Jordan.  Essai sur la géométrie à $n$ dimensions.  Bulletin de la Société Mathématique de France, 3:103–174, 1875.
  * [48] C. King.  The capacity of the quantum depolarizing channel.  IEEE Transactions on Information Theory, 49(1):221–229, 2003.
  * [49] Emanuel Knill and Raymond Laflamme.  Theory of quantum error-correcting codes.  Phys. Rev. A, 55:900–911, Feb 1997.
  * [50] Ryszard Kukulski, Łukasz Pawela, and Zbigniew Puchała.  On the probabilistic quantum error correction, 2022.
  * [51] Felix Leditzky, Debbie Leung, Vikesh Siddhu, Graeme Smith, and John A. Smolin.  Generic nonadditivity of quantum capacity in simple channels, 2022.
  * [52] Felix Leditzky, Debbie Leung, Vikesh Siddhu, Graeme Smith, and John A. Smolin.  The platypus of the quantum channel zoo, 2022.
  * [53] Debbie Leung and Graeme Smith.  Continuity of quantum channel capacities.  Communications in Mathematical Physics, 292(1):201–215, Nov 2009\.
  * [54] Daniel Lidar and Todd Brun, editors.  Quantum Error Correction.  Cambridge University Press, 2013.
  * [55] A. Mari, V. Giovannetti, and A. S. Holevo.  Quantum state majorization at the output of bosonic gaussian channels.  Nature Communications, 5(1):3826, May 2014.
  * [56] Albert W. Marshall, Ingram Olkin, and Barry C. Arnold.  Inequalities: Theory of Majorization and its Applications, volume 143.  Springer, second edition, 2011.
  * [57] Ashwin Nayak and Pranab Sen.  Invertible quantum operations and perfect encryption of quantum states, 2006.
  * [58] M. A. Nielsen.  Conditions for a class of entanglement transformations.  Phys. Rev. Lett., 83:436–439, Jul 1999.
  * [59] M. A. Nielsen and J. Kempe.  Separable states are more disordered globally than locally.  Phys. Rev. Lett., 86:5184–5187, May 2001.
  * [60] Michael A. Nielsen and Isaac L. Chuang.  Quantum Computation and Quantum Information.  Cambridge University Press, 2000.
  * [61] Iosif Pinelis.  Entropy and total variation distance (answer).  MathOverflow.  visited on 2019-08-03.
  * [62] E.M. Rains.  Quantum weight enumerators.  IEEE Transactions on Information Theory, 44(4):1388–1394, 1998\.
  * [63] A Rényi.  On measures of information and entropy.  In Proceedings of the 4th Berkeley Symposium on Mathematics, Statistics and Probability, volume I of Lecture Notes in Computer Science, pages 547–561, Berkeley and Los Angeles, USA, 1960. University of California Press.
  * [64] I. Sason.  Entropy bounds for discrete random variables via maximal coupling.  IEEE Transactions on Information Theory, 59(11):7118–7131, Nov 2013\.
  * [65] Valerio Scarani, Helle Bechmann-Pasquinucci, Nicolas J. Cerf, Miloslav Dušek, Norbert Lütkenhaus, and Momtchil Peev.  The security of practical quantum key distribution.  Rev. Mod. Phys., 81:1301–1350, Sep 2009.
  * [66] C. Schilling.  The quantum marginal problem.  In Mathematical Results in Quantum Mechanics. WORLD SCIENTIFIC, November 2014.
  * [67] Benjamin Schumacher.  Quantum coding.  Phys. Rev. A, 51:2738–2747, Apr 1995.
  * [68] Benjamin Schumacher and Michael D. Westmoreland.  Sending classical information via noisy quantum channels.  Phys. Rev. A, 56:131–138, Jul 1997.
  * [69] Claude Elwood Shannon.  A mathematical theory of communication.  The Bell System Technical Journal, 27:379–423, 1948.
  * [70] M. E. Shirokov.  Tight uniform continuity bounds for the quantum conditional mutual information, for the holevo quantity, and for capacities of quantum channels.  Journal of Mathematical Physics, 58(10):102202, 2017.
  * [71] M. E. Shirokov.  Continuity of characteristics of composite quantum systems, 2022.
  * [72] Peter W. Shor.  Scheme for reducing decoherence in quantum computer memory.  Phys. Rev. A, 52:R2493–R2496, Oct 1995.
  * [73] Peter W. Shor.  Equivalence of additivity questions in quantum information theory.  Communications in Mathematical Physics, 246(3):453–472, Apr 2004\.
  * [74] P.W. Shor.  Algorithms for quantum computation: discrete logarithms and factoring.  In Proceedings 35th Annual Symposium on Foundations of Computer Science, pages 124–134, 1994.
  * [75] Graeme Smith.  Quantum channel capacities.  In 2010 IEEE Information Theory Workshop, pages 1–5, 2010.
  * [76] A. M. Steane.  Error correcting codes in quantum theory.  Phys. Rev. Lett., 77:793–797, Jul 1996.
  * [77] A.G.M. Steerneman.  G-majorization, group-induced cone orderings, and reflection groups.  Linear Algebra and its Applications, 127:107 – 119, 1990.
  * [78] W Forrest Stinespring.  Positive functions on c*-algebras.  Proceedings of the American Mathematical Society, 6(2):211–216, 1955.
  * [79] D. Sutter, V. B. Scholz, A. Winter, and R. Renner.  Approximate degradable quantum channels.  IEEE Transactions on Information Theory, 63(12):7832–7844, Dec 2017\.
  * [80] Marco Tomamichel.  Quantum Information Processing with Finite Resources: Mathematical Foundations.  Springer Publishing Company, Incorporated, 1st edition, 2015.
  * [81] Constantino Tsallis.  Possible Generalization of Boltzmann-Gibbs Statistics.  J. Statist. Phys., 52:479–487, 1988.
  * [82] Mahathi Vempati, Saumya Shah, Nirman Ganguly, and Indranil Chakrabarty.  A-unital operations and quantum conditional entropy.  Quantum, 6:641, February 2022.
  * [83] John Watrous.  The Theory of Quantum Information.  Cambridge University Press, 2018.
  * [84] Mark M. Wilde.  Quantum Information Theory.  Cambridge University Press, 2013.
  * [85] Mark M. Wilde.  Optimal uniform continuity bound for conditional entropy of classical–quantum states.  Quantum Information Processing, 19(2):61, Jan 2020.
  * [86] Mark M. Wilde and Andreas Winter.  Strong converse for the quantum capacity of the erasure channel for almost all codes.  Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH, Wadern/Saarbruecken, Germany, 2014.
  * [87] Andreas Winter.  Tight uniform continuity bounds for quantum entropies: Conditional entropy, relative entropy distance and energy constraints.  Communications in Mathematical Physics, 347(1):291–313, Oct 2016\.
  * [88] W. K. Wootters and W. H. Zurek.  A single quantum cannot be cloned.  Nature, 299(5886):802–803, October 1982.
  * [89] Raymond W. Yeung.  A First Course in Information Theory (Information Technology: Transmission, Processing and Storage).  Springer-Verlag, Berlin, Heidelberg, 2006.
  * [90] Z. Zhang.  Estimating mutual information via Kolmogorov distance.  IEEE Transactions on Information Theory, 53(9):3280–3282, Sep. 2007\.