Classical capacity

Template:Short description 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 $𝒩$:

$\chi (𝒩)=\underset{{\rho }^{XA}}{\max }I(X;B{)}_{𝒩(\rho )}$

where ${\rho }^{XA}$ is a classical-quantum state of the following form:

${\rho }^{XA}=\sum _x{p}_X(x)|x⟩⟨x{|}^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 $𝒩$.

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 }_x.$

The meaning of the above notation is that inputting the classical letter $x$ at the transmitting end leads to a quantum state ${\rho }_x$ 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 }_x$ are perfectly distinguishable from one another (i.e., if they have orthogonal supports such that $\mathrm{T}\mathrm{r}\left\{{\rho }_x{\rho }_{x^{\prime }}\right\}=0$ for $x\ne x^{\prime }$), 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 }_x$ 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 }_x$ 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\{{\mathrm{\Lambda }}_m\right\}}_m$. These operators should satisfy positivity and completeness in order to form a valid POVM:

${\mathrm{\Lambda }}_m\ge 0\mathrm{\forall }m$

$\sum _m{\mathrm{\Lambda }}_m=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\{{\mathrm{\Lambda }}_m\right\}$, then the probability $p\left(m\right)$ for obtaining outcome $m$ is equal to

$p\left(m\right)=\text{Tr}\left\{{\mathrm{\Lambda }}_m\rho \right\},$

and the post-measurement state is

${\rho }_m^{\prime }=\frac{1}{p\left(m\right)}\sqrt{{\mathrm{\Lambda }}_m}\rho \sqrt{{\mathrm{\Lambda }}_m},$

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: [Winter] Given an ensemble $\{p_X\left(x\right),{\rho }_x\}$ with expected density operator $\rho \equiv \sum _x{p}_X\left(x\right){\rho }_x$, suppose that an operator $\mathrm{\Lambda }$ such that $I\ge \mathrm{\Lambda }\ge 0$ succeeds with high probability on the state $\rho$:

$\text{Tr}\left\{\mathrm{\Lambda }\rho \right\}\ge 1-ϵ.$

Then the subnormalized state $\sqrt{\mathrm{\Lambda }}{\rho }_x\sqrt{\mathrm{\Lambda }}$ is close in expected trace distance to the original state ${\rho }_x$:

${𝔼}_X\left\{{\Vert \sqrt{\mathrm{\Lambda }}{\rho }_X\sqrt{\mathrm{\Lambda }}-{\rho }_X\Vert }_1\right\}\le 2\sqrt{ϵ}.$

(Note that ${\Vert A\Vert }_1$ is the nuclear norm of the operator $A$ so that ${\Vert A\Vert }_1\equiv$Tr$\left\{\sqrt{A^{†}A}\right\}$.)

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

Template:NumBlk

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

Non-commutative union bound

Lemma: [Sen's bound] The following bound holds for a subnormalized state $\sigma$ such that $0\le \sigma$ and $Tr\left\{\sigma \right\}\le 1$ with ${\mathrm{\Pi }}_1$, ... , ${\mathrm{\Pi }}_N$ being projectors: $\text{Tr}\left\{\sigma \right\}-\text{Tr}\{{\mathrm{\Pi }}_N\cdots {\mathrm{\Pi }}_1\sigma {\mathrm{\Pi }}_1\cdots {\mathrm{\Pi }}_N\}\le 2\sqrt{\sum _{i=1}^N\text{Tr}\left\{(I-{\mathrm{\Pi }}_i)\sigma \right\}},$

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:

$\mathrm{Pr}\left\{{(A_1\cap \cdots \cap A_N)}^c\right\}=\mathrm{Pr}\{A_1^c\cup \cdots \cup A_N^c\}\le \sum _{i=1}^N\mathrm{Pr}\left\{A_i^c\right\},$

where $A_1,\dots ,A_N$ are events. The analogous bound for projector logic would be

$\text{Tr}\left\{(I-{\mathrm{\Pi }}_1\cdots {\mathrm{\Pi }}_N\cdots {\mathrm{\Pi }}_1)\rho \right\}\le \sum _{i=1}^N\text{Tr}\left\{(I-{\mathrm{\Pi }}_i)\rho \right\},$

if we think of ${\mathrm{\Pi }}_1\cdots {\mathrm{\Pi }}_N$ as a projector onto the intersection of subspaces. Though, the above bound only holds if the projectors ${\mathrm{\Pi }}_1$, ..., ${\mathrm{\Pi }}_N$ are commuting (choosing ${\mathrm{\Pi }}_1=|+⟩⟨+|$, ${\mathrm{\Pi }}_2=|0⟩⟨0|$, and $\rho =|0⟩⟨0|$ 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\to {\rho }_x$ and a distribution $p_X\left(x\right)$. They choose $M$ classical sequences $x^n$ according to the IID\ distribution $p_{X^n}\left(x^n\right)$. After selecting them, they label them with indices as ${\left\{x^n\left(m\right)\right\}}_{m\in \left[M\right]}$. This leads to the following quantum codewords:

${\rho }_{x^n\left(m\right)}={\rho }_{x_1\left(m\right)}\otimes \cdots \otimes {\rho }_{x_n\left(m\right)}.$

The quantum codebook is then $\left\{{\rho }_{x^n\left(m\right)}\right\}$. The average state of the codebook is then

Template:NumBlk

where $\rho =\sum _x{p}_X\left(x\right){\rho }_x$.

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 $\{{\mathrm{\Pi }}_{\rho ,\delta }^n,I-{\mathrm{\Pi }}_{\rho ,\delta }^n\}$. Next, he asks in sequential order, "Is the received codeword in the $m^{\text{th}}$ conditionally typical subspace?" This is in some sense equivalent to the question, "Is the received codeword the $m^{\text{th}}$ transmitted codeword?" He can ask these questions operationally by performing the measurements corresponding to the conditionally typical projectors $\{{\mathrm{\Pi }}_{{\rho }_{x^n\left(m\right)},\delta },I-{\mathrm{\Pi }}_{{\rho }_{x^n\left(m\right)},\delta }\}$.

Why should this sequential decoding scheme work well? The reason is that the transmitted codeword lies in the typical subspace on average:

${𝔼}_{X^n}\left\{\text{Tr}\left\{{\mathrm{\Pi }}_{\rho ,\delta }{\rho }_{X^n}\right\}\right\}=\text{Tr}\left\{{\mathrm{\Pi }}_{\rho ,\delta }{𝔼}_{X^n}\left\{{\rho }_{X^n}\right\}\right\}$

$=\text{Tr}\left\{{\mathrm{\Pi }}_{\rho ,\delta }{\rho }^{\otimes n}\right\}$

$\ge 1-ϵ,$

where the inequality follows from (\ref{eq:1st-typ-prop}). Also, the projectors ${\mathrm{\Pi }}_{{\rho }_{x^n\left(m\right)},\delta }$ are "good detectors" for the states ${\rho }_{x^n\left(m\right)}$ (on average) because the following condition holds from conditional quantum typicality:

${𝔼}_{X^n}\left\{\text{Tr}\left\{{\mathrm{\Pi }}_{{\rho }_{X^n},\delta }{\rho }_{X^n}\right\}\right\}\ge 1-ϵ.$

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

$\text{Tr}\{{\mathrm{\Pi }}_{{\rho }_{X^n\left(m\right)},\delta }{\hat{\mathrm{\Pi }}}_{{\rho }_{X^n(m-1)},\delta }\cdots {\hat{\mathrm{\Pi }}}_{{\rho }_{X^n\left(1\right)},\delta }{\mathrm{\Pi }}_{\rho ,\delta }^n{\rho }_{x^n\left(m\right)}{\mathrm{\Pi }}_{\rho ,\delta }^n{\hat{\mathrm{\Pi }}}_{{\rho }_{X^n\left(1\right)},\delta }\cdots {\hat{\mathrm{\Pi }}}_{{\rho }_{X^n(m-1)},\delta }{\mathrm{\Pi }}_{{\rho }_{X^n\left(m\right)},\delta }\},$

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

$1-\text{Tr}\{{\mathrm{\Pi }}_{{\rho }_{X^n\left(m\right)},\delta }{\hat{\mathrm{\Pi }}}_{{\rho }_{X^n(m-1)},\delta }\cdots {\hat{\mathrm{\Pi }}}_{{\rho }_{X^n\left(1\right)},\delta }{\mathrm{\Pi }}_{\rho ,\delta }^n{\rho }_{x^n\left(m\right)}{\mathrm{\Pi }}_{\rho ,\delta }^n{\hat{\mathrm{\Pi }}}_{{\rho }_{X^n\left(1\right)},\delta }\cdots {\hat{\mathrm{\Pi }}}_{{\rho }_{X^n(m-1)},\delta }{\mathrm{\Pi }}_{{\rho }_{X^n\left(m\right)},\delta }\},$

and the average error probability of this scheme is equal to

$1-\frac{1}{M}\sum _m\text{Tr}\{{\mathrm{\Pi }}_{{\rho }_{X^n\left(m\right)},\delta }{\hat{\mathrm{\Pi }}}_{{\rho }_{X^n(m-1)},\delta }\cdots {\hat{\mathrm{\Pi }}}_{{\rho }_{X^n\left(1\right)},\delta }{\mathrm{\Pi }}_{\rho ,\delta }^n{\rho }_{x^n\left(m\right)}{\mathrm{\Pi }}_{\rho ,\delta }^n{\hat{\mathrm{\Pi }}}_{{\rho }_{X^n\left(1\right)},\delta }\cdots {\hat{\mathrm{\Pi }}}_{{\rho }_{X^n(m-1)},\delta }{\mathrm{\Pi }}_{{\rho }_{X^n\left(m\right)},\delta }\}.$

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:

Template:NumBlk

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={𝔼}_{X^n}\left\{\frac{1}{M}\sum _m\text{Tr}\left\{{\rho }_{X^n\left(m\right)}\right\}\right\}$

$={𝔼}_{X^n}\{\frac{1}{M}\sum _m\text{Tr}\left\{{\mathrm{\Pi }}_{\rho ,\delta }^n{\rho }_{X^n\left(m\right)}\right\}+\text{Tr}\left\{{\hat{\mathrm{\Pi }}}_{\rho ,\delta }^n{\rho }_{X^n\left(m\right)}\right\}\}$

$={𝔼}_{X^n}\left\{\frac{1}{M}\sum _m\text{Tr}\left\{{\mathrm{\Pi }}_{\rho ,\delta }^n{\rho }_{X^n\left(m\right)}{\mathrm{\Pi }}_{\rho ,\delta }^n\right\}\right\}+\frac{1}{M}\sum _m\text{Tr}\left\{{\hat{\mathrm{\Pi }}}_{\rho ,\delta }^n{𝔼}_{X^n}\left\{{\rho }_{X^n\left(m\right)}\right\}\right\}$

$={𝔼}_{X^n}\left\{\frac{1}{M}\sum _m\text{Tr}\left\{{\mathrm{\Pi }}_{\rho ,\delta }^n{\rho }_{X^n\left(m\right)}{\mathrm{\Pi }}_{\rho ,\delta }^n\right\}\right\}+\text{Tr}\left\{{\hat{\mathrm{\Pi }}}_{\rho ,\delta }^n{\rho }^{\otimes n}\right\}$

$\le {𝔼}_{X^n}\left\{\frac{1}{M}\sum _m\text{Tr}\left\{{\mathrm{\Pi }}_{\rho ,\delta }^n{\rho }_{X^n\left(m\right)}{\mathrm{\Pi }}_{\rho ,\delta }^n\right\}\right\}+ϵ$

Substituting into (Template:EquationNote) (and forgetting about the small $ϵ$ term for now) gives an upper bound of

${𝔼}_{X^n}\left\{\frac{1}{M}\sum _m\text{Tr}\left\{{\mathrm{\Pi }}_{\rho ,\delta }^n{\rho }_{X^n\left(m\right)}{\mathrm{\Pi }}_{\rho ,\delta }^n\right\}\right\}$

$-{𝔼}_{X^n}\left\{\frac{1}{M}\sum _m\text{Tr}\{{\mathrm{\Pi }}_{{\rho }_{X^n\left(m\right)},\delta }{\hat{\mathrm{\Pi }}}_{{\rho }_{X^n(m-1)},\delta }\cdots {\hat{\mathrm{\Pi }}}_{{\rho }_{X^n\left(1\right)},\delta }{\mathrm{\Pi }}_{\rho ,\delta }^n{\rho }_{X^n\left(m\right)}{\mathrm{\Pi }}_{\rho ,\delta }^n{\hat{\mathrm{\Pi }}}_{{\rho }_{X^n\left(1\right)},\delta }\cdots {\hat{\mathrm{\Pi }}}_{{\rho }_{X^n(m-1)},\delta }{\mathrm{\Pi }}_{{\rho }_{X^n\left(m\right)},\delta }\}\right\}.$

We then apply Sen's bound to this expression with $\sigma ={\mathrm{\Pi }}_{\rho ,\delta }^n{\rho }_{X^n\left(m\right)}{\mathrm{\Pi }}_{\rho ,\delta }^n$ and the sequential projectors as ${\mathrm{\Pi }}_{{\rho }_{X^n\left(m\right)},\delta }$, ${\hat{\mathrm{\Pi }}}_{{\rho }_{X^n(m-1)},\delta }$, ..., ${\hat{\mathrm{\Pi }}}_{{\rho }_{X^n\left(1\right)},\delta }$. This gives the upper bound ${𝔼}_{X^n}\left\{\frac{1}{M}\sum _{m}2{[\text{Tr}\left\{(I-{\mathrm{\Pi }}_{{\rho }_{X^n\left(m\right)},\delta }){\mathrm{\Pi }}_{\rho ,\delta }^n{\rho }_{X^n\left(m\right)}{\mathrm{\Pi }}_{\rho ,\delta }^n\right\}+\sum _{i=1}^{m-1}\text{Tr}\left\{{\mathrm{\Pi }}_{{\rho }_{X^n\left(i\right)},\delta }{\mathrm{\Pi }}_{\rho ,\delta }^n{\rho }_{X^n\left(m\right)}{\mathrm{\Pi }}_{\rho ,\delta }^n\right\}]}^{1/2}\right\}.$ Due to concavity of the square root, we can bound this expression from above by

$2{\left[{𝔼}_{X^n}\{\frac{1}{M}\sum _m\text{Tr}\left\{(I-{\mathrm{\Pi }}_{{\rho }_{X^n\left(m\right)},\delta }){\mathrm{\Pi }}_{\rho ,\delta }^n{\rho }_{X^n\left(m\right)}{\mathrm{\Pi }}_{\rho ,\delta }^n\right\}+\sum _{i=1}^{m-1}\text{Tr}\left\{{\mathrm{\Pi }}_{{\rho }_{X^n\left(i\right)},\delta }{\mathrm{\Pi }}_{\rho ,\delta }^n{\rho }_{X^n\left(m\right)}{\mathrm{\Pi }}_{\rho ,\delta }^n\right\}\}\right]}^{1/2}$

$\le 2{\left[{𝔼}_{X^n}\{\frac{1}{M}\sum _m\text{Tr}\left\{(I-{\mathrm{\Pi }}_{{\rho }_{X^n\left(m\right)},\delta }){\mathrm{\Pi }}_{\rho ,\delta }^n{\rho }_{X^n\left(m\right)}{\mathrm{\Pi }}_{\rho ,\delta }^n\right\}+\sum _{i\ne m}\text{Tr}\left\{{\mathrm{\Pi }}_{{\rho }_{X^n\left(i\right)},\delta }{\mathrm{\Pi }}_{\rho ,\delta }^n{\rho }_{X^n\left(m\right)}{\mathrm{\Pi }}_{\rho ,\delta }^n\right\}\}\right]}^{1/2},$

where the second bound follows by summing over all of the codewords not equal to the $m^{\text{th}}$ 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:

${𝔼}_{X^n}\left\{\frac{1}{M}\sum _m\text{Tr}\left\{(I-{\mathrm{\Pi }}_{{\rho }_{X^n\left(m\right)},\delta }){\mathrm{\Pi }}_{\rho ,\delta }^n{\rho }_{X^n\left(m\right)}{\mathrm{\Pi }}_{\rho ,\delta }^n\right\}\right\}$

$\le {𝔼}_{X^n}\{\frac{1}{M}\sum _m\text{Tr}\left\{(I-{\mathrm{\Pi }}_{{\rho }_{X^n\left(m\right)},\delta }){\rho }_{X^n\left(m\right)}\right\}+{\Vert {\rho }_{X^n\left(m\right)}-{\mathrm{\Pi }}_{\rho ,\delta }^n{\rho }_{X^n\left(m\right)}{\mathrm{\Pi }}_{\rho ,\delta }^n\Vert }_1\}$

$\le ϵ+2\sqrt{ϵ}.$

where the first inequality follows from (Template:EquationNote) 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 _{i\ne m}{𝔼}_{X^n}\left\{\text{Tr}\left\{{\mathrm{\Pi }}_{{\rho }_{X^n\left(i\right)},\delta }{\mathrm{\Pi }}_{\rho ,\delta }^n{\rho }_{X^n\left(m\right)}{\mathrm{\Pi }}_{\rho ,\delta }^n\right\}\right\}$

$=\sum _{i\ne m}\text{Tr}\left\{{𝔼}_{X^n}\left\{{\mathrm{\Pi }}_{{\rho }_{X^n\left(i\right)},\delta }\right\}{\mathrm{\Pi }}_{\rho ,\delta }^n{𝔼}_{X^n}\left\{{\rho }_{X^n\left(m\right)}\right\}{\mathrm{\Pi }}_{\rho ,\delta }^n\right\}$

$=\sum _{i\ne m}\text{Tr}\left\{{𝔼}_{X^n}\left\{{\mathrm{\Pi }}_{{\rho }_{X^n\left(i\right)},\delta }\right\}{\mathrm{\Pi }}_{\rho ,\delta }^n{\rho }^{\otimes n}{\mathrm{\Pi }}_{\rho ,\delta }^n\right\}$

$\le \sum _{i\ne m}{2}^{-n[H\left(B\right)-\delta ]}\text{Tr}\left\{{𝔼}_{X^n}\left\{{\mathrm{\Pi }}_{{\rho }_{X^n\left(i\right)},\delta }\right\}{\mathrm{\Pi }}_{\rho ,\delta }^n\right\}$

The first equality follows because the codewords $X^n\left(m\right)$ and $X^n\left(i\right)$ are independent since they are different. The second equality follows from (Template:EquationNote). The first inequality follows from (\ref{eq:3rd-typ-prop}). Continuing, we have

$\le \sum _{i\ne m}{2}^{-n[H\left(B\right)-\delta ]}{𝔼}_{X^n}\left\{\text{Tr}\left\{{\mathrm{\Pi }}_{{\rho }_{X^n\left(i\right)},\delta }\right\}\right\}$

$\le \sum _{i\ne m}{2}^{-n[H\left(B\right)-\delta ]}{2}^{n[H(B|X)+\delta ]}$

$=\sum _{i\ne m}{2}^{-n[I(X;B)-2\delta ]}$

$\le M{2}^{-n[I(X;B)-2\delta ]}.$

The first inequality follows from ${\mathrm{\Pi }}_{\rho ,\delta }^n\le I$ and exchanging the trace with the expectation. The second inequality follows from (\ref{eq:2nd-cond-typ}). The next two are straightforward.

Putting everything together, we get our final bound on the expectation of the average error probability:

$1-{𝔼}_{X^n}\left\{\frac{1}{M}\sum _m\text{Tr}\{{\mathrm{\Pi }}_{{\rho }_{X^n\left(m\right)},\delta }{\hat{\mathrm{\Pi }}}_{{\rho }_{X^n(m-1)},\delta }\cdots {\hat{\mathrm{\Pi }}}_{{\rho }_{X^n\left(1\right)},\delta }{\mathrm{\Pi }}_{\rho ,\delta }^n{\rho }_{X^n\left(m\right)}{\mathrm{\Pi }}_{\rho ,\delta }^n{\hat{\mathrm{\Pi }}}_{{\rho }_{X^n\left(1\right)},\delta }\cdots {\hat{\mathrm{\Pi }}}_{{\rho }_{X^n(m-1)},\delta }{\mathrm{\Pi }}_{{\rho }_{X^n\left(m\right)},\delta }\}\right\}$

$\le ϵ+2{[(ϵ+2\sqrt{ϵ})+M{2}^{-n[I(X;B)-2\delta ]}]}^{1/2}.$

Thus, as long as we choose $M=2^{n[I(X;B)-3\delta ]}$, there exists a code with vanishing error probability.

See also

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

References

• Template:Citation.
• Template:Citation.
• Template:Citation
• Template:Citation.
• Template:Citation.