{{Use American English|date=January 2019}} {{Short description|Highest rate quantum information can be sent through a noisy quantum channel}} In the theory of quantum communication, the '''quantum capacity''' is the highest rate at which quantum information can be communicated over many independent uses of a noisy quantum channel from a sender to a receiver. It is also equal to the highest rate at which entanglement can be generated over the channel, and forward classical communication cannot improve it. The quantum capacity theorem is important for the theory of quantum error correction, and more broadly for the theory of quantum computation. The theorem giving a lower bound on the quantum capacity of any channel is colloquially known as the Lloyd–Shor–Devetak (LSD) theorem, after the authors Seth Lloyd,<ref name="Lloyd1997">{{cite journal | journal = Physical Review A | volume = 55 | issue = 3 | pages = 1613–1622 | year = 1997 | author = Seth Lloyd |title = Capacity of the noisy quantum channel | doi = 10.1103/PhysRevA.55.1613 | arxiv = quant-ph/9604015|bibcode = 1997PhRvA..55.1613L | s2cid = 5555850 }}</ref> Peter Shor,<ref name="Shor2002">{{cite journal | journal = Lecture Notes, MSRI Workshop on Quantum Computation | year = 2002 | author = Peter Shor | title = The quantum channel capacity and coherent information | url = http://www.msri.org/publications/ln/msri/2002/quantumcrypto/shor/1/meta/aux/shor.pdf }}</ref> and Igor Devetak<ref name="Devetak2005">{{cite journal | journal = IEEE Transactions on Information Theory | volume = 51 | pages = 44–55 | year = 2005 | author = Igor Devetak | title = The private classical capacity and quantum capacity of a quantum channel | issue = 1 | doi = 10.1109/TIT.2004.839515 | arxiv = quant-ph/0304127| bibcode = 2005ITIT...51...44D | s2cid = 12246393 }}</ref> who proved it with increasing standards of rigor.<ref>{{Cite book |last=Wilde |first=Mark M. |title=Quantum information theory |date=2017 |isbn=978-1-316-80997-6 |edition=2nd |location=Cambridge, UK |oclc=972292559}}</ref>

== Hashing bound for Pauli channels ==

The LSD theorem states that the coherent information of a quantum channel is an achievable rate for reliable quantum communication. For a Pauli channel, the coherent information has a simple form{{Citation needed|date=April 2015}} and the proof that it is achievable is particularly simple as well. We{{Who|date=October 2017}} prove the theorem for this special case by exploiting random stabilizer codes and correcting only the likely errors that the channel produces.

'''Theorem''' (hashing bound). There exists a stabilizer quantum error-correcting code that achieves the hashing limit <math>R=1-H\left(\mathbf{p}\right)</math> for a Pauli channel of the following form:<math display="block"> \rho \mapsto p_{I}\rho+p_{X}X\rho X+p_{Y}Y\rho Y+p_{Z}Z\rho Z, </math>where <math>\mathbf{p}=\left(p_{I},p_{X},p_{Y},p_{Z}\right)</math> and <math>H\left(\mathbf{p}\right)</math> is the entropy of this probability vector.

'''Proof'''. Consider correcting only the typical errors. That is, consider defining the typical set of errors as follows:<math display="block"> T_{\delta}^{\mathbf{p}^{n}}\equiv\left\{ a^{n}:\left\vert -\frac{1}{n} \log_{2}\left( \Pr\left\{ E_{a^{n}}\right\} \right) -H\left( \mathbf{p}\right) \right\vert \leq\delta\right\} ,</math>where <math>a^{n}</math> is some sequence consisting of the letters <math>\left\{I,X,Y,Z\right\}</math> and <math>\Pr\left\{E_{a^{n}}\right\}</math> is the probability that an IID Pauli channel issues some tensor-product error <math>E_{a^{n}}\equiv E_{a_{1}}\otimes\cdots\otimes E_{a_{n}}</math>. This typical set consists of the likely errors in the sense that<math display="block"> \sum_{a^{n}\in T_{\delta}^{\mathbf{p}^{n}}}\Pr\left\{E_{a^{n}}\right\} \geq 1-\epsilon, </math>for all <math>\epsilon>0</math> and sufficiently large <math>n</math>. The error-correcting conditions<ref name="NC">{{citation | last1 = Nielsen | first1 = Michael A. | author1-link = Michael Nielsen | last2 = Chuang | first2 = Isaac L. | author2-link = Isaac Chuang | title = Quantum Computation and Quantum Information | publisher = Cambridge University Press | date = 2000 | isbn = 978-0-521-63503-5}}.</ref> for a stabilizer code <math>\mathcal{S}</math> in this case are that <math>\{E_{a^{n}}:a^{n}\in T_{\delta}^{\mathbf{p}^{n}}\}</math> is a correctable set of errors if

<math display="block"> E_{a^{n}}^{\dagger}E_{b^{n}}\notin N\left(\mathcal{S}\right) \backslash \mathcal{S}, </math>for all error pairs <math>E_{a^{n}}</math> and <math>E_{b^{n}}</math> such that <math>a^{n},b^{n}\in T_{\delta}^{\mathbf{p}^{n}}</math> where <math>N(\mathcal{S})</math> is the normalizer of <math>\mathcal{S}</math>. Also, we consider the expectation of the error probability under a random choice of a stabilizer code.

Proceed as follows:<math display="block"> \begin{align} \mathbb{E}_{\mathcal{S}}\left\{p_{e}\right\} &= \mathbb{E}_{\mathcal{S}} \left\{ \sum_{a^{n}} \Pr \left\{ E_{a^{n}}\right\} \mathcal{I}\left(E_{a^{n}}\text{ is uncorrectable under }\mathcal{S}\right) \right\} \\ &\leq \mathbb{E}_{\mathcal{S}} \left\{ \sum_{a^{n} \in T_{\delta}^{\mathbf{p}^{n}}} \Pr\left\{E_{a^{n}}\right\} \mathcal{I}\left(E_{a^{n}}\text{ is uncorrectable under }\mathcal{S}\right) \right\} + \epsilon \\ &= \sum_{a^{n} \in T_{\delta}^{\mathbf{p}^{n}}} \Pr\left\{E_{a^{n}}\right\} \mathbb{E}_{\mathcal{S}} \left\{ \mathcal{I}\left(E_{a^{n}}\text{ is uncorrectable under }\mathcal{S}\right) \right\} + \epsilon \\ &= \sum_{a^{n} \in T_{\delta}^{\mathbf{p}^{n}}} \Pr\left\{E_{a^{n}}\right\} \Pr_{\mathcal{S}} \left\{E_{a^{n}}\text{ is uncorrectable under }\mathcal{S}\right\} + \epsilon. \end{align} </math>The first equality follows by definition—<math>\mathcal{I}</math> is an indicator function equal to one if <math>E_{a^{n}}</math> is uncorrectable under <math>\mathcal{S}</math> 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:<math display="block"> =\sum_{a^{n}\in T_{\delta}^{\mathbf{p}^{n}}}\Pr\left\{ E_{a^{n}}\right\} \Pr_{\mathcal{S}}\left\{ \exists E_{b^{n}}:b^{n}\in T_{\delta}^{\mathbf{p} ^{n}},\ b^{n}\neq a^{n},\ E_{a^{n}}^{\dagger}E_{b^{n}}\in N\left( \mathcal{S} \right) \backslash\mathcal{S}\right\} </math> :<math> \leq\sum_{a^{n}\in T_{\delta}^{A^{n}}}\Pr\left\{ E_{a^{n}}\right\} \Pr_{\mathcal{S}}\left\{ \exists E_{b^{n}}:b^{n}\in T_{\delta}^{\mathbf{p} ^{n}},\ b^{n}\neq a^{n},\ E_{a^{n}}^{\dagger}E_{b^{n}}\in N\left( \mathcal{S} \right) \right\} </math> :<math> =\sum_{a^{n}\in T_{\delta}^{\mathbf{p}^{n}}}\Pr\left\{ E_{a^{n}}\right\} \Pr_{\mathcal{S}}\left\{ \bigcup\limits_{b^{n}\in T_{\delta}^{\mathbf{p}^{n} },\ b^{n}\neq a^{n}}E_{a^{n}}^{\dagger}E_{b^{n}}\in N\left( \mathcal{S}\right) \right\} </math> :<math> \leq\sum_{a^{n},b^{n}\in T_{\delta}^{\mathbf{p}^{n}},\ b^{n}\neq a^{n}} \Pr\left\{ E_{a^{n}}\right\} \Pr_{\mathcal{S}}\left\{ E_{a^{n}}^{\dagger }E_{b^{n}}\in N\left( \mathcal{S}\right) \right\} </math> :<math> \leq\sum_{a^{n},b^{n}\in T_{\delta}^{\mathbf{p}^{n}},\ b^{n}\neq a^{n}} \Pr\left\{ E_{a^{n}}\right\} 2^{-\left( n-k\right) }</math> :<math> \leq2^{2n\left[ H\left( \mathbf{p}\right) +\delta\right] }2^{-n\left[ H\left( \mathbf{p}\right) +\delta\right] }2^{-\left( n-k\right) }</math> :<math> =2^{-n\left[ 1-H\left( \mathbf{p}\right) -k/n-3\delta\right] }. </math> The first equality follows from the error-correcting conditions for a quantum stabilizer code, where <math>N\left( \mathcal{S}\right) </math> is the normalizer of <math>\mathcal{S}</math>. The first inequality follows by ignoring any potential degeneracy in the code—we consider an error uncorrectable if it lies in the normalizer <math>N\left( \mathcal{S}\right) </math> and the probability can only be larger because <math>N\left( \mathcal{S}\right) \backslash\mathcal{S}\in N\left( \mathcal{S}\right) </math>. 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 <math>E_{a^{n}}^{\dagger}E_{b^{n}}</math> not equal to the identity commuting with the stabilizer operators of a random stabilizer can be upper bounded as follows: <math> \Pr_{\mathcal{S}}\left\{ E_{a^{n}}^{\dagger}E_{b^{n}}\in N\left( \mathcal{S} \right) \right\} =\frac{2^{n+k}-1}{2^{2n}-1}\leq2^{-\left( n-k\right) }. </math> The reasoning here is that the random choice of a stabilizer code is equivalent to fixing operators <math>Z_{1}</math>, ..., <math>Z_{n-k}</math> and performing a uniformly random Clifford unitary. The probability that a fixed operator commutes with <math>\overline{Z}_{1}</math>, ..., <math>\overline{Z}_{n-k}</math> is then just the number of non-identity operators in the normalizer (<math>2^{n+k}-1</math>) divided by the total number of non-identity operators (<math>2^{2n}-1</math>). After applying the above bound, we then exploit the following typicality bounds: <math display="block"> \forall a^{n} \in T_{\delta}^{\mathbf{p}^{n}}:\Pr\left\{ E_{a^{n} }\right\} \leq2^{-n\left[ H\left( \mathbf{p}\right) +\delta\right] },</math><math display="block">\left\vert T_{\delta}^{\mathbf{p}^{n}}\right\vert \leq2^{n\left[ H\left( \mathbf{p}\right) +\delta\right] }. </math> We conclude that as long as the rate <math>k/n=1-H\left( \mathbf{p}\right) -4\delta</math>, 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.

The hashing bound is also used as a benchmark for explicit quantum error-correcting code constructions. In 2025, Daiki Komoto and Kenta Kasai reported low-density parity-check CSS codes for the depolarizing channel whose numerical decoding performance approached the hashing bound while using a sum-product decoder with computational cost linear in the number of physical qubits.<ref>{{cite journal |last1=Komoto |first1=Daiki |last2=Kasai |first2=Kenta |title=Quantum error correction near the coding theoretical bound |journal=npj Quantum Information |volume=11 |article-number=154 |year=2025 |doi=10.1038/s41534-025-01090-1 |doi-access=free}}</ref>

== See also == * Quantum computing

== References == <references />{{quantum computing}}

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