Classical capacity

Uses your system voice; voice and rate in settings.

Snapshot

≈ 16 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

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.

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} \geq0\ \ \ \ \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 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}). Hayashi and Nagaoka extended the information-spectrum approach to classical-quantum channels, giving capacity formulas and a characterization of the strong-converse property without assuming stationarity or memorylessness. For stationary memoryless channels, their formulation recovers the usual Holevo-capacity result. The Hayashi-Nagaoka operator inequality from this work is used to bound error probabilities of square-root measurements in achievability proofs for classical communication over quantum channels.

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\geq0 succeeds with probability 1-\epsilon on the state \rho : \operatorname{Tr} \Lambda\rho \geq1-\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}] \leq2\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 : 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 \leq1 , 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} \leq2\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 {{NumBlk|:| \mathbb{E}_{X^{n}}[\rho_{X^{n}}] = \sum_{x^{n}}p_{X^{n}}(x^{n})\rho_{x^{n}}=\rho^{\otimes n}, | }} 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} \geq1-\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: {{NumBlk|:| 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]. | }} 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 ( ) (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 ( ) 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 ( ). 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}) + M 2^{-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.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1363590191 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot enwiki-001363590191 · captured 1783735072.0 · version history

Cite this page as: encyclopegia.org, “Classical capacity”, snapshot enwiki-001363590191. https://encyclopegia.org/a/classical-capacity

Sources cited in this revision

3 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.