Classical Capacity

In quantum information theory, the classical capacity of a quantum channel is the maximum rate at which classical data can be sent over it error-free in the limit of many uses of the channel. Holevo, Schumacher, and Westmoreland proved the following least upper bound on the classical capacity of any quantum channel $\mathcal$:

:$\chi(\mathcal) = \max_ I(X;B)_$

where $\rho^$ is a classical-quantum state of the following form:
:$\rho^ = \sum_x p_X(x) \vert x \rangle \langle x \vert^X \otimes \rho_x^A ,$
$p_X(x)$ is a probability distribution, and each $\rho_x^A$ is a density operator that can be input to the channel $\mathcal$.

Achievability using sequential decoding

We briefly review the HSW coding theorem (the
statement of the achievability of the Holevo information rate $I(X;B)$ for
communicating classical data over a quantum channel). We first review the
minimal amount of quantum mechanics needed for the theorem. We then cover
quantum typicality, and finally we prove the theorem using a recent sequential
decoding technique.

Review of quantum mechanics

In order to prove the HSW coding theorem, we really just need a few basic
things from quantum mechanics. First, a quantum state is a unit trace,
positive operator known as a density operator. Usually, we denote it
by $\rho$, $\sigma$, $\omega$, etc. The simplest model for a quantum channel
is known as a classical-quantum channel:

$x\mapsto \rho_.$

The meaning of the above notation is that inputting the classical letter $x$
at the transmitting end leads to a quantum state $\rho_$ at the receiving
end. It is the task of the receiver to perform a measurement to determine the
input of the sender. If it is true that the states $\rho_$ are perfectly
distinguishable from one another (i.e., if they have orthogonal supports such
that $\mathrm\,\left\ =0$ for $x\neq x^$), then the channel is a noiseless channel. We are interested in situations
for which this is not the case. If it is true that the states $\rho_$ all
commute with one another, then this is effectively identical to the situation
for a classical channel, so we are also not interested in these situations.
So, the situation in which we are interested is that in which the states
$\rho_$ have overlapping support and are non-commutative.

The most general way to describe a quantum measurement is with a
positive operator-valued measure (POVM). We usually denote the elements of a POVM as
$\left\ _$. These operators should satisfy
positivity and completeness in order to form a valid POVM:
:$\Lambda_ \geq0\ \ \ \ \forall m$
:$\sum_\Lambda_ =I.$
The probabilistic interpretation of quantum mechanics states that if someone
measures a quantum state $\rho$ using a measurement device corresponding to
the POVM $\left\$, then the probability $p\left( m\right)$ for obtaining outcome $m$ is equal to
:$p\left( m\right) =\text\left\ ,$
and the post-measurement state is
:$\rho_^=\frac\sqrt\rho \sqrt,$
if the person measuring obtains outcome $m$. These rules are sufficient for us
to consider classical communication schemes over cq channels.

Quantum typicality

The reader can find a good review of this topic in the article about the typical subspace.

Gentle operator lemma

The following lemma is important for our proofs. It
demonstrates that a measurement that succeeds with high probability on average
does not disturb the state too much on average:

Lemma: interGiven an
ensemble $\left\$ with expected
density operator $\rho\equiv\sum_p_\left( x\right) \rho_$, suppose
that an operator $\Lambda$ such that $I\geq\Lambda\geq0$ succeeds with high
probability on the state $\rho$:

$\text\left\ \geq1-\epsilon.$

Then the subnormalized state $\sqrt\rho_\sqrt$ is close
in expected trace distance to the original state $\rho_$:

$\mathbb_\left\ \leq2\sqrt.$

(Note that $\left\Vert A\right\Vert _$ is the nuclear norm of the operator
$A$ so that $\left\Vert A\right\Vert _\equiv$Tr$\left\$.)

The following inequality is useful for us as well. It holds for any operators
$\rho$, $\sigma$, $\Lambda$ such that $0\leq\rho,\sigma,\Lambda\leq I$:

The quantum information-theoretic interpretation of the above inequality is
that the probability of obtaining outcome $\Lambda$ from a quantum measurement
acting on the state $\rho$ is upper bounded by the probability of obtaining
outcome $\Lambda$ on the state $\sigma$ summed with the distinguishability of
the two states $\rho$ and $\sigma$.

Non-commutative union bound

Lemma: en's boundThe following bound
holds for a subnormalized state $\sigma$ such that $0\leq\sigma$ and
$Tr\left\ \leq1$ with $\Pi_$, ... , $\Pi_$ being
projectors:
$\text\left\ -\text\left\ \leq2\sqrt,$

We can think of Sen's bound as a "non-commutative union
bound" because it is analogous to the following union bound
from probability theory:

$\Pr\left\ =\Pr\left\ \leq\sum_^ \Pr\left\ ,$

where $A_, \ldots, A_$ are events. The analogous bound for projector
logic would be
:$\text\left\ \leq\sum_^\text\left\ ,$
if we think of $\Pi_\cdots\Pi_$ as a projector onto the intersection of
subspaces. Though, the above bound only holds if the projectors $\Pi_$,
..., $\Pi_$ are commuting (choosing $\Pi_=\left\vert +\right\rangle \left\langle +\right\vert$, $\Pi_=\left\vert 0\right\rangle \left\langle 0\right\vert$, and $\rho=\left\vert 0\right\rangle \left\langle 0\right\vert$ gives a counterexample). If the projectors are non-commuting, then Sen's
bound is the next best thing and suffices for our purposes here.

HSW theorem with the non-commutative union bound

We now prove the HSW theorem with Sen's non-commutative union bound. We
divide up the proof into a few parts: codebook generation, POVM construction,
and error analysis.

Codebook Generation. We first describe how Alice and Bob agree on a
random choice of code. They have the channel $x\rightarrow\rho_$ and a
distribution $p_\left( x\right)$. They choose $M$ classical sequences
$x^$ according to the IID\ distribution $p_\left( x^\right)$.
After selecting them, they label them with indices as $\left\ _$. This leads to the following
quantum codewords:

$\rho_=\rho_\otimes \cdots\otimes\rho_.$

The quantum codebook is then $\left\$. The average state of the codebook is then

where $\rho=\sum_p_\left( x\right) \rho_$.

POVM Construction . Sens' bound from the above lemma
suggests a method for Bob to decode a state that Alice transmits. Bob should
first ask "Is the received state in the average typical
subspace?" He can do this operationally by performing a
typical subspace measurement corresponding to $\left\$. Next, he asks in sequential order,
"Is the received codeword in the $m^$
conditionally typical subspace?" This is in some sense
equivalent to the question, "Is the received codeword the
$m^$ transmitted codeword?" He can ask these
questions operationally by performing the measurements corresponding to the
conditionally typical projectors $\left\$.

Why should this sequential decoding scheme work well? The reason is that the
transmitted codeword lies in the typical subspace on average:
:$\mathbb_\left\ =\text\left\$
:$=\text\left\$
:$\geq1-\epsilon,$
where the inequality follows from (\ref). Also, the
projectors $\Pi_$
are "good detectors" for the states $\rho_$ (on average) because the following condition holds from conditional quantum
typicality:

$\mathbb_\left\ \geq1-\epsilon.$

Error Analysis. The probability of detecting the $m^$
codeword correctly under our sequential decoding scheme is equal to

$\text\left\ ,$

where we make the abbreviation $\hat\equiv I-\Pi$. (Observe that we
project into the average typical subspace just once.) Thus, the probability of
an incorrect detection for the $m^$ codeword is given by

$1-\text\left\ ,$

and the average error probability of this scheme is equal to

$1-\frac\sum_\text\left\ .$

Instead of analyzing the average error probability, we analyze the expectation
of the average error probability, where the expectation is with respect to the
random choice of code:

Our first step is to apply Sen's bound to the above quantity. But before doing
so, we should rewrite the above expression just slightly, by observing that
:$1 =\mathbb_\left\$
:$=\mathbb_\left\$
:$=\mathbb_\left\ +\frac\sum_\text\left\$
:$=\mathbb_\left\ +\text\left\$
:$\leq\mathbb_\left\ +\epsilon$
Substituting into () (and forgetting about the small
$\epsilon$ term for now) gives an upper bound of
:$\mathbb_\left\$
:$-\mathbb_\left\ .$
We then apply Sen's bound to this expression with $\sigma=\Pi_^\rho_\Pi_^$ and the sequential
projectors as $\Pi_$, $\hat _$, ..., $\hat_$. This gives the upper bound
$\mathbb_\left\ .$
Due to concavity of the square root, we can bound this expression from above
by
:
2\left \mathbb_\left\ \right ^
: \leq2\left \mathbb_\left\ \right ^,

where the second bound follows by summing over all of the codewords not equal
to the $m^$ codeword (this sum can only be larger).

We now focus exclusively on showing that the term inside the square root can
be made small. Consider the first term:
:$\mathbb_\left\$
:$\leq\mathbb_\left\$
:$\leq\epsilon+2\sqrt.$
where the first inequality follows from () and the
second inequality follows from the gentle operator lemma and the
properties of unconditional and conditional typicality. Consider now the
second term and the following chain of inequalities:
:$\sum_\mathbb_\left\$
:$=\sum_\text\left\$
:$=\sum_\text\left\$
:$\leq\sum_2^\ \text\left\$
The first equality follows because the codewords $X^\left( m\right)$ and
$X^\left( i\right)$ are independent since they are different. The second
equality follows from (). The first inequality follows from
(\ref). Continuing, we have
:$\leq\sum_2^\ \mathbb_\left\$
:$\leq\sum_2^\ 2^$
:$=\sum_2^$
:$\leq M\ 2^.$
The first inequality follows from $\Pi_^\leq I$ and exchanging
the trace with the expectation. The second inequality follows from
(\ref). The next two are straightforward.

Putting everything together, we get our final bound on the expectation of the
average error probability:
:$1-\mathbb_\left\$
:\leq\epsilon+2\left \left( \epsilon+2\sqrt\right)
+M\ 2^\right ^.

Thus, as long as we choose $M=2^$, there exists a code with vanishing error probability.

See also

* Entanglement-assisted classical capacity
* Quantum capacity
* Quantum information theory
* Typical subspace

References

*.
*.
*
*.
*.

{{Quantum computing

Quantum information theory
Limits of computation