In the theory ofquantum communication, thequantum capacity is the highest rate at whichquantum information can be communicated over many independent uses of a noisyquantum channel from a sender to a receiver. It is also equal to the highest rate at whichentanglement can be generated over the channel, and forward classical communication cannot improve it. The quantum capacity theorem is important for the theory ofquantum error correction, and more broadly for the theory ofquantum computation. The theorem giving a lower bound on the quantum capacity of any channel is colloquially known as the LSD theorem, after the authorsLloyd,^[1]Shor,^[2] and Devetak^[3] who proved it with increasing standards of rigor.^[4]

The LSD theorem states that thecoherent information of aquantum channel is an achievable rate for reliable quantum communication. For aPauli channel, thecoherent information has a simple form^{[citation needed]} and the proof that it is achievable is particularly simple as well. We^[who?] prove the theorem for this special case by exploiting randomstabilizer codes and correcting only the likely errors that the channel produces.

Theorem (hashing bound). There exists a stabilizerquantum error-correcting code that achieves the hashing limit${\displaystyle R=1-H\left(\mathbf{p}\right)}$ for a Pauli channel of the following form:$${\displaystyle \rho \mapsto p_I\rho +p_{X}X\rho X+p_{Y}Y\rho Y+p_{Z}Z\rho Z,}$$where${\displaystyle \mathbf{p}=\left(p_I,p_X,p_Y,p_Z\right)}$ and${\displaystyle H\left(\mathbf{p}\right)}$ is the entropy of this probability vector.

Proof. Consider correcting only the typical errors. That is, consider defining thetypical set of errors as follows:$${\displaystyle T_{\delta }^{{\mathbf{p}}^n}\equiv \left\{a^n:\left|-\frac{1}{n}{\log }_2\left(Pr\left\{E_{a^n}\right\}\right)-H\left(\mathbf{p}\right)\right|\le \delta \right\},}$$where${\displaystyle a^n}$ is some sequence consisting of the letters${\displaystyle \left\{I,X,Y,Z\right\}}$ and${\displaystyle Pr\left\{E_{a^n}\right\}}$ is the probability that an IID Pauli channel issues some tensor-product error${\displaystyle E_{a^n}\equiv E_{a_1}\otimes \cdots \otimes E_{a_n}}$. This typical set consists of the likely errors in the sense that$${\displaystyle \sum _{a^n\in T_{\delta }^{{\mathbf{p}}^n}}Pr\left\{E_{a^n}\right\}\ge 1-ϵ,}$$for all${\displaystyle ϵ>0}$ and sufficiently large${\displaystyle n}$. The error-correctingconditions^[5] for a stabilizer code${\displaystyle \mathcal{S}}$ in this case are that${\displaystyle \{E_{a^n}:a^n\in T_{\delta }^{{\mathbf{p}}^n}\}}$ is a correctable set of errors if

$${\displaystyle E_{a^n}^{†}{E}_{b^n}\notin N\left(\mathcal{S}\right)\mathrm{\setminus }\mathcal{S},}$$for all error pairs${\displaystyle E_{a^n}}$ and${\displaystyle E_{b^n}}$ such that${\displaystyle a^n,b^n\in T_{\delta }^{{\mathbf{p}}^n}}$ where${\displaystyle N(\mathcal{S})}$ is thenormalizer of${\displaystyle \mathcal{S}}$. Also, we consider the expectation of the error probability under a random choice of a stabilizer code.

Proceed as follows:The first equality follows by definition—${\displaystyle \mathcal{I}}$ is an indicator function equal to one if${\displaystyle E_{a^n}}$ is uncorrectable under${\displaystyle \mathcal{S}}$ and equal to zero otherwise. The first inequality follows, since we correct only the typical errors because the atypical error set has negligible probability mass. The second equality follows by exchanging the expectation and the sum. The third equality follows because the expectation of an indicator function is the probability that the event it selects occurs.

Continuing, we have:$${\displaystyle =\sum _{a^n\in T_{\delta }^{{\mathbf{p}}^n}}Pr\left\{E_{a^n}\right\}\underset{\mathcal{S}}{Pr}\left\{\mathrm{\exists }{E}_{b^n}:b^n\in T_{\delta }^{{\mathbf{p}}^n},b^n\ne a^n,E_{a^n}^{†}{E}_{b^n}\in N\left(\mathcal{S}\right)\mathrm{\setminus }\mathcal{S}\right\}}$$

${\displaystyle \le \sum _{a^n\in T_{\delta }^{A^n}}Pr\left\{E_{a^n}\right\}\underset{\mathcal{S}}{Pr}\left\{\mathrm{\exists }{E}_{b^n}:b^n\in T_{\delta }^{{\mathbf{p}}^n},b^n\ne a^n,E_{a^n}^{†}{E}_{b^n}\in N\left(\mathcal{S}\right)\right\}}$

${\displaystyle =\sum _{a^n\in T_{\delta }^{{\mathbf{p}}^n}}Pr\left\{E_{a^n}\right\}\underset{\mathcal{S}}{Pr}\left\{\bigcup _{b^n\in T_{\delta }^{{\mathbf{p}}^n},b^n\ne a^n}{E}_{a^n}^{†}{E}_{b^n}\in N\left(\mathcal{S}\right)\right\}}$

${\displaystyle \le \sum _{a^n,b^n\in T_{\delta }^{{\mathbf{p}}^n},b^n\ne a^n}Pr\left\{E_{a^n}\right\}\underset{\mathcal{S}}{Pr}\left\{E_{a^n}^{†}{E}_{b^n}\in N\left(\mathcal{S}\right)\right\}}$

${\displaystyle \le \sum _{a^n,b^n\in T_{\delta }^{{\mathbf{p}}^n},b^n\ne a^n}Pr\left\{E_{a^n}\right\}{2}^{-\left(n-k\right)}}$

${\displaystyle \le 2^{2n\left[H\left(\mathbf{p}\right)+\delta \right]}{2}^{-n\left[H\left(\mathbf{p}\right)+\delta \right]}{2}^{-\left(n-k\right)}}$

${\displaystyle =2^{-n\left[1-H\left(\mathbf{p}\right)-k/n-3\delta \right]}.}$

The first equality follows from the error-correcting conditions for a quantum stabilizer code, where${\displaystyle N\left(\mathcal{S}\right)}$ is the normalizer of${\displaystyle \mathcal{S}}$. The first inequality follows by ignoring any potential degeneracy in the code—we consider an error uncorrectable if it lies in the normalizer${\displaystyle N\left(\mathcal{S}\right)}$ and the probability can only be larger because${\displaystyle N\left(\mathcal{S}\right)\mathrm{\setminus }\mathcal{S}\in N\left(\mathcal{S}\right)}$. The second equality follows by realizing that the probabilities for the existence criterion and the union of events are equivalent. The second inequality follows by applying the union bound. The third inequality follows from the fact that the probability for a fixed operator${\displaystyle E_{a^n}^{†}{E}_{b^n}}$ not equal to the identity commuting withthe stabilizer operators of a random stabilizer can be upper bounded as follows:${\displaystyle \underset{\mathcal{S}}{Pr}\left\{E_{a^n}^{†}{E}_{b^n}\in N\left(\mathcal{S}\right)\right\}=\frac{2^{n+k}-1}{2^{2n}-1}\le 2^{-\left(n-k\right)}.}$The reasoning here is that the random choice of a stabilizer code is equivalent tofixing operators${\displaystyle Z_1}$, ...,${\displaystyle Z_{n-k}}$ and performing a uniformly randomClifford unitary. The probability that a fixed operator commutes with${\displaystyle {\overline{Z}}_1}$, ...,${\displaystyle {\overline{Z}}_{n-k}}$ is then just the number ofnon-identity operators in the normalizer (${\displaystyle 2^{n+k}-1}$) divided by the total number of non-identity operators (${\displaystyle 2^{2n}-1}$). After applying the above bound, we then exploit the following typicality bounds:$${\displaystyle \mathrm{\forall }{a}^n\in T_{\delta }^{{\mathbf{p}}^n}:Pr\left\{E_{a^n}\right\}\le 2^{-n\left[H\left(\mathbf{p}\right)+\delta \right]},}$$$${\displaystyle \left|T_{\delta }^{{\mathbf{p}}^n}\right|\le 2^{n\left[H\left(\mathbf{p}\right)+\delta \right]}.}$$We conclude that as long as the rate${\displaystyle k/n=1-H\left(\mathbf{p}\right)-4\delta }$, the expectation of the error probability becomes arbitrarily small, so that there exists at least one choice of a stabilizer code with the same bound on the error probability.

• Quantum computing

• Quantum information science
• Quantum information theory
• Models of computation
• Quantum cryptography
• Theoretical computer science
• Classes of computers
• Information theory
• Computational complexity theory
• Limits of computation

• CS1 maint: location missing publisher
• Use American English from January 2019
• All Wikipedia articles written in American English
• Articles with short description
• Short description matches Wikidata
• All articles with unsourced statements
• Articles with unsourced statements from April 2015
• All articles with specifically marked weasel-worded phrases
• Articles with specifically marked weasel-worded phrases from October 2017