Classical capacity explained

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

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

where

\rho ^{XA} is a classical-quantum state of the following form:\rho ^{XA} = \sum _{x} p _{X(x)} \vert x \rangle \langle x \vert ^{X} ⊗ \rho ^{A} _{x} , p _{X(x)} is a probability distribution, and each \rho ^{A} _{x} is a density operator that can be input to the channel l{N} .

Achievability using sequential decoding

We briefly review the HSW coding theorem (thestatement of the achievability of the Holevo information rate

I(X;B) forcommunicating classical data over a quantum channel). We first review theminimal amount of quantum mechanics needed for the theorem. We then coverquantum typicality, and finally we prove the theorem using a recent sequentialdecoding technique.

Review of quantum mechanics

In order to prove the HSW coding theorem, we really just need a few basicthings from quantum mechanics. First, a quantum state is a unit trace,positive operator known as a density operator. Usually, we denote itby

\rho , \sigma , \omega , etc. The simplest model for a quantum channelis 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 receivingend. It is the task of the receiver to perform a measurement to determine theinput of the sender. If it is true that the states \rho _{x} are perfectlydistinguishable from one another (i.e., if they have orthogonal supports suchthat Tr \left\{ \rho _{x} \rho _{x ^{\prime}} \right\} =0 for x ≠ x ^{\prime} ), then the channel is a noiseless channel. We are interested in situationsfor which this is not the case. If it is true that the states \rho _{x} allcommute with one another, then this is effectively identical to the situationfor 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\{ Λ _{m} \right\} _{m} . These operators should satisfypositivity and completeness in order to form a valid POVM:Λ _{m} \geq 0 \forall m \sum _{m} Λ _{m} = I. The probabilistic interpretation of quantum mechanics states that if someonemeasures a quantum state \rho using a measurement device corresponding tothe POVM \left\{ Λ _{m} \right\} , then the probability p\left(m\right) for obtaining outcome m is equal top\left( m\right) = Tr \left\{ Λ _{m} \rho\right\} , and the post-measurement state is\rho ^{\prime} _{m} = (1)/(p\left( m\right)) \sqrt{ Λ _{m} }\rho\sqrt,if the person measuring obtains outcome m . These rules are sufficient for usto 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. Itdemonstrates that a measurement that succeeds with high probability on averagedoes not disturb the state too much on average:

Lemma: [Winter] Given anensemble

\left\{ p _{X} \left( x\right) ,\rho _{x} \right\} with expecteddensity operator \rho\equiv\sum _{x} p _{X} \left( x\right) \rho _{x} , supposethat an operator Λ such that I\geq Λ \geq 0 succeeds with highprobability on the state \rho :Tr \left\{ Λ \rho\right\} \geq 1- \epsilon.

Then the subnormalized state

\sqrt{ Λ }\rho _{x} \sqrt{ Λ } is closein expected trace distance to the original state \rho _{x} :E _{X} \left\{ \left\Vert \sqrt{ Λ }\rho _{X} \sqrt{ Λ } - \rho _{X} \right\Vert _{1} \right\} \leq 2 \sqrt{\epsilon}.

(Note that

\left\Vert A\right\Vert _{1} is the nuclear norm of the operatorA so that \left\Vert A\right\Vert _{1} \equiv Tr\left\{ \sqrt{A ^{\dagger} A}\right\} .)

The following inequality is useful for us as well. It holds for any operators

\rho , \sigma , Λ such that 0 \leq\rho,\sigma, Λ \leq I :

The quantum information-theoretic interpretation of the above inequality isthat the probability of obtaining outcome

Λ from a quantum measurementacting on the state \rho is upper bounded by the probability of obtainingoutcome Λ on the state \sigma summed with the distinguishability ofthe two states \rho and \sigma .

Non-commutative union bound

Lemma: [Sen's bound] The following boundholds for a subnormalized state

\sigma such that 0 \leq\sigma andTr\left\{ \sigma\right\} \leq 1 with \Pi _{1} , ..., \Pi _{N} beingprojectors:Tr \left\{ \sigma\right\} - Tr \left\{ \Pi _{N} … \Pi _{1} \sigma \Pi _{1} … \Pi _{N} \right\} \leq 2 \sqrt{\sum ^{N} _{i =1} Tr \left\{ \left( I - \Pi _{i} \right) \sigma\right\} },

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

\Pr\left\{ \left( A _{1} \cap … \cap A _{N} \right) ^{c} \right\} = \Pr\left\{ A ^{c} _{1} \cup … \cup A ^{c} _{N} \right\} \leq\sum ^{N} _{i =1} \Pr\left\{ A ^{c} _{i} \right\} ,

where

A _{1} , \ldots, A _{N} are events. The analogous bound for projectorlogic would beTr \left\{ \left( I - \Pi _{1} … \Pi _{N} … \Pi _{1} \right) \rho\right\} \leq\sum ^{N} _{i =1} Tr \left\{ \left( I - \Pi _{i} \right) \rho\right\} , if we think of \Pi _{1} … \Pi _{N} as a projector onto the intersection ofsubspaces. Though, the above bound only holds if the projectors \Pi _{1} ,..., \Pi _{N} are commuting (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 Sen'sbound 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. Wedivide 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 arandom choice of code. They have the channel

x → \rho _{x} and adistribution p _{X} \left( x\right) . They choose M classical sequencesx ^{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[} . This leads to the followingquantum codewords:\rho _{x ^{n} \left( m\right)} = \rho _{x _{1} \left( m\right)} ⊗ … ⊗ \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

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 shouldfirst ask "Is the received state in the average typicalsubspace?" He can do this operationally by performing atypical subspace measurement corresponding to

\left\{ \Pi _{\rho,\delta} ^{n} ,I - \Pi ^{n} _{\rho,\delta} \right\} . Next, he asks in sequential order,"Is the received codeword in the m ^{th} conditionally typical subspace?" This is in some senseequivalent to the question, "Is the received codeword them ^{th} transmitted codeword?" He can ask thesequestions operationally by performing the measurements corresponding to theconditionally typical projectors \left\{ \Pi _{\rho _{x ^{n} \left( m\right)} ,\delta} ,I - \Pi _{\rho _{x ^{n} \left( m\right)} ,\delta} \right\} .

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

E _{X ^{n}} \left\{ Tr \left\{ \Pi _{\rho,\delta} \rho _{X ^{n}} \right\} \right\} = Tr \left\{ \Pi _{\rho,\delta} E _{X ^{n}} \left\{ \rho _{X ^{n}} \right\} \right\} = Tr \left\{ \Pi _{\rho,\delta} \rho ^{⊗} \right\} \geq 1- \epsilon, where the inequality follows from (\ref). Also, theprojectors \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 quantumtypicality:E _{X ^{n}} \left\{ Tr \left\{ \Pi _{\rho _{X ^{n}} ,\delta} \rho _{X ^{n}} \right\} \right\} \geq 1- \epsilon.

Error Analysis. The probability of detecting the

m ^{th} codeword correctly under our sequential decoding scheme is equal toTr \left\{ \Pi _{\rho _{X ^{n} \left( m\right)} ,\delta} \hat{\Pi} _{\rho _{X ^{n} \left( m -1 \right)} ,\delta} … \hat{\Pi} _{\rho _{X ^{n} \left( 1 \right)} ,\delta} \Pi ^{n} _{\rho,\delta} \rho _{x ^{n} \left( m\right)} \Pi ^{n} _{\rho,\delta} \hat{\Pi} _{\rho _{X ^{n} \left( 1 \right)} ,\delta} … \hat{\Pi} _{\rho _{X ^{n} \left( m -1 \right)} ,\delta} \Pi _{\rho _{X ^{n} \left( m\right)} ,\delta} \right\} ,

where we make the abbreviation

\hat{\Pi}\equiv I - \Pi . (Observe that weproject into the average typical subspace just once.) Thus, the probability ofan incorrect detection for the m ^{th} codeword is given by1- Tr \left\{ \Pi _{\rho _{X ^{n} \left( m\right)} ,\delta} \hat{\Pi} _{\rho _{X ^{n} \left( m -1 \right)} ,\delta} … \hat{\Pi} _{\rho _{X ^{n} \left( 1 \right)} ,\delta} \Pi ^{n} _{\rho,\delta} \rho _{x ^{n} \left( m\right)} \Pi ^{n} _{\rho,\delta} \hat{\Pi} _{\rho _{X ^{n} \left( 1 \right)} ,\delta} … \hat{\Pi} _{\rho _{X ^{n} \left( m -1 \right)} ,\delta} \Pi _{\rho _{X ^{n} \left( m\right)} ,\delta} \right\} ,

and the average error probability of this scheme is equal to

1- (1)/(M) \sum _{m} Tr \left\{ \Pi _{\rho _{X ^{n} \left( m\right)} ,\delta} \hat{\Pi} _{\rho _{X ^{n} \left( m -1 \right)} ,\delta} … \hat{\Pi } _{\rho _{X ^{n} \left( 1 \right)} ,\delta} \Pi ^{n} _{\rho,\delta} \rho _{x ^{n} \left( m\right)} \Pi ^{n} _{\rho,\delta} \hat{\Pi} _{\rho _{X ^{n} \left( 1 \right)} ,\delta} … \hat{\Pi} _{\rho _{X ^{n} \left(m -1 \right)} ,\delta} \Pi _{\rho _{X ^{n} \left( m\right)} ,\delta} \right\} .

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

Our first step is to apply Sen's bound to the above quantity. But before doingso, we should rewrite the above expression just slightly, by observing that

1 = E _{X ^{n}} \left\{ (1)/(M) \sum _{m} Tr \left\{ \rho _{X ^{n} \left( m\right)} \right\} \right\} = E _{X ^{n}} \left\{ (1)/(M) \sum _{m} Tr \left\{ \Pi ^{n} _{\rho,\delta} \rho _{X ^{n} \left( m\right)} \right\} + Tr \left\{ \hat{\Pi} ^{n} _{\rho,\delta} \rho _{X ^{n} \left( m\right)} \right\} \right\} = E _{X ^{n}} \left\{ (1)/(M) \sum _{m} Tr \left\{ \Pi ^{n} _{\rho,\delta} \rho _{X ^{n} \left( m\right)} \Pi ^{n} _{\rho,\delta} \right\} \right\} + (1)/(M) \sum _{m} Tr \left\{ \hat{\Pi} _{\rho,\delta} ^{n} E _{X ^{n}} \left\{ \rho _{X ^{n} \left( m\right)} \right\} \right\} = E _{X ^{n}} \left\{ (1)/(M) \sum _{m} Tr \left\{ \Pi ^{n} _{\rho,\delta} \rho _{X ^{n} \left( m\right)} \Pi ^{n} _{\rho,\delta} \right\} \right\} + Tr \left\{ \hat{\Pi} ^{n} _{\rho,\delta} \rho ^{⊗ n} \right\} \leq E _{X ^{n}} \left\{ (1)/(M) \sum _{m} Tr \left\{ \Pi ^{n} _{\rho,\delta} \rho _{X ^{n} \left( m\right)} \Pi _{\rho,\delta} ^{n} \right\} \right\} + \epsilon Substituting into (and forgetting about the small\epsilon term for now) gives an upper bound ofE _{X ^{n}} \left\{ (1)/(M) \sum _{m} Tr \left\{ \Pi ^{n} _{\rho,\delta} \rho _{X ^{n} \left( m\right)} \Pi ^{n} _{\rho,\delta} \right\} \right\} - E _{X ^{n}} \left\{ (1)/(M) \sum _{m} Tr \left\{ \Pi _{\rho _{X ^{n} \left( m\right)} ,\delta} \hat{\Pi} _{\rho _{X ^{n} \left(m -1 \right)} ,\delta} … \hat{\Pi} _{\rho _{X ^{n} \left( 1 \right)} ,\delta} \Pi ^{n} _{\rho,\delta} \rho _{X ^{n} \left( m\right)} \Pi ^{n} _{\rho,\delta} \hat{\Pi} _{\rho _{X ^{n} \left( 1 \right)} ,\delta} … \hat{\Pi} _{\rho _{X ^{n} \left( m -1 \right)} ,\delta} \Pi _{\rho _{X ^{n} \left( m\right)} ,\delta} \right\} \right\} . We then apply Sen's bound to this expression with \sigma = \Pi ^{n} _{\rho,\delta} \rho _{X ^{n} \left( m\right)} \Pi ^{n} _{\rho,\delta} and the sequentialprojectors as \Pi _{\rho _{X ^{n} \left( m\right)} ,\delta} , \hat{\Pi} _{\rho _{X ^{n} \left( m -1 \right)} ,\delta} , ..., \hat{\Pi} _{\rho _{X ^{n} \left( 1 \right)} ,\delta} . This gives the upper boundE _{X ^{n}} \left\{ (1)/(M) \sum _{m} 2 \left[ Tr \left\{ \left( I - \Pi _{\rho _{X ^{n} \left( m\right)} ,\delta} \right) \Pi ^{n} _{\rho ,\delta} \rho _{X ^{n} \left( m\right)} \Pi ^{n} _{\rho,\delta} \right\} + \sum ^{m -1} _{i =1} Tr \left\{ \Pi _{\rho _{X ^{n} \left( i\right)} ,\delta} \Pi ^{n} _{\rho,\delta} \rho _{X ^{n} \left( m\right)} \Pi _{\rho,\delta} ^{n} \right\} \right] ^{1/2} \right\} . Due to concavity of the square root, we can bound this expression from aboveby2 \left[ E _{X ^{n}} \left\{ (1)/(M) \sum _{m} Tr \left\{ \left( I - \Pi _{\rho _{X ^{n} \left( m\right)} ,\delta} \right) \Pi ^{n} _{\rho ,\delta} \rho _{X ^{n} \left( m\right)} \Pi ^{n} _{\rho,\delta} \right\} + \sum ^{m -1} _{i =1} Tr \left\{ \Pi _{\rho _{X ^{n} \left( i\right)} ,\delta} \Pi ^{n} _{\rho,\delta} \rho _{X ^{n} \left( m\right)} \Pi _{\rho,\delta} ^{n} \right\} \right\} \right] ^{1/2} \leq 2 \left[ E _{X ^{n}} \left\{ (1)/(M) \sum _{m} Tr \left\{ \left( I - \Pi _{\rho _{X ^{n} \left( m\right)} ,\delta} \right) \Pi ^{n} _{\rho ,\delta} \rho _{X ^{n} \left( m\right)} \Pi ^{n} _{\rho,\delta} \right\} + \sum _{i ≠} Tr \left\{ \Pi _{\rho _{X ^{n} \left( i\right)} ,\delta} \Pi ^{n} _{\rho,\delta} \rho _{X ^{n} \left( m\right)} \Pi _{\rho,\delta} ^{n} \right\} \right\} \right] ^{1/2} , where the second bound follows by summing over all of the codewords not equalto the m ^{th} codeword (this sum can only be larger).

We now focus exclusively on showing that the term inside the square root canbe made small. Consider the first term:

E _{X ^{n}} \left\{ (1)/(M) \sum _{m} Tr \left\{ \left(I - \Pi _{\rho _{X ^{n} \left( m\right)} ,\delta} \right) \Pi _{\rho,\delta} ^{n} \rho _{X ^{n} \left( m\right)} \Pi ^{n} _{\rho,\delta} \right\} \right\} \leq E _{X ^{n}} \left\{ (1)/(M) \sum _{m} Tr \left\{ \left(I - \Pi _{\rho _{X ^{n} \left( m\right)} ,\delta} \right) \rho _{X ^{n} \left(m\right)} \right\} + \left\Vert \rho _{X ^{n} \left( m\right)} - \Pi ^{n} _{\rho,\delta} \rho _{X ^{n} \left( m\right)} \Pi _{\rho,\delta} ^{n} \right\Vert _{1} \right\} \leq\epsilon +2 \sqrt{\epsilon}. where the first inequality follows from and thesecond inequality follows from the gentle operator lemma and theproperties of unconditional and conditional typicality. Consider now thesecond term and the following chain of inequalities:\sum _{i ≠} E _{X ^{n}} \left\{ Tr \left\{ \Pi _{\rho _{X ^{n} \left( i\right)} ,\delta} \Pi ^{n} _{\rho,\delta} \rho _{X ^{n} \left(m\right)} \Pi ^{n} _{\rho,\delta} \right\} \right\} = \sum _{i ≠} Tr \left\{ E _{X ^{n}} \left\{ \Pi _{\rho _{X ^{n} \left( i\right)} ,\delta} \right\} \Pi _{\rho,\delta} ^{n} E _{X ^{n}} \left\{ \rho _{X ^{n} \left( m\right)} \right\} \Pi ^{n} _{\rho,\delta} \right\} = \sum _{i ≠} Tr \left\{ E _{X ^{n}} \left\{ \Pi _{\rho _{X ^{n} \left( i\right)} ,\delta} \right\} \Pi _{\rho,\delta} ^{n} \rho ^{⊗} \Pi ^{n} _{\rho,\delta} \right\} \leq\sum _{i ≠} 2 ^{-n\left[} Tr \left\{ E _{X ^{n}} \left\{ \Pi _{\rho _{X ^{n} \left(i\right)} ,\delta} \right\} \Pi ^{n} _{\rho,\delta} \right\} The first equality follows because the codewords X ^{n} \left( m\right) andX ^{n} \left( i\right) are independent since they are different. The secondequality follows from . The first inequality follows from(\ref). Continuing, we have\leq\sum _{i ≠} 2 ^{-n\left[} E _{X ^{n}} \left\{ Tr \left\{ \Pi _{\rho _{X ^{n} \left(i\right)} ,\delta} \right\} \right\} \leq\sum _{i ≠} 2 ^{-n\left[} 2 ^{n\left[} = \sum _{i ≠} 2 ^{-n\left[} \leq M 2 ^{-n\left[} . The first inequality follows from \Pi ^{n} _{\rho,\delta} \leq I and exchangingthe 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 theaverage error probability:

1- E _{X ^{n}} \left\{ (1)/(M) \sum _{m} Tr \left\{ \Pi _{\rho _{X ^{n} \left( m\right)} ,\delta} \hat{\Pi} _{\rho _{X ^{n} \left(m -1 \right)} ,\delta} … \hat{\Pi} _{\rho _{X ^{n} \left( 1 \right)} ,\delta} \Pi ^{n} _{\rho,\delta} \rho _{X ^{n} \left( m\right)} \Pi ^{n} _{\rho,\delta} \hat{\Pi} _{\rho _{X ^{n} \left( 1 \right)} ,\delta} … \hat{\Pi} _{\rho _{X ^{n} \left( m -1 \right)} ,\delta} \Pi _{\rho _{X ^{n} \left( m\right)} ,\delta} \right\} \right\} \leq\epsilon +2 \left[ \left( \epsilon +2 \sqrt{\epsilon}\right) + M 2 ^{-n\left[} \right] ^{1/2} . Thus, as long as we choose M =2 ^{n\left[} , there exists a code with vanishing error probability.

See also

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

References

• .
• .
  • .
• .