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.

Background

Mixed states and quantum channels

A mixed quantum state is a unit trace, positive operator known as a density operator, and is often denoted by $\rho$, $\sigma$, $\omega$, etc. The simplest model for a quantum channel is a classical-quantum channel

$x\mapsto \rho _{x}.$

which sends the classical letter $x$ at the transmitting end to a quantum state $\rho _{x}$ at the receiving end, with noise possibly introduced in between. The receiver's task is to perform a measurement to determine the input of the sender. If the states $\rho _{x}$ are perfectly distinguishable from one another (i.e., if they have orthogonal supports such that $\operatorname {Tr} \rho _{x}\rho _{x^{\prime }}=0$ for $x\neq x^{\prime }$) and the channel is noiseless, then perfect decoding is trivially possible. If the states $\rho _{x}$ all commute with each other then the channel is effectively classical. The situation becomes nontrivial only when the states $\rho _{x}$ have overlapping support and do not necessarily commute.

Quantum measurements

The most general way to describe a quantum measurement is with a positive operator-valued measure, whose elements are typically denoted as $\left\{\Lambda _{m}\right\}_{m}$. These operators should satisfy positivity and completeness in order to form a valid POVM:

$\Lambda _{m}\geq 0\ \ \ \ \forall m$

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

$p(m)=\operatorname {Tr} \Lambda _{m}\rho ,$

and the post-measurement state is

$\rho _{m}^{\prime }={\frac {1}{p(m)}}\Lambda _{m}^{1/2}\rho \Lambda _{m}^{1/2},$

if the person measuring obtains outcome $m$.

Classical communication over quantum channels

The above is sufficient to consider a classical classical communication scheme over a cq channel. The sender uses a cq channel to map a classical letter x to a quantum state $\rho _{x}$, which is then sent through some noisy quantum channel, and then measured using some POVM by the receiver, who obtains another classical letter.

Precise definition

The classical capacity can be defined as the maximum rate achievable by a coding scheme for classical information transmission, which can be defined as follows.

Definition. (Coding scheme) A $(n,m,\delta )$-coding scheme for classical information transmission using a quantum channel $T:B({\mathcal {H}}_{A})\to B({\mathcal {H}}_{A})$ is given by pair of an encoding map $E:\{0,1\}^{n}\to D({\mathcal {H}}_{A}^{\otimes n})$ and a decoding POVM $\mu :\{0,1\}^{n}\to B({\mathcal {H}}_{B})^{\otimes n}$ such that $\langle \mu (x),T^{\otimes n}(E(x))\rangle \geq 1-\delta$ with respect to the Hilbert-Schmidt inner product for all $x\in \{0,1\}^{n}$.

Definition. (Achievable rate) A rate $R\geq 0$ is achievable for the channel $T$ if either $R=0$ or $R>0$ and for any $n$ there exists a $(n,m_{n},\delta _{n})$-coding scheme such that $R=\lim _{n\to \infty }m_{n}/n$ and $\lim _{n\to \infty }\delta _{n}=0$ both hold.

Holevo-Schumacher-Westmoreland theorem

The Holevo information (also called the Holevo $\chi$ quantity) of a quantum channel ${\mathcal {N}}$ can be defined as

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

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

$\rho ^{XA}=\sum _{x}p_{X}(x)\vert x\rangle \langle x\vert ^{X}\otimes \rho _{x}^{A}$

for some probability distribution $p_{X}(x)$ and density operators $\rho _{x}^{A}$ which can be input to the given channel.

Schumacher and Westmoreland in 1997, and Holevo independently in 1998, proved that the classical capacity of a quantum channel can be equivalently defined as

$C(T)=\lim _{k\to \infty }\chi (T^{\otimes k}).$

Gentle measurement lemma

The gentle measurement lemma states that a measurement succeeding with high probability does not disturb the state too much on average.

Lemma. (Winter) Given an ensemble $\left\{p_{X}(x),\rho _{x}\right\}$ with expected density operator $\rho \equiv \sum _{x}p_{X}(x)\rho _{x}$, suppose that an operator $\Lambda$ with $I\geq \Lambda \geq 0$ succeeds with probability $1-\epsilon$ on the state $\rho$:

$\operatorname {Tr} \Lambda \rho \geq 1-\epsilon .$

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

$\mathbb {E} _{X}[\left\Vert {\sqrt {\Lambda }}\rho _{X}{\sqrt {\Lambda }}-\rho _{X}\right\Vert _{1}]\leq 2{\sqrt {\epsilon }}.$

The gentle measurement lemma has the following analog which holds for any operators $\rho$, $\sigma$, $\Lambda$ such that $0\leq \rho ,\sigma ,\Lambda \leq I$:

$\operatorname {Tr} \Lambda \rho \leq \operatorname {Tr} \Lambda \sigma +\left\Vert \rho -\sigma \right\Vert _{1}.$ 1

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

Non-commutative union bound

Lemma. (Sen's bound) For a subnormalized state $\sigma$ such that $0\leq \sigma$ and $\operatorname {Tr} \sigma \leq 1$, and for projectors $\Pi _{1}$, ... , $\Pi _{N}$ we have $$\operatorname {Tr} \sigma -\operatorname {Tr} \Pi _{N}\cdots \Pi _{1}\ \sigma \ \Pi _{1}\cdots \Pi _{N}\leq 2{\sqrt {\sum _{i=1}^{N}\operatorname {Tr} \left(I-\Pi _{i}\right)\sigma }}.$$

Intuitively, Sen's bound is a sort of "non-commutative union bound" because it is analogous to the union bound from classical probability theory: $$\Pr \left(A_{1}\cap \cdots \cap A_{N}\right)^{c}=\Pr \left(A_{1}^{c}\cup \cdots \cup A_{N}^{c}\right)\leq \sum _{i=1}^{N}\Pr(A_{i}^{c}),$$ where $A_{1},\ldots ,A_{N}$ are events. The analogous quantum bound would be

${\text{Tr}}\left(I-\Pi _{1}\cdots \Pi _{N}\cdots \Pi _{1}\right)\rho \leq \sum _{i=1}^{N}{\text{Tr}}\left(I-\Pi _{i}\right)\rho$

if we think of $\Pi _{1}\cdots \Pi _{N}$ as a projector onto the intersection of subspaces. However, this only holds if the projectors $\Pi _{1}$, ..., $\Pi _{N}$ commute (choosing $\Pi _{1}=\left\vert +\right\rangle \left\langle +\right\vert$, $\Pi _{2}=\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 one must use a non-commutative or quantum union bound.

Proof

We now prove the HSW theorem with Sen's non-commutative union bound. We first describe how the code is chosen, then give the construction of Bob's POVM, and finally analyze the error of the protocol.

Encoding map

We first describe how Alice and Bob agree on a random choice of code. They have the channel $x\rightarrow \rho _{x}$ and a distribution $p_{X}(x)$. They choose $M$ classical sequences $x^{n}$ according to the IID distribution $p_{X^{n}}(x^{n})$. After selecting them, they label them with indices as $\{x^{n}(m)\}_{m\in [M]}$. This leads to the following quantum codewords:

$\rho _{x^{n}(m)}=\rho _{x_{1}(m)}\otimes \cdots \otimes \rho _{x_{n}(m)}.$

The quantum codebook is then $\{\rho _{x^{n}(m)}\}_{m\in [M]}$. The average state of the codebook is then

$\mathbb {E} _{X^{n}}[\rho _{X^{n}}]=\sum _{x^{n}}p_{X^{n}}(x^{n})\rho _{x^{n}}=\rho ^{\otimes n},$ 2

where $\rho =\sum _{x}p_{X}(x)\rho _{x}$.

Decoding POVM construction

Sen's 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 $\{\Pi _{\rho ,\delta }^{n},I-\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 $\{\Pi _{\rho _{x^{n}(m)},\delta },I-\Pi _{\rho _{x^{n}(m)},\delta }\}$.

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

$\mathbb {E} _{X^{n}}[\operatorname {Tr} \Pi _{\rho ,\delta }\rho _{X^{n}}]=\operatorname {Tr} \Pi _{\rho ,\delta }\ \mathbb {E} _{X^{n}}[\rho _{X^{n}}]$

$=\operatorname {Tr} \Pi _{\rho ,\delta }\rho ^{\otimes n}$

$\geq 1-\epsilon ,$

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

$\mathbb {E} _{X^{n}}[\operatorname {Tr} \Pi _{\rho _{X^{n}},\delta }\rho _{X^{n}}]\geq 1-\epsilon .$

Error analysis

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

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

where we make the abbreviation ${\hat {\Pi }}\equiv I-\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-\operatorname {Tr} \Pi _{\rho _{X^{n}(m)},\delta }{\hat {\Pi }}_{\rho _{X^{n}(m-1)},\delta }\cdots {\hat {\Pi }}_{\rho _{X^{n}(1)},\delta }\Pi _{\rho ,\delta }^{n}\rho _{x^{n}(m)}\Pi _{\rho ,\delta }^{n}{\hat {\Pi }}_{\rho _{X^{n}(1)},\delta }\cdots {\hat {\Pi }}_{\rho _{X^{n}(m-1)},\delta }\Pi _{\rho _{X^{n}(m)},\delta },$

and the average error probability of this scheme is equal to

$1-{\frac {1}{M}}\sum _{m}\operatorname {Tr} \Pi _{\rho _{X^{n}(m)},\delta }{\hat {\Pi }}_{\rho _{X^{n}(m-1)},\delta }\cdots {\hat {\Pi }}_{\rho _{X^{n}(1)},\delta }\Pi _{\rho ,\delta }^{n}\rho _{x^{n}(m)}\Pi _{\rho ,\delta }^{n}{\hat {\Pi }}_{\rho _{X^{n}(1)},\delta }\cdots {\hat {\Pi }}_{\rho _{X^{n}(m-1)},\delta }\Pi _{\rho _{X^{n}(m)},\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:

$1-\mathbb {E} _{X^{n}}\left[{\frac {1}{M}}\sum _{m}\operatorname {Tr} \Pi _{\rho _{X^{n}(m)},\delta }{\hat {\Pi }}_{\rho _{X^{n}(m-1)},\delta }\cdots {\hat {\Pi }}_{\rho _{X^{n}(1)},\delta }\Pi _{\rho ,\delta }^{n}\rho _{x^{n}(m)}\Pi _{\rho ,\delta }^{n}{\hat {\Pi }}_{\rho _{X^{n}(1)},\delta }\cdots {\hat {\Pi }}_{\rho _{X^{n}(m-1)},\delta }\Pi _{\rho _{X^{n}(m)},\delta }\right].$ 3

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 {E} _{X^{n}}\left[{\frac {1}{M}}\sum _{m}\operatorname {Tr} \rho _{X^{n}(m)}\right]$

$=\mathbb {E} _{X^{n}}\left[{\frac {1}{M}}\sum _{m}\operatorname {Tr} \Pi _{\rho ,\delta }^{n}\rho _{X^{n}(m)}+\operatorname {Tr} {\hat {\Pi }}_{\rho ,\delta }^{n}\rho _{X^{n}(m)}\right]$

$=\mathbb {E} _{X^{n}}\left[{\frac {1}{M}}\sum _{m}\operatorname {Tr} \Pi _{\rho ,\delta }^{n}\rho _{X^{n}(m)}\Pi _{\rho ,\delta }^{n}\right]+{\frac {1}{M}}\sum _{m}\operatorname {Tr} {\hat {\Pi }}_{\rho \delta }^{n}\mathbb {E} _{X^{n}}[\rho _{X^{n}(m)}]$

$=\mathbb {E} _{X^{n}}\left[{\frac {1}{M}}\sum _{m}\operatorname {Tr} \Pi _{\rho ,\delta }^{n}\rho _{X^{n}(m)}\Pi _{\rho ,\delta }^{n}\right]+\operatorname {Tr} {\hat {\Pi }}_{\rho ,\delta }^{n}\rho ^{\otimes n}$

$\leq \mathbb {E} _{X^{n}}\left[{\frac {1}{M}}\sum _{m}\operatorname {Tr} \Pi _{\rho ,\delta }^{n}\rho _{X^{n}(m)}\Pi _{\rho ,\delta }^{n}\right]+\epsilon$

Substituting into (3) (and forgetting about the small $\epsilon$ term for now) gives an upper bound of

$\mathbb {E} _{X^{n}}\left[{\frac {1}{M}}\sum _{m}\operatorname {Tr} \Pi _{\rho ,\delta }^{n}\rho _{X^{n}(m)}\Pi _{\rho ,\delta }^{n}\right]$

$-\mathbb {E} _{X^{n}}\left[{\frac {1}{M}}\sum _{m}\operatorname {Tr} \Pi _{\rho _{X^{n}(m)},\delta }{\hat {\Pi }}_{\rho _{X^{n}(m-1)},\delta }\cdots {\hat {\Pi }}_{\rho _{X^{n}(1)},\delta }\Pi _{\rho ,\delta }^{n}\rho _{x^{n}(m)}\Pi _{\rho ,\delta }^{n}{\hat {\Pi }}_{\rho _{X^{n}(1)},\delta }\cdots {\hat {\Pi }}_{\rho _{X^{n}(m-1)},\delta }\Pi _{\rho _{X^{n}(m)},\delta }\right].$

We then apply Sen's bound to this expression with $\sigma =\Pi _{\rho ,\delta }^{n}\rho _{X^{n}(m)}\Pi _{\rho ,\delta }^{n}$ and the sequential projectors as $\Pi _{\rho _{X^{n}(m)},\delta }$, ${\hat {\Pi }}_{\rho _{X^{n}(m-1)},\delta }$, ..., ${\hat {\Pi }}_{\rho _{X^{n}(1)},\delta }$. This gives the upper bound $\mathbb {E} _{X^{n}}\left[{\frac {1}{M}}\sum _{m}2\left(\operatorname {Tr} (I-\Pi _{\rho _{X^{n}(m)},\delta })\Pi _{\rho ,\delta }^{n}\rho _{X^{n}(m)}\Pi _{\rho ,\delta }^{n}+\sum _{i=1}^{m-1}\operatorname {Tr} \Pi _{\rho _{X^{n}(i)},\delta }\Pi _{\rho ,\delta }^{n}\rho _{X^{n}(m)}\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(\mathbb {E} _{X^{n}}\left[{\frac {1}{M}}\sum _{m}\operatorname {Tr} (I-\Pi _{\rho _{X^{n}(m)},\delta })\Pi _{\rho ,\delta }^{n}\rho _{X^{n}(m)}\Pi _{\rho ,\delta }^{n}+\sum _{i=1}^{m-1}\operatorname {Tr} \Pi _{\rho _{X^{n}(i)},\delta }\Pi _{\rho ,\delta }^{n}\rho _{X^{n}(m)}\Pi _{\rho ,\delta }^{n}\right]\right)^{1/2}$

$2\left(\mathbb {E} _{X^{n}}\left[{\frac {1}{M}}\sum _{m}\operatorname {Tr} (I-\Pi _{\rho _{X^{n}(m)},\delta })\Pi _{\rho ,\delta }^{n}\rho _{X^{n}(m)}\Pi _{\rho ,\delta }^{n}+\sum _{i\neq m}\operatorname {Tr} \Pi _{\rho _{X^{n}(i)},\delta }\Pi _{\rho ,\delta }^{n}\rho _{X^{n}(m)}\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:

$\mathbb {E} _{X^{n}}\left[{\frac {1}{M}}\sum _{m}\operatorname {Tr} (I-\Pi _{\rho _{X^{n}(m)},\delta })\Pi _{\rho ,\delta }^{n}\rho _{X^{n}(m)}\Pi _{\rho ,\delta }^{n}\right]$

$\leq \mathbb {E} _{X^{n}}\left[{\frac {1}{M}}\sum _{m}\operatorname {Tr} (I-\Pi _{\rho _{X^{n}(m)},\delta })\rho _{X^{n}(m)}+\left\Vert \rho _{X^{n}(m)}-\Pi _{\rho ,\delta }^{n}\rho _{X^{n}(m)}\Pi _{\rho ,\delta }^{n}\right\Vert _{1}\right]$

$\leq \epsilon +2{\sqrt {\epsilon }}.$

where the first inequality follows from (1) 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\neq m}\mathbb {E} _{X^{n}}[\operatorname {Tr} \Pi _{\rho _{X^{n}(i)},\delta }\Pi _{\rho ,\delta }^{n}\rho _{X^{n}(m)}\Pi _{\rho ,\delta }^{n}]$

$=\sum _{i\neq m}\operatorname {Tr} \mathbb {E} _{X^{n}}[\Pi _{\rho _{X^{n}(i)},\delta }]\Pi _{\rho ,\delta }^{n}\mathbb {E} _{X^{n}}[\rho _{X^{n}(m)}]\Pi _{\rho ,\delta }^{n}$

$=\sum _{i\neq m}\operatorname {Tr} \mathbb {E} _{X^{n}}[\Pi _{\rho _{X^{n}(i)},\delta }]\Pi _{\rho ,\delta }^{n}\rho ^{\otimes n}\Pi _{\rho ,\delta }^{n}$

$\leq \sum _{i\neq m}2^{-n\lfloor H(B)-\delta \rfloor }\operatorname {Tr} \mathbb {E} _{X^{n}}[\Pi _{\rho _{X^{n}(i)},\delta }]\Pi _{\rho ,\delta }^{n}$

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

$\leq \sum _{i\neq m}2^{-n\lfloor H(B)-\delta \rfloor }\mathbb {E} _{X^{n}}[\operatorname {Tr} \Pi _{\rho _{X^{n}(i)},\delta }]$

$\leq \sum _{i\neq m}2^{-n\lfloor H(B)-\delta \rfloor }\ 2^{n\lfloor H(B|X)+\delta \rfloor }$

$=\sum _{i\neq m}2^{-n\lfloor I(X;B)-2\delta \rfloor }$

$\leq M\ 2^{-n\lfloor I(X;B)-2\delta \rfloor }.$

The first inequality follows from $\Pi _{\rho ,\delta }^{n}\leq 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-\mathbb {E} _{X^{n}}\left[\operatorname {Tr} \Pi _{\rho _{X^{n}(m)},\delta }{\hat {\Pi }}_{\rho _{X^{n}(m-1)},\delta }\cdots {\hat {\Pi }}_{\rho _{X^{n}(1)},\delta }\Pi _{\rho ,\delta }^{n}\rho _{x^{n}(m)}\Pi _{\rho ,\delta }^{n}{\hat {\Pi }}_{\rho _{X^{n}(1)},\delta }\cdots {\hat {\Pi }}_{\rho _{X^{n}(m-1)},\delta }\Pi _{\rho _{X^{n}(m)},\delta }\right]$

$\leq \epsilon +2((\epsilon +2{\sqrt {\epsilon }})+M2^{-n\lfloor I(X;B)-2\delta \rfloor })^{1/2}.$

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

Non-additivity of the classical capacity

The HSW theorem can be seen as expressing the classical capacity of a channel $\Phi$ in terms of a regularization of the Holevo $\chi$-quantity over multiple uses of $\Phi$. An open problem in quantum information theory was to determine if the $\chi$-quantity is additive, which would imply that the classical capacity could be expressed using a single use of $\Phi$. However, channels giving counterexamples to this statement were eventually given by Matthew Hastings in 2009. Follow-up work showed that this is a generic phenomenon, in the sense that a channel chosen randomly from a natural probability distribution will give a counterexample with high probability. (This stands in contrast to proofs using the probabilistic method, where random sampling is shown to give a counterexample only with nonzero probability.) A proof of this can be given using Dvoretzky's theorem.

Minimal output entropy

Non-additivity of the classical capacity is closely related to non-additivity of the minimal von Neumann entropy of the output of a quantum channel. An easier problem is to consider the minimal output quantum Rényi entropy for $p>2$, for which simple counterexamples using the inherent entanglement of fermions were given by Grudka, Horodecki, and Pankowski.

See also

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

References

• Wilde, Mark M. (2017), Quantum Information Theory, Cambridge University Press, arXiv:1106.1445, Bibcode:2011arXiv1106.1445W, doi:10.1017/9781316809976.001, S2CID 2515538
• Guha, Saikat; Tan, Si-Hui; Wilde, Mark M. (2012), "Explicit capacity-achieving receivers for optical communication and quantum reading", IEEE International Symposium on Information Theory Proceedings (ISIT 2012), pp. 551–555, arXiv:1202.0518, doi:10.1109/ISIT.2012.6284251, ISBN 978-1-4673-2579-0, S2CID 8786400.