Quantum capacity

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 $R=1-H\backslash left(\backslash mathbf\{p\}\backslash right)$ for a Pauli channel of the following form:$$$$

\rho \mapsto p_{I}\rho+p_{X}X\rho X+p_{Y}Y\rho Y+p_{Z}Z\rho Z,

where $\backslash mathbf\{p\}=\backslash left(p\_\{I\},p\_\{X\},p\_\{Y\},p\_\{Z\}\backslash right)$ and $H\backslash left(\backslash mathbf\{p\}\backslash right)$ 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:$$$$

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\} ,where $a^\{n\}$ is some sequence consisting of the letters $\backslash left\backslash \{I,X,Y,Z\backslash right\backslash \}$ and $\backslash Pr\backslash left\backslash \{E\_\{a^\{n\}\}\backslash right\backslash \}$ is the probability that an IID Pauli channel issues some tensor-product error $E\_\{a^\{n\}\}\backslash equiv$

E_{a_{1}}\otimes\cdots\otimes E_{a_{n}}. This typical set consists of the likely errors in the sense that$$$$

\sum_{a^{n}\in T_{\delta}^{\mathbf{p}^{n}}}\Pr\left\{E_{a^{n}}\right\} \geq 1-\epsilon,

for all $\backslash epsilon>0$ and sufficiently large $n$. The error-correcting

conditions{{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}}. for a stabilizer code $\backslash mathcal\{S\}$ in this case are that $\backslash \{E\_\{a^\{n\}\}:a^\{n\}\backslash in\; T\_\{\backslash delta\}^\{\backslash mathbf\{p\}^\{n\}\}\backslash \}$ is a correctable set of errors if

E_{a^{n}}^{\dagger}E_{b^{n}}\notin N\left(\mathcal{S}\right) \backslash \mathcal{S},

for all error pairs $E\_\{a^\{n\}\}$ and $E\_\{b^\{n\}\}$ such that $a^\{n\},b^\{n\}\backslash in$

T_{\delta}^{\mathbf{p}^{n}} where $N(\backslash mathcal\{S\})$ is the normalizer of $\backslash mathcal\{S\}$. Also, we consider the expectation of the error probability under a random choice of a stabilizer code.

Proceed as follows:$$$$

\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}

The first equality follows by definition—$\backslash mathcal\{I\}$ is an indicator function equal to one if $E\_\{a^\{n\}\}$ is uncorrectable under $\backslash 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:$$$$

=\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\}

:$\backslash leq\backslash sum\_\{a^\{n\}\backslash in\; T\_\{\backslash delta\}^\{A^\{n\}\}\}\backslash Pr\backslash left\backslash \{\; E\_\{a^\{n\}\}\backslash right\backslash \}$

\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\}

:$=\backslash sum\_\{a^\{n\}\backslash in\; T\_\{\backslash delta\}^\{\backslash mathbf\{p\}^\{n\}\}\}\backslash Pr\backslash left\backslash \{\; E\_\{a^\{n\}\}\backslash right\backslash \}$

\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\}

:$\backslash leq\backslash sum\_\{a^\{n\},b^\{n\}\backslash in\; T\_\{\backslash delta\}^\{\backslash mathbf\{p\}^\{n\}\},\backslash \; b^\{n\}\backslash 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\}

:$\backslash leq\backslash sum\_\{a^\{n\},b^\{n\}\backslash in\; T\_\{\backslash delta\}^\{\backslash mathbf\{p\}^\{n\}\},\backslash \; b^\{n\}\backslash neq\; a^\{n\}\}$

\Pr\left\{ E_{a^{n}}\right\} 2^{-\left( n-k\right) }

:$\backslash leq2^\{2n\backslash left[\; H\backslash left(\; \backslash mathbf\{p\}\backslash right)\; +\backslash delta\backslash right]\; \}2^\{-n\backslash left[$

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

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

The first equality follows from the error-correcting conditions for a quantum stabilizer code, where $N\backslash left(\; \backslash mathcal\{S\}\backslash right)$ is the normalizer of

$\backslash 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 $N\backslash left(\; \backslash mathcal\{S\}\backslash right)$ and the probability can only be larger because $N\backslash left(\; \backslash mathcal\{S\}\backslash right)\; \backslash backslash\backslash mathcal\{S\}\backslash in\; N\backslash 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 $E\_\{a^\{n\}\}^\{\backslash dagger\}E\_\{b^\{n\}\}$ not equal to the identity commuting with

the stabilizer operators of a random stabilizer can be upper bounded as follows:

\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) }.

The reasoning here is that the random choice of a stabilizer code is equivalent to

fixing operators $Z\_\{1\}$, ..., $Z\_\{n-k\}$ and performing a uniformly random

Clifford unitary. The probability that a fixed operator commutes with

$\backslash overline\{Z\}\_\{1\}$, ..., $\backslash overline\{Z\}\_\{n-k\}$ is then just the number of

non-identity operators in the normalizer ($2^\{n+k\}-1$) divided by the total number of non-identity operators ($2^\{2n\}-1$). After applying the above bound, we then exploit the following typicality bounds:

\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] },$$\backslash left\backslash vert\; T\_\{\backslash delta\}^\{\backslash mathbf\{p\}^\{n\}\}\backslash right\backslash vert\; \backslash leq2^\{n\backslash left[\; H\backslash left($$

\mathbf{p}\right) +\delta\right] }.

We conclude that as long as the rate $k/n=1-H\backslash left(\; \backslash mathbf\{p\}\backslash 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 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