Eulerian number

Template:Cleanup The theory of quantum error correction plays a prominent role in the practical realization and engineering of quantum computing and quantum communication devices. The first quantum error-correcting codes are strikingly similar to classical block codes in their operation and performance. Quantum error-correcting codes restore a noisy, decohered quantum state to a pure quantum state. A stabilizer quantum error-correcting code appends ancilla qubits to qubits that we want to protect. A unitary encoding circuit rotates the global state into a subspace of a larger Hilbert space. This highly entangled, encoded state corrects for local noisy errors. A quantum error-correcting code makes quantum computation and quantum communication practical by providing a way for a sender and receiver to simulate a noiseless qubit channel given a noisy qubit channel that has a particular error model.

The stabilizer theory of quantum error correction allows one to import some classical binary or quaternary codes for use as a quantum code. The only "catch" when importing is that the classical code must satisfy the dual-containing or self-orthogonality constraint. Researchers have found many examples of classical codes satisfying this constraint, but most classical codes do not. Nevertheless, it is still useful to import classical codes in this way (though, see how the entanglement-assisted stabilizer formalism overcomes this difficulty).

Mathematical background

The Stabilizer formalism exploits elements of the Pauli group $\mathrm{\Pi }$ in formulating quantum error-correcting codes. The set $\mathrm{\Pi }=\{I,X,Y,Z\}$ consists of the Pauli operators:

$I\equiv \left[\begin{array}{cc}1& 0\\ 0& 1\end{array}\right],X\equiv \left[\begin{array}{cc}0& 1\\ 1& 0\end{array}\right],Y\equiv \left[\begin{array}{cc}0& -i\\ i& 0\end{array}\right],Z\equiv \left[\begin{array}{cc}1& 0\\ 0& -1\end{array}\right].$

The above operators act on a single qubit---a state represented by a vector in a two-dimensional Hilbert space. Operators in $\mathrm{\Pi }$ have eigenvalues $\pm 1$ and either commute or anti-commute. The set ${\mathrm{\Pi }}^n$ consists of $n$-fold tensor products of Pauli operators:

${\mathrm{\Pi }}^n=\left\{\begin{array}{c}{e}^{i\varphi }{A}_1\otimes \cdots \otimes A_n:\mathrm{\forall }j\in \{1,\dots ,n\}{A}_j\in \mathrm{\Pi },\varphi \in \{0,\pi /2,\pi ,3\pi /2\}\end{array}\right\}.$

Elements of ${\mathrm{\Pi }}^n$ act on a quantum register of $n$ qubits. We occasionally omit tensor product symbols in what follows so that

$A_1\cdots A_n\equiv A_1\otimes \cdots \otimes A_n.$

The $n$-fold Pauli group ${\mathrm{\Pi }}^n$ plays an important role for both the encoding circuit and the error-correction procedure of a quantum stabilizer code over $n$ qubits.

Definition

Let us define an $[n,k]$ stabilizer quantum error-correcting code to encode $k$ logical qubits into $n$ physical qubits. The rate of such a code is $k/n$. Its stabilizer $\mathcal{𝒮}$ is an abelian subgroup of the $n$-fold Pauli group ${\mathrm{\Pi }}^n$: $\mathcal{𝒮}\subset {\mathrm{\Pi }}^n$. $\mathcal{𝒮}$ does not contain the operator $-I^{\otimes n}$. The simultaneous $+1$-eigenspace of the operators constitutes the codespace. The codespace has dimension $2^k$ so that we can encode $k$ qubits into it. The stabilizer $\mathcal{𝒮}$ has a minimal representation in terms of $n-k$ independent generators

$\{g_1,\dots ,g_{n-k}|\mathrm{\forall }i\in \{1,\dots ,n-k\},g_i\in \mathcal{𝒮}\}.$

The generators are independent in the sense that none of them is a product of any other two (up to a global phase). The operators $g_1,\dots ,g_{n-k}$ function in the same way as a parity check matrix does for a classical linear block code.

Stabilizer error-correction conditions

One of the fundamental notions in quantum error correction theory is that it suffices to correct a discrete error set with support in the Pauli group ${\mathrm{\Pi }}^n$. Suppose that the errors affecting an encoded quantum state are a subset $\mathcal{ℰ}$ of the Pauli group ${\mathrm{\Pi }}^n$:

$\mathcal{ℰ}\subset {\mathrm{\Pi }}^n.$

An error $E\in \mathcal{ℰ}$ that affects an encoded quantum state either commutes or anticommutes with any particular element $g$ in $\mathcal{𝒮}$. The error $E$ is correctable if it anticommutes with an element $g$ in $\mathcal{𝒮}$. An anticommuting error $E$ is detectable by measuring each element $g$ in $\mathcal{𝒮}$ and computing a syndrome $\mathbf{r}$ identifying $E$. The syndrome is a binary vector $\mathbf{r}$ with length $n-k$ whose elements identify whether the error $E$ commutes or anticommutes with each $g\in \mathcal{𝒮}$. An error $E$ that commutes with every element $g$ in $\mathcal{𝒮}$ is correctable if and only if it is in $\mathcal{𝒮}$. It corrupts the encoded state if it commutes with every element of $\mathcal{𝒮}$ but does not lie in $\mathcal{𝒮}$. So we compactly summarize the stabilizer error-correcting conditions: a stabilizer code can correct any errors $E_1,E_2$ in $\mathcal{ℰ}$ if

$E_1^{†}{E}_2\notin \mathcal{𝒵}\left(\mathcal{𝒮}\right)$

or

$E_1^{†}{E}_2\in \mathcal{𝒮}$

where $\mathcal{𝒵}\left(\mathcal{𝒮}\right)$ is the centralizer of $\mathcal{𝒮}$.

Relation between Pauli group and binary vectors

A simple but useful mapping exists between elements of $\mathrm{\Pi }$ and the binary vector space ${\left({\mathbb{\mathbb{Z}}}_2\right)}^2$. This mapping gives a simplification of quantum error correction theory. It represents quantum codes with binary vectors and binary operations rather than with Pauli operators and matrix operations respectively.

We first give the mapping for the one-qubit case. Suppose $\left[A\right]$ is a set of equivalence classes of an operator $A$ that have the same phase:

$\left[A\right]=\left\{\beta A\right|\beta \in \mathbb{ℂ},\left|\beta \right|=1\}.$

Let $\left[\mathrm{\Pi }\right]$ be the set of phase-free Pauli operators where $\left[\mathrm{\Pi }\right]=\left\{\left[A\right]\right|A\in \mathrm{\Pi }\}$. Define the map $N:{\left({\mathbb{\mathbb{Z}}}_2\right)}^2\to \mathrm{\Pi }$ as

$00\to I,01\to X,11\to Y,10\to Z$

Suppose $u,v\in {\left({\mathbb{\mathbb{Z}}}_2\right)}^2$. Let us employ the shorthand $u=\left(z\right|x)$ and $v=\left(z^{\prime }\right|x^{\prime })$ where $z$, $x$, $z^{\prime }$, $x^{\prime }\in {\mathbb{\mathbb{Z}}}_2$. For example, suppose $u=\left(0\right|1)$. Then $N\left(u\right)=X$. The map $N$ induces an isomorphism $\left[N\right]:{\left({\mathbb{\mathbb{Z}}}_2\right)}^2\to \left[\mathrm{\Pi }\right]$ because addition of vectors in ${\left({\mathbb{\mathbb{Z}}}_2\right)}^2$ is equivalent to multiplication of Pauli operators up to a global phase:

$\left[N(u+v)\right]=\left[N\left(u\right)\right]\left[N\left(v\right)\right].$

Let $\odot$ denote the symplectic product between two elements $u,v\in {\left({\mathbb{\mathbb{Z}}}_2\right)}^2$:

$u\odot v\equiv z{x}^{\prime }-x{z}^{\prime }.$

The symplectic product $\odot$ gives the commutation relations of elements of $\mathrm{\Pi }$:

$N\left(u\right)N\left(v\right)={(-1)}^{(u\odot v)}N\left(v\right)N\left(u\right).$

The symplectic product and the mapping $N$ thus give a useful way to phrase Pauli relations in terms of binary algebra. The extension of the above definitions and mapping $N$ to multiple qubits is straightforward. Let $\mathbf{A}=A_1\otimes \cdots \otimes A_n$ denote an arbitrary element of ${\mathrm{\Pi }}^n$. We can similarly define the phase-free $n$-qubit Pauli group $\left[{\mathrm{\Pi }}^n\right]=\left\{\left[\mathbf{A}\right]\right|\mathbf{A}\in {\mathrm{\Pi }}^n\}$ where

$\left[\mathbf{A}\right]=\left\{\beta \mathbf{A}\right|\beta \in \mathbb{ℂ},\left|\beta \right|=1\}.$

The group operation $\ast$ for the above equivalence class is as follows:

$\left[\mathbf{A}\right]\ast \left[\mathbf{B}\right]\equiv \left[A_1\right]\ast \left[B_1\right]\otimes \cdots \otimes \left[A_n\right]\ast \left[B_n\right]=\left[A_1{B}_1\right]\otimes \cdots \otimes \left[A_n{B}_n\right]=\left[\mathbf{A}\mathbf{B}\right].$

The equivalence class $\left[{\mathrm{\Pi }}^n\right]$ forms a commutative group under operation $\ast$. Consider the $2n$-dimensional vector space

${\left({\mathbb{\mathbb{Z}}}_2\right)}^{2n}=\{\left(\mathbf{z},\mathbf{x}\right):\mathbf{z},\mathbf{x}\in {\left({\mathbb{\mathbb{Z}}}_2\right)}^n\}.$

It forms the commutative group $({\left({\mathbb{\mathbb{Z}}}_2\right)}^{2n},+)$ with operation $+$ defined as binary vector addition. We employ the notation $\mathbf{u}=\left(\mathbf{z}\right|\mathbf{x}),\mathbf{v}=\left({\mathbf{z}}^{\prime }\right|{\mathbf{x}}^{\prime })$ to represent any vectors $\mathbf{u},\mathbf{v}\in {\left({\mathbb{\mathbb{Z}}}_2\right)}^{2n}$ respectively. Each vector $\mathbf{z}$ and $\mathbf{x}$ has elements $(z_1,\dots ,z_n)$ and $(x_1,\dots ,x_n)$ respectively with similar representations for ${\mathbf{z}}^{\prime }$ and ${\mathbf{x}}^{\prime }$. The symplectic product $\odot$ of $\mathbf{u}$ and $\mathbf{v}$ is

$\mathbf{u}\odot \mathbf{v}\mathbf{\equiv }\sum _{i=1}^n{z}_i{x}_i^{\prime }-x_i{z}_i^{\prime },$

or

$\mathbf{u}\odot \mathbf{v}\mathbf{\equiv }\sum _{i=1}^n{u}_i\odot v_i,$

where $u_i=\left(z_i\right|x_i)$ and $v_i=\left(z_i^{\prime }\right|x_i^{\prime })$. Let us define a map $\mathbf{N}:{\left({\mathbb{\mathbb{Z}}}_2\right)}^{2n}\to {\mathrm{\Pi }}^n$ as follows:

$\mathbf{N}\left(\mathbf{u}\right)\equiv N\left(u_1\right)\otimes \cdots \otimes N\left(u_n\right).$

Let

$\mathbf{X}\left(\mathbf{x}\right)\equiv X^{x_1}\otimes \cdots \otimes X^{x_n},\mathbf{Z}\left(\mathbf{z}\right)\equiv Z^{z_1}\otimes \cdots \otimes Z^{z_n},$

so that $\mathbf{N}\left(\mathbf{u}\right)$ and $\mathbf{Z}\left(\mathbf{z}\right)\mathbf{X}\left(\mathbf{x}\right)$ belong to the same equivalence class:

$\left[\mathbf{N}\left(\mathbf{u}\right)\right]=\left[\mathbf{Z}\left(\mathbf{z}\right)\mathbf{X}\left(\mathbf{x}\right)\right].$

The map $\left[\mathbf{N}\right]:{\left({\mathbb{\mathbb{Z}}}_2\right)}^{2n}\to \left[{\mathrm{\Pi }}^n\right]$ is an isomorphism for the same reason given as the previous case:

$\left[\mathbf{N}\left(\mathbf{u}+\mathbf{v}\right)\right]=\left[\mathbf{N}\left(\mathbf{u}\right)\right]\left[\mathbf{N}\left(\mathbf{v}\right)\right],$

where $\mathbf{u},\mathbf{v}\in {\left({\mathbb{\mathbb{Z}}}_2\right)}^{2n}$. The symplectic product captures the commutation relations of any operators $\mathbf{N}\left(\mathbf{u}\right)$ and $\mathbf{N}\left(\mathbf{v}\right)$:

$\mathbf{N}\left(\mathbf{u}\right)\mathbf{N}\left(\mathbf{v}\right)={(-1)}^{(\mathbf{u}\odot \mathbf{v})}\mathbf{N}\left(\mathbf{v}\right)\mathbf{N}\left(\mathbf{u}\right).$

The above binary representation and symplectic algebra are useful in making the relation between classical linear error correction and quantum error correction more explicit.

Example of a stabilizer code

An example of a stabilizer code is the five qubit $[5,1]$ stabilizer code. It encodes $k=1$ logical qubit into $n=5$ physical qubits and protects against an arbitrary single-qubit error. Its stabilizer consists of $n-k=4$ Pauli operators:

$\begin{array}{ccccccc}{g}_1& =& X& Z& Z& X& I\\ g_2& =& I& X& Z& Z& X\\ g_3& =& X& I& X& Z& Z\\ g_4& =& Z& X& I& X& Z\end{array}$

The above operators commute. Therefore the codespace is the simultaneous +1-eigenspace of the above operators. Suppose a single-qubit error occurs on the encoded quantum register. A single-qubit error is in the set $\{X_i,Y_i,Z_i\}$ where $A_i$ denotes a Pauli error on qubit $i$. It is straightforward to verify that any arbitrary single-qubit error has a unique syndrome. The receiver corrects any single-qubit error by identifying the syndrome and applying a corrective operation.

References

• D. Gottesman, "Stabilizer codes and quantum error correction," quant-ph/9705052, Caltech Ph.D. thesis. http://arxiv.org/abs/quant-ph/9705052
• P. W. Shor, “Scheme for reducing decoherence in quantum computer memory,” Phys. Rev. A, vol. 52, no. 4, pp. R2493–R2496, Oct 1995.
• A. R. Calderbank and P. W. Shor, “Good quantum error-correcting codes exist,” Phys. Rev. A, vol. 54, no. 2, pp. 1098–1105, Aug 1996. Available at http://arxiv.org/abs/quant-ph/9512032
• A. M. Steane, “Error correcting codes in quantum theory,” Phys. Rev. Lett., vol. 77, no. 5, pp. 793–797, Jul 1996.
• A. Calderbank, E. Rains, P. Shor, and N. Sloane, “Quantum error correction via codes over GF(4),” IEEE Trans. Inf. Theory, vol. 44, pp. 1369–1387, 1998. Available at http://arxiv.org/abs/quant-ph/9608006

Template:Quantum computing