Lecture notes on quantum entanglement: From stabilizer states to stabilizer channels

Abstract

We study mathematical, physical and computational aspects of the stabilizer formalism arising in quantum information and quantum computation. The measurement process of Pauli observables with its algorithm is given. It is shown that to detect genuine entanglement we need a full set of stabilizer generators and the stabilizer witness is coarser than the GHZ (Greenberger–Horne–Zeilinger) witness. We discuss stabilizer codes and construct a stabilizer code from a given linear code. We also discuss quantum error correction, error recovery criteria and syndrome extraction. The symplectic structure of the stabilizer formalism is established and it is shown that any stabilizer code is unitarily equivalent to a trivial code. The structure of graph codes as stabilizer codes is identified by obtaining the respective stabilizer generators. The distance of embeddable stabilizer codes in lattices is obtained. We discuss the Knill−Gottesman theorem, tableau representation and frame representation. The runtime of simulating stabilizer gates is obtained by applying stabilizer matrices. Furthermore, an algorithm for updating global phases is given. Resolution of quantum channels into stabilizer channels is shown. We discuss capacity achieving codes to obtain the capacity of the quantum erasure channel. Finally, we discuss the shadow tomography problem and an algorithm for constructing classical shadow is given.

Graphical abstract

Keywords

Pauli product / stabilizer state / measurement process / entanglement detection / stabilizer code / stabilizer circuit / quantum channel / tomography

1 Introduction

The stabilizer formalism was originally introduced to describe quantum error-correcting codes [1], but now plays many different roles in quantum information and quantum computation. The key idea of this formalism is that quantum states can be represented by operators that stabilize them. A quantum system is fully described by a quantum state, which is viewed as a mathematical object. The description of quantum states is a complicated task, because we need exponentially many parameters in the number of qubits [2]. The stabilizer formalism is a powerful tool to describe a considerable class of entangled states.

One of the challenges facing quantum computation and other attempts to create specific highly entangled states is decoherence and controlling operational errors. A subclass of quantum codes, the stabilizer codes, has developed based on a group theoretical approach to meet this challenge [3]. A stabilizer quantum error-correcting code encodes logical qubits into physical qubits. In other words, a stabilizer code appends ancilla qubits to qubits that we want to protect. Stabilizer codes have found a wide range of applications, for instance, decoherence-free stabilizer codes are constructed for open quantum systems [4] and stabilizer codes are related to Lorentzian lattices and non-chiral CFTs [5].

An $n$-qubit stabilizer state is the simultaneous +1 eigenvector of $n$ independent, commuting elements of the Pauli group. A graph state is a special type of multi-qubit state that can be represented by a graph. Stabilizer states and graph states have applications in quantum error correction and form a universal resource for measurement-based quantum computation [6]. The class of stabilizer states is rich enough to be considered useful in almost all applications of quantum networks. For example, the GHZ-state is seen in many quantum protocols [7]. Some of these applications include quantum secret sharing [8], conference key agreement [9], anonymous transfer [10] and clock synchronization [11].

A stabilizer circuit is a quantum circuit in which every gate is a controlled-NOT, Hadamard, phase, or 1-qubit measurement gate. Stabilizer circuits can be applied to create highly entangled states. They also perform the encoding and decoding steps for quantum error-correcting codes. They also play a central role in fault-tolerant circuits [12]. The stabilizer formalism enables us to encompass most of the paradoxes of quantum mechanics including dense quantum coding [13], the GHZ experiment [14] and quantum teleportation [15]. However, the Knill−Gottesman theorem allows such circuits to be simulated classically with an efficient runtime [16].

This paper is devoted to the description of the stabilizer formalism and its applications arising in quantum information and quantum computation. This paper is organized as follows. In Section 2, we provide basic definitions and lemmas on stabilizer states, binary representation and Clifford group. In Section 3, we study the measurement process of a Pauli observable by using the projective measurement and give the respective algorithm based on stabilizer generators. In Section 4, we introduce two fundamental concepts of “entanglement detection” and “entanglement witness”. Then it is shown that the stabilizer witness is coarser than the GHZ witness by applying the GHZ basis and methods of operator theory. Furthermore, it is shown that to detect genuine entanglement by stabilizer witness we need a full set of stabilizer generators. In this way, we apply methods of standard linear algebra. In Section 5, we give basic definitions and important instances of stabilizer codes, then a stabilizer code is constructed from a given classical linear code. We discuss Pauli errors, error-correcting codes and the process of syndrome extraction. The symplectic structure of the stabilizer formalism is established and it is shown that any stabilizer code with $k$ logical qubits is unitarily equivalent to a $k$-trivial stabilizer code. Two equivalent definitions of graph states are given. Graph codes associated with linear codes are characterized and it is shown that any graph code is a stabilizer code by identifying its stabilizer generators. The cleaning lemma based on independent logical operators is shown and the distance of an embeddable code in a lattice is obtained. Generalization of stabilizer codes and Clifford group is given. In Section 6, stabilizer gates are introduced and their simulating runtime is obtained by applying stabilizer matrices. The Knill−Gottesman theorem, tableau representation and frame representation are discussed. The runtime of resolution of a Pauli group element into production of a stabilizer state and a destabilizer state is obtained. The algorithm for updating global phases is given. In Section 7, we discuss stabilizer channels and their types including Pauli reset channels and Clifford channels. Resolution of a quantum channel into a sum of stabilizer channels is given. The key concept of negativity is discussed. The capacity of the quantum erasure channel is obtained by a class of capacity achieving stabilizer codes. In Section 8, we discuss shadow tomography problem and the framework of classical shadow estimation is given as an algorithm. And finally, in Section 9 we present some research lines.

2 Pauli products

The Pauli operators on a two-level quantum system $H\simeq {\mathbb{C}}^2$ (qubit) are defined as follows:

$\begin{array}{rl}& {\sigma }_0=I=\left(\begin{array}{cc}1& 0\\ 0& 1\end{array}\right),{\sigma }_x=X=\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right),\\ & {\sigma }_y=Y=\left(\begin{array}{cc}0& -\mathrm{i}\\ \mathrm{i}& 0\end{array}\right),{\sigma }_z=Z=\left(\begin{array}{cc}1& 0\\ 0& -1\end{array}\right),\end{array}$

where $H$ is the Hilbert space on which the operators act. The Pauli group $\mathcal{P}$ is defined as the group generated by the Pauli operators up to the phase factors $\pm 1$, $\pm \mathrm{i}$, i.e.,

$\mathcal{P}=⟨\{\pm 1,\pm \mathrm{i}\}\times \{I,X,Y,Z\}⟩.$

For $n$ qubits, the Pauli group is defined as

$\begin{array}{rl}{\mathcal{P}}_n={\mathcal{P}}^{\otimes n}=& \{{\mathrm{i}}^k{\sigma }_1\otimes {\sigma }_2\otimes ...\otimes {\sigma }_n:k\in \{0,1,2,3\},\\ & {\sigma }_j\in \{I,X,Y,Z\}\}.\end{array}$

Pauli operators on qubit $j$ form a basis for the operator space on a single qubit. Products of operators of this sort, called Pauli products, span the space of operators on $n$ qubits. If $u$ is an operator on $n$ qubits, its base is the set of qubits on which it acts nontrivially ($X$, $Y$, or $Z$). The weight $w(u)$ of $u$ is the number of qubits in its base. For example

$\begin{array}{rl}{X}_1{Z}_1{Z}_2{X}_3{Z}_5=& X_1{Z}_1\otimes Z_2\otimes X_3\otimes I_4\otimes Z_5\\ & \otimes I_6\otimes ...\otimes I_n,\end{array}$

has base $\{1,2,3,5\}$, so is of weight 4. Here, the index (of operators) indicates the Hilbert space (qubit) that the respective operator acts on.

2.1 Stabilizer states

A stabilizer $S$ of $n$ qubits is an Abelian subgroup of ${\mathcal{P}}_n$ that does not include $-I=-I^{\otimes n}$. Let $S=⟨g_1,g_2,...,g_k⟩$, where $g_j\in {\mathcal{P}}_n$ are commuting and independent (i.e., no one can be expressed as a product of other generators, up to a sign) generators. Every element of the Pauli group is either Hermitian operator or anti-Hermitian operator. Any Hermitian operator has order two, i.e., $g_j^2=g_j{g}_j^{†}=I$ where $g_j^{†}$ is the adjoint operator, and any anti-Hermitian operator has order four, i.e., $(\mathrm{i}{g}_j{)}^4=I$. Therefore, $S$ cannot contain anti-Hermitian operators as otherwise $-I\in S$. It shows that $|S|=2^k$. When $|S|=2^n$, there is a state $|\psi ⟩$ that is the common eigenvector of elements of $S$ and is called a stabilizer state. For example, the EPR (Einstein−Podolsky−Rosen) state $\frac{|00⟩+|11⟩}{\sqrt{2}}$ is a stabilizer state, because it is a +1 eigenvector of the stabilizer subgroup $⟨X\otimes X,Z\otimes Z⟩$. The stabilized subspace $V_S$ is defined as follows

$V_S=\{|\psi ⟩\in H^{\otimes n}:s|\psi ⟩=|\psi ⟩,\mathrm{\forall }s\in S\}.$

An $n$-qubit GHZ state is defined by $|GHZ⟩=$$\frac{1}{\sqrt{2}}(|0{⟩}^{\otimes n}+|1{⟩}^{\otimes n})$. In fact, the GHZ state is a +1 eigenvector of the following Pauli products:

${\mathfrak{g}}_1:=X_1{X}_2...X_n,{\mathfrak{g}}_k:=Z_{k-1}{Z}_k(k=2,...,n).$

In other words, ${\mathfrak{g}}_k|GHZ⟩=|GHZ⟩$ for $k=1,...,n$. Let $S=⟨{\mathfrak{g}}_1,{\mathfrak{g}}_2,...,{\mathfrak{g}}_n⟩$ be the stabilizer generated by ${\mathfrak{g}}_1,{\mathfrak{g}}_2,...,{\mathfrak{g}}_n$. Then $|S|=2^n$ and by letting $S=\{s_1,s_2,...,s_{2^n}\}$, we have

(1)$|GHZ⟩⟨GHZ|=2^{-n}{\displaystyle \sum _{k=1}^{2^n}{s}_k=2^{-n}{\displaystyle \prod _{k=1}^n(I+{\mathfrak{g}}_k).}}$

We will apply Eq. (1) in Section 4.

2.2 Binary representation

At each qubit we use the following encoding of the Pauli operators as pairs of bits:

$b(I)=(0|0),b(X)=(1|0),b(Y)=(1|1),b(Z)=(0|1).$

We can reconstruct the Pauli operators as follows:

(2)${\sigma }_j={\mathrm{i}}^{b_1({\sigma }_j)b_2({\sigma }_j)}{X}^{b_1({\sigma }_j)}{Z}^{b_2({\sigma }_j)},$

where $b({\sigma }_j)=(b_1({\sigma }_j)|b_2({\sigma }_j))$. By applying Eq. (2) it follows that

$b({\sigma }_j{\sigma }_k)=b({\sigma }_j)+b({\sigma }_k),$

(3)$b({\sigma }_j)J{b}^{\text{t}}({\sigma }_k)=\{\begin{array}{ll}0& \text{if}[{\sigma }_j,{\sigma }_k]=0,\\ 1& \text{if}\{{\sigma }_j,{\sigma }_k\}=0,\end{array}$

where $J=\left(\begin{array}{cc}\mathbf{0}& I\\ I& \mathbf{0}\end{array}\right)$, $[A,B]=AB-BA$, $\{A,B\}=AB+BA$, “t” is transposition and computations are done modulo 2. The left side of Eq. (3) is the symplectic inner product of the binary vectors. For example, using this notation, the Pauli product $u=X_1{Z}_2{Z}_5$ acting on $({\mathbb{C}}^2{)}^{\otimes 5}$ has the following encoding

$b(u)=(10000|01001)\in {\mathbb{F}}_2^{10},$

where ${\mathbb{F}}_2$ is the binary field.

Lemma 1. For every $u,v,w\in {\mathcal{P}}_n$ with corresponding binary vectors $b(u),b(v),b(w)\in {\mathbb{F}}_2^{2n},$ in encoding $b:{\mathcal{P}}_n\to {\mathbb{F}}_2^{2n}$,

i) $uv\sim w\iff b(u)+b(v)=b(w)$,

ii) $[u,v]=0\iff b(u)J{b}^{\text{t}}(v)=0$,

where ~ denotes equality up to a global phase.

Proof. It is derived from the following representation:

$u={\mathrm{i}}^{\sum _{j=1}^n[b_1(u){]}_j[b_2(u){]}_j}{\displaystyle \prod _{j=1}^n{X_j}^{[b_1(u){]}_j}{\displaystyle \prod _{j=1}^n{Z_j}^{[b_2(u){]}_j},}}$

where $b(u)=(b_1(u)|b_2(u))$.□

Remark 1. Property (i) shows that the encoding is a homomorphism of groups, and property (ii) shows that when two Pauli products commute. Throughout this paper, the phrase “up to a global phase” means that we can ignore global phases.

For a given set of Pauli products $u_1,u_2,...,u_r$, the $r\times 2n$ matrix

$G=\left(\begin{array}{c}b(u_1)\\ b(u_2)\\ .\\ .\\ .\\ b(u_r)\end{array}\right)$

is called the parity-check matrix corresponding to the Pauli products.

Corollary 1. A set of Pauli products $g_1,g_2,...,g_n$ with parity-check matrix $G$ are stabilizer generators of a stabilizer state if and only if the following conditions hold

i) $GJ{G}^{\text{t}}=\mathbf{0}$,

ii) $G$ has full rank.

Proof. It follows from Lemma 1.□

2.3 Clifford group

The Clifford group on $n$ qubits is defined as follows ${\mathcal{C}}_n=\{u\in U(2^n):u{\mathcal{P}}_n{u}^{†}={\mathcal{P}}_n\}$, where $U(2^n)$ is the unitary group of degree $2^n$. We take into account that the action of every $u\in {\mathcal{C}}_1$ is completely determined by the images of $X$ and $Z$, moreover $uX{u}^{†}$ and $uZ{u}^{†}$ must anti-commute. Then, $X$ can go to any element of $\{\pm X,\pm Y,\pm Z\}$ (since $\sigma$ is Hermitian if and only if $u\sigma u^{†}$ is Hermitian) and $Z$ can go to any element of $\{\pm X,\pm Y,\pm Z\}\setminus \{\pm uX{u}^{†}\}$. Therefore, including the global phase ${\mathcal{C}}_1$ has $8\times 24=128$ elements. In general, $|{\mathcal{C}}_n|=8\prod _{i=1}^{n}2(4^i-1)4^i$ [17]. We note that qubit $|q⟩=\text{cos}(\frac{\theta }{2})|0⟩+{\mathrm{e}}^{\mathrm{i}\phi }\text{sin}(\frac{\theta }{2})|1⟩$ on the Bloch sphere can be written as $\mathit{q}=(\text{sin}\theta \text{cos}\phi ,\text{sin}\theta \text{sin}\phi ,\text{cos}\theta )$. Let $\mathit{\sigma }=({\sigma }_x,{\sigma }_y,{\sigma }_z)$ and define

$\begin{array}{rl}{M}_q=\mathit{q}\cdot \mathit{\sigma }=& \text{sin}\theta \text{cos}\phi {\sigma }_x+\text{sin}\theta \text{sin}\phi {\sigma }_y+\text{cos}\theta {\sigma }_z\\ =& \left(\begin{array}{cc}\text{cos}\theta & {\mathrm{e}}^{-\mathrm{i}\phi }\text{sin}\theta \\ {\mathrm{e}}^{\mathrm{i}\phi }\text{sin}\theta & -\text{cos}\theta \end{array}\right).\end{array}$

A qubit rotation by angle $\alpha$ about the arbitrary axis $\hat{n}$ is written as a similarity transformation, i.e., $M_{q^{{}^{\prime }}}=U_{\hat{n}}(\alpha )M_q{U}_{\hat{n}}(\alpha {)}^{†}$, where $U_{\hat{n}}(\alpha )={\mathrm{e}}^{-\mathrm{i}\frac{\alpha }{2}\hat{n}\cdot \mathit{\sigma }}=\text{cos}(\frac{\alpha }{2})I-$$\mathrm{i}\text{sin}(\frac{\alpha }{2})(\hat{n}\cdot \mathit{\sigma })$. We can think of ${\mathcal{C}}_1$ as rotations of the Bloch sphere that permute $\pm x,\pm y,\pm z$ directions.

3 Measurement process

In this section, we study the process of measuring a Pauli observable, i.e., Hermitian Pauli group element, $O$ on a stabilizer state $|\psi ⟩$. We recall that the projective measurement described by $O$ is based on the decomposition $O=\sum _k{\lambda }_k{P}_k$, where $P_k$ is the projector onto the eigenvector of $O$ with eigenvalue ${\lambda }_k$. Upon measuring, the probability of getting result ${\lambda }_k$ is $p(k)=⟨\psi |P_k|\psi ⟩$. Given that outcome ${\lambda }_k$ occured, the post-measurement state is $\frac{P_k|\psi ⟩}{\sqrt{p(k)}}$.

Lemma 2. Adding an independent and commuting generator to the set of stabilizer generators cuts the stabilized subspace dimension in half.

Proof. Given a generator $g$,

${\left[{\displaystyle \frac{1}{2}}(I+g)\right]}^2={\displaystyle \frac{1}{4}}(I+2g+g^2)={\displaystyle \frac{1}{4}}(I+2g+I)={\displaystyle \frac{1}{2}}(I+g),$

thus $P_g=\frac{1}{2}(I+g)$ is a projector. We note that $P_g|\psi ⟩=|\psi ⟩$ if and only if $g|\psi ⟩=|\psi ⟩$, and $P_g|\psi ⟩=0$ if and only if $g|\psi ⟩=-|\psi ⟩$, thus $P_g$ is the projector onto $V_S$, where $S=⟨g⟩$ and

$\text{dim}{V}_S=\text{tr}{P}_g=\text{tr}\left[{\displaystyle \frac{1}{2}}(I+g)\right]=\text{tr}\left[{\displaystyle \frac{I}{2}}\right]=2^{n-1}.$

By adding an independent and commuting generator $h$ to $S$, we have

$P_g|\psi ⟩=|\psi ⟩,P_h|\psi ⟩=|\psi ⟩\iff P_g{P}_h|\psi ⟩=|\psi ⟩,$

and it means that the subspace stabilized by both $g$ and $h$ is of dimension $\text{tr}[P_g{P}_h]=2^{n-2}$. By induction on the number of generators of $S$, the proof is completed.□

Let $S=⟨g_1,g_2,...,g_n⟩$ be a set of stabilizer generators for $|\psi ⟩$. There are two cases:

Case I. For every $j$, $O$ commutes with $g_j$. From Lemma 1, it follows that $O$ cannot be independent of the generators in $S$. Hence, $O=(-1{)}^k{g}_1^{k_1}{g}_2^{k_2}...g_n^{k_n}$, where $k,k_j\in \{0,1\}$. Therefore,

$O|\psi ⟩=(-1{)}^k{g}_1^{k_1}{g}_2^{k_2}...g_n^{k_n}|\psi ⟩=(-1{)}^k|\psi ⟩,$

measurement $O$ gives result $(-1{)}^k$ with probability

$\begin{array}{rl}p((-1{)}^k)=& ⟨\psi |\frac{1}{2}(I+(-1{)}^{k}O)|\psi ⟩\\ =& \frac{1}{2}⟨\psi |\psi ⟩+\frac{(-1{)}^k(-1{)}^k}{2}⟨\psi |\psi ⟩=1,\end{array}$

and the post-measurement state is $\frac{1}{2}(I+(-1{)}^{k}O)|\psi ⟩=|\psi ⟩$.

Case II. There is a generator $g$ in $S$, such that $O$ anti-commutes with $g$. For a given generator $g_j$, $O$ either commutes with or anti-commutes with $g_j$. In the first case, we do not change $g_j$, but in the second case we construct a new set of generators as follows. We note that $Og{g}_j=-gO{g}_j=g{g}_{j}O$, then $g{g}_j$ is a generator that commutes with $O$. $g_j$ is replaced by $g{g}_j$ and it is also denoted by $g_j$. The action of $g_j$ on the (un-normalized) post-measurement state is

$\begin{array}{rl}{g}_j\left(\frac{1}{2}\right)[I+(-1{)}^{k}O]|\psi ⟩=& \frac{1}{2}[I+(-1{)}^{k}O]g_j|\psi ⟩\\ =& \frac{1}{2}[I+(-1{)}^{k}O]|\psi ⟩,\end{array}$

where $(-1{)}^k$ is the measurement outcome. Now, we only need one more independent stabilizer generator (instead of $g$) to characterize the post-measurement state completely. The key idea is that an $n-$qubit stabilizer state is uniquely determined by $n$ stabilizing operators. $O$ is the generator that is needed because, firstly, $O$ anti-commutes with $g$, so it is independent of all the generators. Furthermore, $(-1{)}^{k}O$ stabilizes the post-measurement state as follows:

$(-1{)}^{k}O\left({\displaystyle \frac{1}{2}}\right)[I+(-1{)}^{k}O]|\psi ⟩={\displaystyle \frac{1}{2}}[(-1{)}^{k}O+I]|\psi ⟩.$

This argument shows that by obtaining the measurement outcome $(-1{)}^k$, we reach stabilizer generators for the post-measurement state to be $g_j\ne g$ and $(-1{)}^{k}O$. The measurement outcomes are $\pm 1$ with equal probability, because

$\mathbb{E}(O)=⟨\psi |O|\psi ⟩=⟨\psi |Og|\psi ⟩=⟨\psi |-gO|\psi ⟩=-⟨\psi |O|\psi ⟩,$

or $⟨\psi |O|\psi ⟩=0$.

From this discussion, it results the following algorithm to measure a Pauli observable $O$ in a stabilizer state $|\psi ⟩$:

Algorithm 1. (Measurement process)

1) Find a set of stabilizer generators for $|\psi ⟩$ such that at most one generator anti-commutes with $O$.

2) If all the stabilizer generators commute with $O$, then the outcome will be certain and the post-measurement state will be $|\psi ⟩$.

3) If one generator, say $g$, anti-commutes with $O$, then outcome will be random and by replacing $g$ with $\pm O$ we reach a new set of generators that stabilize the post-measurement state.

In the following section, we present the method of entanglement witnesses as the most common entanglement detection tool.

4 Entanglement detection

Entangled state $|\psi ⟩$ describes a system made of two separable parts which cannot be written as a tensor product of states $|{\psi }_1⟩$ and $|{\psi }_2⟩$ describing separately each of the subsystems, i.e., $|\psi ⟩\ne |{\psi }_1⟩\otimes |{\psi }_2⟩$. A pure state is called biseparable, if it can be written as a tensor product of two multi-partite states $|\psi ⟩=|{\psi }_1⟩\otimes |{\psi }_2⟩$, we take into account that each of $|{\psi }_1⟩$ and $|{\psi }_2⟩$ can be an entangled state. A mixed state is biseparable, if it can be written as a convex combination of biseparable pure states, i.e., $\rho =\sum _i{p}_i|{\psi }_i{⟩}_1⟨{\psi }_i|\otimes |{\varphi }_i{⟩}_2⟨{\varphi }_i|$ with $p_i\ge 0$ and $\sum _i{p}_i=1$, where $|{\psi }_i⟩$’s and $|{\varphi }_i⟩$’s are biseparable pure states. A state that is not biseparable is called genuine multipartite entangled.

Theorem 1. ([18]) A density operator $\rho$ on ${\mathcal{H}}_1\otimes {\mathcal{H}}_2$, where ${\mathcal{H}}_i$’s are Hilbert spaces, is entangled if and only if there exists a Hermitian operator $w$ such that $\text{tr}[w\rho ]<0$, and for all separable states ${\rho }_{\text{sep}}$, $\text{tr}[w{\rho }_{\text{sep}}]\ge 0$. $w$ is called entanglement witness.

Let $|\psi ⟩$ be a pure state, $B$ be a fixed bipartite splitting, and consider product states $|\varphi ⟩\in B$. By choosing an orthonormal product basis $|ij⟩$ for partition $B$, we can write

$|\psi ⟩={\displaystyle \sum _{i,j}{\gamma }_{ij}|ij⟩,|\varphi ⟩=|\alpha \beta ⟩={\displaystyle \sum _{i,j}{\alpha }_i{\beta }_j|ij⟩.}}$

Let $\gamma =({\gamma }_{ij})$ be the coefficient matrix, $\mathit{\alpha }$ and $\mathit{\beta }$ be the normalized coefficient vectors. Thus

$\begin{array}{rl}{\text{max}}_{|\varphi ⟩\in B}|⟨\varphi |\psi ⟩|=& {\text{max}}_{{\alpha }_i,{\beta }_j}|\sum _{i,j}({\alpha }_i^{\ast }{\gamma }_{ij}{\beta }_j^{\ast })|\\ =& {\text{max}}_{\mathit{\alpha },\mathit{\beta }}|⟨\mathit{\alpha }|\gamma |{\mathit{\beta }}^{\mathbf{\ast }}⟩|={\text{max}}_k\{{\lambda }_k(\gamma )\},\end{array}$

where ${\lambda }_k(\gamma )$ denotes the singular values of $\gamma$. In other words, ${\lambda }_k(\gamma )$ are the Schmidt coefficients of $|\psi ⟩$ with respect to bipartite splitting $B$. Let $m$ be the square of the maximal Schmidt coefficient over all possible bipartite partitions of $|\psi ⟩$. Therefore, ${\mathcal{W}}_{\psi }=mI-|\psi ⟩⟨\psi |$ is a witness operator that detects genuine multipartite entanglement of $|\psi ⟩$. We can summarize this discussion in the following lemma.

Lemma 3. A witness operator that detects genuine multipartite entanglement of a pure state $|\psi ⟩$ is given by ${\mathcal{W}}_{\psi }=mI-|\psi ⟩⟨\psi |$, where $I$ is the identity operator and $m={\text{max}}_{|\varphi ⟩\in B}|⟨\varphi |\psi ⟩{|}^2$, where $B$ denotes the set of biseparable states.

Corollary 2. For $|\psi ⟩=|GHZ⟩$, ${\mathcal{W}}_{GHZ}=\frac{1}{2}I-$$|GHZ⟩⟨GHZ|$.

The witness ${\mathcal{W}}_{\mathrm{G}\mathrm{H}\mathrm{Z}}$ detects genuine $n$-qubit entanglement around the GHZ state, which has been applied in an experiment [19]. By applying Eq. (1), it turns out that ${\mathcal{W}}_{\mathrm{G}\mathrm{H}\mathrm{Z}}$ is a stabilizer witness, i.e., constructed by stabilizer generators, and can be measured locally, i.e., can be written as a sum of Pauli products. But the number of measurement settings increases exponentially with the number of qubits [20], which is not appropriate.

The GHZ state basis $\mathcal{B}$ is defined as the set of the following states

$\frac{1}{\sqrt{2}}(|x^1...x^n⟩\pm |{\tilde{x}}^1...{\tilde{x}}^n⟩),$

where $x^i\in \{0,1\}$ and ${\tilde{x}}^i=1-x^i$ for $i=1,...,n$. $\mathcal{B}$ is an orthogonal basis and $|\mathcal{B}|=2^n$. We represent elements of $\mathcal{B}$ as $|B⟩$.

For a given entanglement witness $\mathcal{W}$, let $D_{\mathcal{W}}$ be the set of states which are detected by $\mathcal{W}$, i.e.,

$D_{\mathcal{W}}:=\{\rho \ge 0:\text{tr}[\mathcal{W}\rho ]<0\}.$

For two given entanglement witnesses ${\mathcal{W}}_1$ and ${\mathcal{W}}_2$, we say that ${\mathcal{W}}_1$ is finer (coarser) than ${\mathcal{W}}_2$, if $D_{{\mathcal{W}}_2}\subset D_{{\mathcal{W}}_1}$ ($D_{{\mathcal{W}}_1}\subset D_{{\mathcal{W}}_2}$).

Theorem 2. There is a stabilizer witness consisting of all the generators which is coarser than ${\mathcal{W}}_{\mathrm{G}\mathrm{H}\mathrm{Z}}$.

Proof. It is shown that ${\mathcal{W}}_{\text{stab}}=\frac{n-1}{2}I-\frac{1}{2}\sum _{k=1}^n{\mathfrak{g}}_k$ is the desired witness. We note that $X|0⟩=|1⟩$, $X|1⟩=|0⟩$, $Z|0⟩=|0⟩$ and $Z|1⟩=-|1⟩$. Let

$T=(n-2)I-{\displaystyle \sum _{k=1}^n{\mathfrak{g}}_k+2|\mathrm{G}\mathrm{H}\mathrm{Z}⟩⟨\mathrm{G}\mathrm{H}\mathrm{Z}|.}$

Given a basis element $|B⟩\ne |\mathrm{G}\mathrm{H}\mathrm{Z}⟩$, there exists a stabilizer generator ${\mathfrak{g}}_k$ such that ${\mathfrak{g}}_k|B⟩=-|B⟩$, because case 1: if $|B⟩=\frac{|\mathrm{00...0}⟩-|\mathrm{11...1}⟩}{\sqrt{2}}$, then ${\mathfrak{g}}_1|B⟩=-|B⟩$, and case 2: if all of $x^i$’s in $|B⟩=\frac{1}{\sqrt{2}}(|x^1...x^n⟩\pm |{\tilde{x}}^1...{\tilde{x}}^n⟩)$ are not equal, let $j$ be the first index for which $x^i\ne x^{i+1}$, then ${\mathfrak{g}}_{j+1}|B⟩=-|B⟩$. It follows that $T|B⟩={\lambda }_B|B⟩$, where ${\lambda }_B\ge 0$. Furthermore, $T|\mathrm{G}\mathrm{H}\mathrm{Z}⟩=0$. It shows that all of the $2^n$ eigenvalues of $T$ are nonnegative, thus $T\ge 0$. Hence, ${\mathcal{W}}_{\text{stab}}\ge {\mathcal{W}}_{\mathrm{G}\mathrm{H}\mathrm{Z}}$ and then $\text{tr}[{\mathcal{W}}_{\text{stab}}\rho ]\ge \text{tr}[{\mathcal{W}}_{\mathrm{G}\mathrm{H}\mathrm{Z}}\rho ]$ for every state $\rho$. It means that $D_{{\mathcal{W}}_{\text{stab}}}\subset D_{{\mathcal{W}}_{\mathrm{G}\mathrm{H}\mathrm{Z}}}$.□

Theorem 2 shows that ${\mathcal{W}}_{\text{stab}}$ detects only states with genuine $n$-qubit entanglement. In fact, ${\mathcal{W}}_{\text{stab}}$ uses only two measurement settings: 1) $\{X_1,...,X_n\}$ to measure $\mathbb{E}({\mathfrak{g}}_1)$, and 2) $\{Z_1,...,Z_n\}$ to measure $\mathbb{E}({\mathfrak{g}}_2)$,..., $\mathbb{E}({\mathfrak{g}}_n)$. This is the advantage of using ${\mathcal{W}}_{\text{stab}}$.

Theorem 3. In Theorem 2, we need a full set of generators to detect genuine entanglement. In other words, with less than $n$ generators, we cannot detect genuine $n$-qubit entanglement.

Proof. We remove one of the stabilizer generators, say ${\mathfrak{g}}_n$. We claim that there is a Pauli product $u\in {\mathcal{P}}_n$ such that $u$ commutes with ${\mathfrak{g}}_i$ for $i=1,...,n-1$, and anticommutes with ${\mathfrak{g}}_n$. Since the parity check matrix $G$ has full rank, then the system of equations

$G_x=(00...01{)}^{\mathrm{t}}$

has a solution $\mathit{b}=\left(\begin{array}{c}{\mathit{b}}_1\\ {\mathit{b}}_2\end{array}\right)$, where ${\mathit{b}}_1$ and ${\mathit{b}}_2$ are $n\times 1$ binary columns. Let $U=({\mathit{b}}_2^{\text{t}}{\mathit{b}}_1^{\text{t}})$, then for rows $G_i$ of $G$, we have

$G_{i}J{U}^{\text{t}}=0(i=1,...,n-1),G_{n}J{U}^{\text{t}}=1.$

Let $u$ be the Pauli product corresponding to $U$, then according to Lemma 1, it turns out that $[u,{\mathfrak{g}}_i]=0$ for $i=1,...,n-1$, and $u{\mathfrak{g}}_n\ne {\mathfrak{g}}_{n}u$. Let $\hat{\mathcal{W}}$ be the witness which is obtained from ${\mathcal{W}}_{\text{stab}}$ by removing ${\mathfrak{g}}_n$. Since $u{\mathfrak{g}}_i={\mathfrak{g}}_{i}u$ ($i=1,...,n-1$), then the expectation values of $\hat{\mathcal{W}}$ in $|\mathrm{G}\mathrm{H}\mathrm{Z}⟩$ and $|g{}^{\prime }⟩:=u|\mathrm{G}\mathrm{H}\mathrm{Z}⟩$ are equal and it means that there are at least two elements of the basis $\mathcal{B}$ which give the minimum. We note that $⟨\mathrm{G}\mathrm{H}\mathrm{Z}|{\mathcal{W}}_{\text{stab}}|\mathrm{G}\mathrm{H}\mathrm{Z}⟩=-\frac{1}{2}$, and for any basis element $|B⟩\ne |\mathrm{G}\mathrm{H}\mathrm{Z}⟩$, $\sum _{k=1}^n⟨B|{\mathfrak{g}}_k|B⟩<n$, thus $⟨B|{\mathcal{W}}_{\text{stab}}|B⟩>-\frac{1}{2}$. Therefore, ${\mathcal{W}}_{\text{stab}}$ takes the minimal value only for $|\mathrm{G}\mathrm{H}\mathrm{Z}⟩$. There is a superposition of $|\mathrm{G}\mathrm{H}\mathrm{Z}⟩$ and $|g{}^{\prime }⟩$ which is biseparable. It follows that the witness $\hat{\mathcal{W}}$ takes the minimal value in the biseparable state and then it is not applicable to detect genuine $n$-qubit entanglement.□

In the next section, we study stabilizer codes as a strong tool to correct errors in multiple qubit systems.

5 Stabilizer codes

In classical coding theory, our goal is to encode $k$ classical bits (as $k$-bit strings) into binary codewords that are $n$-bit strings, say $v_k\mapsto v_n$. This is a linear code, if there exists an $k\times n$ full-rank matrix $G_c$ such that $v_n=v_k{G}_c$. The matrix $G_c$ is called the generator matrix of the code. The code is a $k$-dimensional subspace of ${\mathbb{F}}_2^n$ and is denoted by $\mathfrak{C}\in [n,k]$. The distance of $\mathfrak{C}$ is defined as $d:=\text{min}\{|\mathit{c}|:\mathit{c}\in \mathfrak{C}\}$, where $|\mathit{c}|=|\{c_i:c_i=1\}|$ with $\mathit{c}=(c_1,...,c_n)$. Here, it is denoted by $\mathfrak{C}\in [n,k,d]$. The dual of $\mathfrak{C}$ is a linear code defined as ${\mathfrak{C}}^{\perp }:=\{\mathit{x}\in {\mathbb{F}}_2^n:⟨\mathit{x},\mathit{c}⟩=0,\mathrm{\forall }\mathit{c}\in \mathfrak{C}\}$, where $⟨.,.⟩$ is the standard inner product. The parity check matrix of $\mathfrak{C}$ is the generator matrix of ${\mathfrak{C}}^{\perp }$ and is denoted by $P_c$.

Quantum stabilizer codes are quantum analogs of binary linear codes. Given an Abelian subgroup $S$ of ${\mathcal{P}}_n$ which does not contain $-I$, the (quantum) stabilizer code corresponding to $S$ is defined as $Q:=V_S$. When $S$ is generated by $n-k$ generators, the subspace $Q$ has dimension $2^k$ (Lemma 2), it encodes $k$ logical qubits to $n$ physical qubits and it is denoted by $Q\in [[n,k]]$. The distance of the code is defined as $d:={\text{min}}_{u\in N(S)\setminus S}w(u)$, where $N(S)=\{u\in {\mathcal{P}}_n:uS{u}^{†}=S\}$ is the normalizer of $S$. The elements of $N(S)\setminus S$ are called nontrivial logical operators and trivial logical operators are elements of $S$. We denote the set of all logical operators by $\mathcal{L}$. Here, the code is denoted by $Q\in [[n,k,d]]$. For example, the 7-qubit code (Steane code) is a $[[7,1,3]]$ code with the following stabilizer

$\begin{array}{rl}S=& ⟨Z_1{Z}_2{Z}_3{Z}_4,Z_1{Z}_2{Z}_5{Z}_6,Z_1{Z}_3{Z}_5{Z}_7,X_1{X}_2{X}_3{X}_4,\\ & X_1{X}_2{X}_5{X}_6,X_1{X}_3{X}_5{X}_7⟩.\end{array}$

This code encodes 1 qubit to 7 qubits and its codewords are

$\begin{array}{rl}|0{⟩}_L=& \frac{1}{\sqrt{8}}(|0000000⟩+|1010101⟩+|0110011⟩\\ & +|1100110⟩+|0001111⟩+|1011010⟩\\ & +|0111100⟩+|1101001⟩),\\ |1{⟩}_L=& X_1{X}_2{X}_3{X}_4{X}_5{X}_6{X}_7|0{⟩}_L.\end{array}$

The Steane code belongs to the family of CSS (Calderbank−Shor−Steane) codes. A CSS code $Q$ is a stabilizer code whose stabilizer $S$ splits into two sets $S_X$ and $S_Z$ satisfying: 1) $S_X,S_Z\subset {\mathcal{P}}_n$ and $S$ is the minimal group generated by $S_X$ and $S_Z$. 2) If $u=\prod _{i=1}^n{v}_i\in S_X$, then $v_i\in \{I,X\}$. 3) If $u=\prod _{i=1}^n{v}_i\in S_Z$, then $v_i\in \{I,Z\}$. Let $C_X$ and $C_Z$ be the subgroups of ${\mathbb{F}}_2^{2n}$ corresponding to $S_X$ and $S_Z$ in Lemma 1, respectively. Hence, up to a global phase, we have the following bijection:

$u_x={\displaystyle \prod _{i=1}^n{v}_i\in S_X\iff {\mathit{c}}_x=(c_1,...,c_n)\in C_X,}$

where $c_i=1(0)$ if and only if $v_i=X(I)$, and similarly for $S_Z$ and $C_Z$. It follows that $⟨c_x,c_z⟩=0$, thus $C_Z\subseteq C_X^{\perp }$ and $C_X\subseteq C_Z^{\perp }$. In this example, the distance of the stabilizer code is defined as $d={\text{min}}_{\mathit{c}\in C_X^{\perp }\setminus C_Z,C_Z^{\perp }\setminus C_X}|\mathit{c}|$.

The toric code is an instance of CSS codes. Let $\mathrm{\Lambda }$ be a two-dimensional lattice, i.e., a set of vertices $\mathcal{V}$, edges $\mathfrak{E}$ and faces $\mathcal{F}$ glued together in a certain way. The toric code in two dimensions is defined on a lattice $\mathrm{\Lambda }$ by placing one qubit on every edge, and associating $X$- and $Z$-type generators with vertices and faces of $\mathrm{\Lambda }$ as follows:

$\mathrm{\forall }v\in \mathcal{V},X(v):={\displaystyle \prod _{e\in v}X(e),\mathrm{\forall }f\in \mathcal{F},Z(f):={\displaystyle \prod _{e\in f}Z(e),}}$

where $X(e)$ and $Z(e)$ denote Pauli $X$ and $Z$ operators, respectively, acting on qubit placed on the edge $e$ (see Fig.1).

Fig.1 Toric code.

Full size|PPT slide

The Gottesman−Kitaev−Preskil (GKP) code is another instance of stabilizer codes. The GKP code is an $n$-mode quantum lattice code with $2n$ stabilizers, i.e., constructed using a non-degenerate lattice. This family of codes is quite important in fault-tolerant quantum computation. The GKP code is an important type of bosonic quantum error-correcting codes, which encodes a qubit in an oscillator [47].

A natural question gives rise: Given a linear code, how can we construct a stabilizer code? Let $\mathfrak{C}$ be an $[n,k]$ linear code with generator $G_c$. Let $A_1,...,A_k$ be the rows of $G_c$. We extend the set of rows to a basis for ${\mathbb{F}}_2^n$ denoted by $\{A_1,...,A_k,A_{k+1},...,A_n\}$. Let $A$ be an $n\times n$ matrix with rows $A_1,...,A_n$ and $B$ be the inverse of $A$. Denote the columns of $B$ by $B_1,...,B_n$. By applying this notation ${\mathit{X}}^{\mathit{a}}:=\prod _{i=1}^n{X}_i^{a_i}$ and ${\mathit{Z}}^{\mathit{a}}:=\prod _{i=1}^n{Z}_i^{a_i}$, where $\mathit{a}=(a_1,...,a_n)\in {\mathbb{F}}_2^n$, we define the following $2n-k-2$ generators on $2n-k-1$ qubits:

$\begin{array}{rl}& g_i={\mathit{Z}}^{A_i}1\le i\le k,\\ & g_{k+i}={\mathit{Z}}^{A_{k+i}}{Z}_{n+i}1\le i\le n-k-1,\\ & g_{n-1+i}={\mathit{X}}^{B_{k+i}}{X}_{n+i}1\le i\le n-k-1.\end{array}$

1) $g_i$’s are independent. It follows from the linear independence of $A_i$’s, the linear independence of $B_i$’s, and the fact that the binary representation of $X$-type operators is linear independent of the binary representation of $Z$-type operators.

2) $g_i$’s mutually commute. It is clear for the first $n-1$ generators and for the last $n-k-1$ generators. Between them, the commutation follows from the following identity

${\mathit{X}}^{A_i}{\mathit{Z}}^{B_j}=(-1{)}^{⟨A_i,B_j⟩}{\mathit{Z}}^{B_j}{\mathit{X}}^{A_i},$

and the fact that $⟨A_i,B_j⟩=0$ for $i\ne j$, and for $i=j$ the presence of $X_{n+i}$ and $Z_{n+i}$ guarantees commutation. Hence, $S=⟨g_1,...,g_{2n-k-2}⟩$ defines a $[[2n-k-1,1]]$ stabilizer code.

5.1 Quantum error correction

Classical computers use repetition codes, i.e., each bit is encoded in many electrons, and after each time step the error correction is done, i.e., it is turned back to the value held by the majority of the electrons. The simplest example is the following repetition code: $0\mapsto 000,1\mapsto 111$. It will correct the state $101$ to the majority value $111$. Because of the No−Cloning theorem, quantum computers cannot use a quantum repetition code as follows: $|\psi ⟩\mapsto |\psi ⟩\otimes |\psi ⟩\otimes |\psi ⟩$. The No−Cloning theorem says that there is no quantum operation that takes any state $|\psi ⟩$ to $|\psi ⟩\otimes |\psi ⟩$ [21].

Quantum error correction comes from meeting error correction in classical information theory and principles of quantum mechanics [23]. It is concerned with the main problem of communication in the presence of noise. Consider a single qubit in a pure state which interacts with its environment. Without loss of generality, we may assume that the initial state of the environment is pure, say $|0{⟩}_E$. The evolution of the qubit and its environment is described by a unitary operator $\mathit{U}$ as follows:

$\begin{array}{rl}\mathit{U}:& |0⟩\otimes |0{⟩}_E\mapsto |0⟩\otimes |{\varphi }_{00}{⟩}_E+|1⟩\otimes |{\varphi }_{01}{⟩}_E,\\ & |1⟩\otimes |0{⟩}_E\mapsto |0⟩\otimes |{\varphi }_{10}{⟩}_E+|1⟩\otimes |{\varphi }_{11}{⟩}_E,\end{array}$

where $|{\varphi }_{ij}{⟩}_E$ are states of the environment. For an arbitrary state $|\psi ⟩=a|0⟩+b|1⟩$, we have

$\begin{array}{rl}\mathit{U}:& (a|0⟩+b|1⟩)\otimes |0{⟩}_E\mapsto a(|0⟩\otimes |{\varphi }_{00}{⟩}_E\\ & +|1⟩\otimes |{\varphi }_{01}{⟩}_E)+b(|0⟩\otimes |{\varphi }_{10}{⟩}_E+|1⟩\otimes |{\varphi }_{11}{⟩}_E)\\ =& (a|0⟩+b|1⟩)\otimes \frac{1}{2}(|{\varphi }_{00}{⟩}_E+|{\varphi }_{11}{⟩}_E)\\ & +(a|0⟩-b|1⟩)\otimes \frac{1}{2}(|{\varphi }_{00}{⟩}_E-|{\varphi }_{11}{⟩}_E)\\ & +(a|1⟩+b|0⟩)\otimes \frac{1}{2}(|{\varphi }_{01}{⟩}_E+|{\varphi }_{10}{⟩}_E)\\ & +(a|1⟩-b|0⟩)\otimes \frac{1}{2}(|{\varphi }_{01}{⟩}_E-|{\varphi }_{10}{⟩}_E)\\ =& I|\psi ⟩\otimes |{\varphi }_I{⟩}_E+X|\psi ⟩\otimes |{\varphi }_X{⟩}_E\\ & +Y|\psi ⟩\otimes |{\varphi }_Y{⟩}_E+Z|\psi ⟩\otimes |{\varphi }_Z{⟩}_E.\end{array}$

The interpretation of this expanding is that one of the following situations occurs to the qubit: trivial ($I$), bit flip ($X$), phase flip ($Z$), or both ($Y=iXZ$) (in practice, this classification makes sense when four states $|{\varphi }_I{⟩}_E,|{\varphi }_X{⟩}_E,|{\varphi }_Y{⟩}_E$ and $|{\varphi }_Z{⟩}_E$ of the environment are mutually orthogonal).

In general, for $n$ qubits, the action of an arbitrary unitary operator can be described as follows:

$|\psi ⟩\otimes |0{⟩}_E\mapsto {\displaystyle \sum _{u}u|\psi ⟩\otimes |{\varphi }_u{⟩}_E,}$

where $u$ ranges over Pauli products and $|{\varphi }_u{⟩}_E$ are the corresponding states of the environment. We aim to identify a subset $\mathcal{E}\subset {\mathcal{P}}_n$ of correctable errors, i.e., the errors that we wish to be able to correct.

5.1.1 Error-correcting codes

A quantum error-correcting code is a mapping from the Hilbert space of dimension $2^k$ corresponding to $k$ logical (encoded) qubits into the Hilbert space of dimension $2^n$ corresponding to $n$ physical qubits, where $n>k$. The image of this mapping is called the code subspace. Our goal is to protect $k$ encoded qubits from error. In this way, $n-k$ qubits are added as redundant qubits. Let $\{|{\psi }_i⟩\}$ be an orthonormal basis for the code subspace, $|{\psi }_i⟩$’s are called codewords. Now the quantum error correction criteria [22], i.e., a necessary and sufficient condition in terms of the codewords to preserve the code subspace, is proved.

Theorem 4. Let $\mathcal{E}=\{E_a\}$ be a linear space of errors acting on the subspace code $Q$. Then recovery is possible if and only if

(4)$⟨\psi |E_b^{†}{E}_a|\varphi ⟩=0,$

(5)$⟨\psi |E_b^{†}{E}_a|\psi ⟩=⟨\varphi |E_b^{†}{E}_a|\varphi ⟩,$

$\mathrm{\forall }a,band\mathrm{\forall }|\psi ⟩\ne |\varphi ⟩\in Q$.

Proof. Suppose that recovery is possible and let $\mathcal{R}$ be the unitary operator describing the whole recovery operation, then

$\mathcal{R}|{\eta }_a⟩E_a|\varphi ⟩=|{\eta }_a^{\mathrm{\prime }}⟩|\varphi ⟩,\mathcal{R}|{\eta }_b⟩E_b|\psi ⟩=|{\eta }_b^{\mathrm{\prime }}⟩|\psi ⟩,$

where $|\eta ⟩$’s are states of the ancilla (it is employed to implement the recovery operation) and the environment. Therefore,

$⟨\psi |E_b^{†}⟨{\eta }_b|{\mathcal{R}}^{†}\mathcal{R}|{\eta }_a⟩E_a|\varphi ⟩=⟨{\eta }_b^{\mathrm{\prime }}|{\eta }_a^{\mathrm{\prime }}⟩⟨\psi |\varphi ⟩.$

Since the recovery operation must work particularly when $|{\eta }_a⟩=|{\eta }_b⟩$, then $⟨\psi |E_b^{†}{E}_a|\varphi ⟩=0$ and Eq. (4) is proven. To prove Eq. (5), we can write as follows:

$\begin{array}{rl}& \mathcal{R}|\eta ⟩E_i|\psi ⟩=|{\eta }_i^{\mathrm{\prime }}⟩|\psi ⟩,(i=a,b)\\ & \Rightarrow ⟨\psi |E_b^{†}⟨\eta |{\mathcal{R}}^{†}\mathcal{R}|\eta ⟩E_a|\psi ⟩=⟨{\eta }_b^{\mathrm{\prime }}|{\eta }_a^{\mathrm{\prime }}⟩\\ & \Rightarrow ⟨\psi |E_b^{†}{E}_a|\psi ⟩=⟨{\eta }_b^{\mathrm{\prime }}|{\eta }_a^{\mathrm{\prime }}⟩.\end{array}$

Similarly, by starting from $|\varphi ⟩$, the same result is obtained and then Eq. (5) is proved. Analog of Eq. (5) is not possible in classical coding theory [42].

Suppose that Eqs. (4) and (5) or equivalently $⟨{\psi }_j|E_b^{†}{E}_a|{\psi }_i⟩=C_{ba}{\delta }_{ij}$ holds. It is clear that $C=[C_{ba}]$ is a Hermitian matrix. The action of an error on a basis state $|{\psi }_i⟩$ and the environment is $|{\psi }_i⟩\otimes |0{⟩}_E\mapsto$$\sum _{\alpha }{F}_{\alpha }|{\psi }_i⟩\otimes |\alpha {⟩}_E$, where $|\alpha {⟩}_E$’s are elements of an orthonormal basis for the environment, and $F_{\alpha }$’s are linear combinations of the Pauli products $E_a$’s, satisfying the normalization condition

(6)${\displaystyle \sum _{\alpha }{F}_{\alpha }^{†}{F}_{\alpha }=I.}$

It follows that $⟨{\psi }_j|F_{\beta }^{†}{F}_{\alpha }|{\psi }_i⟩=C_{\beta \alpha }{\delta }_{ij}$. The error can be reversed if there exist operators $R_{\mu }$’s such that $\sum _{\mu }{R}_{\mu }^{†}{R}_{\mu }=I$ (normalization) and

${\displaystyle \sum _{\alpha ,\mu }{R}_{\mu }{F}_{\alpha }|{\psi }_i⟩\otimes |\alpha {⟩}_E\otimes |\mu {⟩}_A=|{\psi }_i⟩\otimes |\vartheta {⟩}_{EA},}$

where $\{|\mu {⟩}_A\}$ is an orthonormal basis for the Hilbert space of the ancilla and the state $|\vartheta {⟩}_{EA}$ of environment and ancilla does not depend on $i$. The basis for the environment $\{|\alpha {⟩}_E\}$ can be chosen such that the matrix $C$ is diagonalized

(7)$⟨{\psi }_j|F_{\beta }^{†}{F}_{\alpha }|{\psi }_i⟩=C_{\alpha }{\delta }_{\alpha \beta }{\delta }_{ij},$

where $\sum _{\alpha }{C}_{\alpha }=1$ follows from Eq. (6). For each $\mu$ with $C_{\mu }\ne 0$, let $R_{\mu }=\frac{1}{\sqrt{C_{\mu }}}\sum _i|{\psi }_i⟩⟨{\psi }_i|F_{\mu }^{†}$, therefore

(8)$\begin{array}{rl}& \sum _{\alpha ,\mu }{R}_{\mu }{F}_{\alpha }|{\psi }_i⟩\otimes |\alpha {⟩}_E\otimes |\mu {⟩}_A\\ & =|{\psi }_i⟩\otimes (\sum _{\mu }\sqrt{C_{\mu }}|\mu {⟩}_E\otimes |\mu {⟩}_A).\end{array}$

Equation (8) shows that the $R_{\mu }$’s do indeed reverse the error. It remains to check the normalization condition. Let

$R={\displaystyle \sum _{\mu }{R}_{\mu }^{†}{R}_{\mu }={\displaystyle \sum _{\mu }\frac{1}{C_{\mu }}{\displaystyle \sum _i{F}_{\mu }|{\psi }_i⟩⟨{\psi }_i|F_{\mu }^{†}.}}}$

By applying Eq. (7) it follows that

$\begin{array}{rl}{R}^2=& (\sum _{\mu }\frac{1}{C_{\mu }}\sum _i{F}_{\mu }|{\psi }_i⟩⟨{\psi }_i|F_{\mu }^{†})(\sum _{\gamma }\frac{1}{C_{\gamma }}\sum _j{F}_{\gamma }|{\psi }_j⟩⟨{\psi }_j|F_{\gamma }^{†})\\ =& \sum _{\mu }\frac{1}{C_{\mu }}\sum _i{F}_{\mu }|{\psi }_i⟩\sum _{\gamma }\frac{1}{C_{\gamma }}\sum _j{C}_{\gamma }{\delta }_{\mu \gamma }{\delta }_{ij}⟨{\psi }_j|F_{\gamma }^{†}\\ =& \sum _{\mu }\frac{1}{C_{\mu }}\sum _i{F}_{\mu }|{\psi }_i⟩⟨{\psi }_i|F_{\mu }^{†}=R.\end{array}$

By adding the projector $I-R$ to $R_{\mu }$’s, we obtain a set of recovery operators (Kraus operators) satisfying the normalization condition.□

Remark 2. The distance of a stabilizer code can be defined as the smallest positive integer $d$ such that the quantum error correction criteria is satisfied for all error combinations $E_b^{†}{E}_a$ of weight in the range $1\le$$w(E_b^{†}{E}_a)<d$.

A code is called nondegenerate, if $⟨{\psi }_j|E_b^{†}{E}_a|{\psi }_i⟩={\delta }_{ab}{\delta }_{ij}$ for all $a,b,i\text{and}j$. A code that is not nondegenerate is degenerate. For example, consider the 9-qubit code (Shor code) with the following stabilizer:

$\begin{array}{rl}S=& ⟨Z_1{Z}_2,Z_2{Z}_3,Z_4{Z}_5,Z_5{Z}_6,Z_7{Z}_8,Z_8{Z}_9,\\ & X_1{X}_2{X}_3{X}_4{X}_5{X}_6,X_4{X}_5{X}_6{X}_7{X}_8{X}_9⟩.\end{array}$

It is a $[[9,1,3]]$ code with these codewords:

$\begin{array}{rl}|0{⟩}_L=& \frac{1}{\sqrt{8}}(|000⟩+|111⟩)\otimes (|000⟩+|111⟩)\\ & \otimes (|000⟩+|111⟩),\\ |1{⟩}_L=& \frac{1}{\sqrt{8}}(|000⟩-|111⟩)\otimes (|000⟩-|111⟩)\\ & \otimes (|000⟩-|111⟩).\end{array}$

The Shor code is degenerate, because we cannot distinguish $Z_1$ and $Z_2$,

$Z_1{Z}_2|\psi ⟩=|\psi ⟩\iff Z_1|\psi ⟩=Z_2|\psi ⟩.$

5.1.2 Syndrome extraction

Based on the property that every two Pauli products either commute or anti-commute, we will see how a stabilizer code detects and corrects errors. The corresponding syndrome of a given error is a bit string including which stabilizer generator commutes or anti-commutes with the error. Given an error $E$, its syndrome is denoted by $\text{Syn}(E)$. For example, consider the 5-qubit code with the following stabilizer

$S=⟨Z_1{X}_2{X}_3{Z}_4,Z_2{X}_3{X}_4{Z}_5,Z_1{Z}_3{X}_4{X}_5,X_1{Z}_2{Z}_4{X}_5⟩.$

The syndrome for the error $X_2$ is $(0101)$, where 0’s indicate that the generators $g_1,g_3$ commute with $X_2$ and 1’s indicate that the generators $g_2,g_4$ anti-commute with $X_2$.

Proposition 1. Given a stabilizer code $Q$, there exists an error with any given syndrome.

Proof. Let $S=⟨g_1,...,g_l⟩$ be the stabilizer of $Q$. The syndrome of an error $E$ is a bit string of length $l$. Therefore, $b=(b_1...b_l)$ is the syndrome of $E$ if and only if $b(g_i)Jb(E{)}^t=b_i$ for all $i$ (Lemma 1). It gives a system of equations with $l$ equations and $2n$ variables $(l\le n)$ which has a nonzero solution.□

Any code allows correction of a particular family of correctable errors. Given a stabilizer code $Q$ with stabilizer $S$, error operators in $S$ are all correctable. If the noise of the system under consideration includes only these errors, the code is called a decoherence free subspace. There is a large family $\mathcal{E}=\{E_{\alpha }\}$ of errors which are correctable by extracting the corresponding syndromes. It is shown that if for every product $E_{\alpha }{E}_{\beta }$ of two members of $\mathcal{E}$, either $E_{\alpha }{E}_{\beta }\in S$ or $E_{\alpha }{E}_{\beta }s=-s{E}_{\alpha }{E}_{\beta }$ for some $s\in S$ then $\mathcal{E}$ is correctable. Let $|\psi ⟩=\sum _i{a}_i|{\psi }_i⟩$ be a general encoded state.

In the first case, $E_{\alpha }$ and $E_{\beta }$ have the same syndrome, so are indistinguishable, but both are correctable because the common syndrome leads us to apply $E_{\alpha }$ as the corrective operator. If it was $E_{\alpha }$ which occured, this is well, while if $E_{\beta }$ occured, the final state will be $E_{\alpha }{E}_{\beta }|\psi ⟩=|\psi ⟩$ which is also correct. This case is related to degenerate codes.

In the second case, either $E_{\alpha }s=s{E}_{\alpha },E_{\beta }s=-s{E}_{\beta }$, or $E_{\alpha }s=-s{E}_{\alpha },E_{\beta }s=s{E}_{\beta }$. It follows that $E_{\alpha }$ and $E_{\beta }$ have different syndromes, thus they are distinguishable from each other. The noisy state is $\sum _{\alpha }(E_{\alpha }|\psi ⟩)\otimes |{\varphi }_{\alpha }{⟩}_E$. Quantum error correction determines the error syndrome with the help of ancilla qubits:

$\begin{array}{rl}& |0{⟩}_A\otimes \sum _{\alpha }(E_{\alpha }|\psi ⟩)\otimes |{\varphi }_{\alpha }{⟩}_E\\ & \mapsto \sum _{\alpha }|\text{Syn}(E_{\alpha }){⟩}_A\otimes (E_{\alpha }|\psi ⟩)\otimes |{\varphi }_{\alpha }{⟩}_E.\end{array}$

By a projective measurement of the ancilla, the sum will be collapsed to a single term randomly $|\text{Syn}(E_{\alpha }){⟩}_A\otimes$$(E_{\alpha }|\psi ⟩)\otimes |{\varphi }_{\alpha }{⟩}_E$ and we will obtain $\text{Syn}(E_{\alpha })$ as the measurement result. Since there is only one error with this syndrome, we are able to apply $E_{\alpha }$ to correct the error. This case is related to nondegenerate codes.

5.2 Symplectic structure

Matrix $M\in {\mathbb{F}}_2^{2n\times 2n}$ is called symplectic, if $MJ{M}^t=J$. The set of all symplectic matrices in ${\mathbb{F}}_2^{2n\times 2n}$ is denoted by $\text{Sp}(2n,{\mathbb{F}}_2)$, which is a group under matrix multiplication.

Lemma 4. Up to a global phase, ${\mathcal{C}}_n/{\mathcal{P}}_n\simeq \text{Sp}(2n,{\mathbb{F}}_2)$.

Proof. For $\mathit{a}=({\mathit{a}}_1{\mathit{a}}_2)\in {\mathbb{F}}_2^{2n}$, where ${\mathit{a}}_i=(a_i^1{a}_i^2...a_i^n)$, let

$\xi (\mathit{a}):={\mathit{X}}^{{\mathit{a}}_1}{\mathit{Z}}^{{\mathit{a}}_2}={\displaystyle \prod _{i=1}^n{X}_i^{a_1^i}{\displaystyle \prod _{i=1}^n{Z}_i^{a_2^i}.}}$

It follows that for every $\mathit{a},\mathit{b}\in {\mathbb{F}}_2^{2n}$,

$\xi (\mathit{a})\xi (\mathit{b})=(-1{)}^{⟨{\mathit{b}}_1,{\mathit{a}}_2⟩}\xi (\mathit{a}+\mathit{b})=(-1{)}^{\mathit{b}\left(\begin{array}{cc}\mathbf{0}& I\\ \mathbf{0}& \mathbf{0}\end{array}\right){\mathit{a}}^t}\xi (\mathit{a}+\mathit{b}),$

and every $u\in {\mathcal{C}}_n$ satisfies $u\xi (\mathit{a})u^{†}=(-1{)}^{f(\mathit{a})}\xi (g(\mathit{a}))$ for some functions $f$ and $g$. It turns out that

$\begin{array}{rl}& (-1{)}^{f(\mathit{a}+\mathit{b})}\xi (g(\mathit{a}+\mathit{b}))=u\xi (\mathit{a}+\mathit{b})u^{†}\\ & =(-1{)}^{\mathit{b}\left(\begin{array}{cc}\mathbf{0}& I\\ \mathbf{0}& \mathbf{0}\end{array}\right){\mathit{a}}^t}u\xi (\mathit{a})u^{†}u\xi (\mathit{b})u^{†}\\ & =(-1{)}^{f(\mathit{a})+f(\mathit{b})+\mathit{b}\left(\begin{array}{cc}\mathbf{0}& I\\ \mathbf{0}& \mathbf{0}\end{array}\right){\mathit{a}}^t}\xi (g(\mathit{a}))\xi (g(\mathit{b}))\\ & =(-1{)}^{f(\mathit{a})+f(\mathit{b})+\mathit{b}\left(\begin{array}{cc}\mathbf{0}& I\\ \mathbf{0}& \mathbf{0}\end{array}\right){\mathit{a}}^t+g(\mathit{b})\left(\begin{array}{cc}\mathbf{0}& I\\ \mathbf{0}& \mathbf{0}\end{array}\right)g(\mathit{a}{)}^t}\xi (g(\mathit{a})+g(\mathit{b})).\end{array}$

From this equality, we have

$\begin{array}{rl}f(\mathit{a}+\mathit{b})=& f(\mathit{a})+f(\mathit{b})+\mathit{b}\left(\begin{array}{cc}\mathbf{0}& I\\ \mathbf{0}& \mathbf{0}\end{array}\right){\mathit{a}}^t\\ & +g(\mathit{b})\left(\begin{array}{cc}\mathbf{0}& I\\ \mathbf{0}& \mathbf{0}\end{array}\right)g(\mathit{a}{)}^t,\\ g(\mathit{a}+\mathit{b})=& g(\mathit{a})+g(\mathit{b}).\end{array}$

Therefore, $g(\mathit{x})=\mathit{x}M$ for some $M\in {\mathbb{F}}_2^{2n\times 2n}$ and

$f(\mathit{x})=⟨\mathit{r},\mathit{x}⟩+\mathit{b}\left(\begin{array}{cc}\mathbf{0}& I\\ \mathbf{0}& \mathbf{0}\end{array}\right){\mathit{a}}^t+g(\mathit{b})\left(\begin{array}{cc}\mathbf{0}& I\\ \mathbf{0}& \mathbf{0}\end{array}\right)g(\mathit{a}{)}^t,$

for some $\mathit{r}\in {\mathbb{F}}_2^{2n}$. Let $⟨\mathit{x},\mathit{y}{⟩}_{\text{s}}:=\mathit{x}J{\mathit{y}}^t$ be the symplectic inner product. We note that $\xi (\mathit{x})$ and $\xi (\mathit{y})$ commute (anti-commute) if and only if $⟨\mathit{x},\mathit{y}{⟩}_{\text{s}}=0(1)$. Given unitary $u\in {\mathcal{C}}_n$, conjugating by $u$ ($\sigma \mapsto u\sigma u^{†}$) preserves commutation (anti-commutation) of $\xi (\mathit{x})$ and $\xi (\mathit{y})$, then its corresponding matrix $M$ preserves the symplectic inner product, i.e., $\mathit{x}J{\mathit{y}}^t=\mathit{x}MJ(\mathit{y}M{)}^t=\mathit{x}MJ{M}^t{\mathit{y}}^t$ for every $\mathit{x}$ and $\mathit{y}$. Hence, $MJ{M}^t=J$, i.e., $M\in \text{Sp}(2n,{\mathbb{F}}_2)$, and $h:{\mathcal{C}}_n\to \text{Sp}(2n,{\mathbb{F}}_2)$ which maps $u$ onto $M$ defines a group homomorphism. It is clear that ${\mathcal{P}}_n\subset \text{Ker}(h)=\{u\in {\mathcal{C}}_n:uv{u}^{†}=\pm v,\mathrm{\forall }v\in {\mathcal{P}}_n\}$. Let $u\in \text{Ker}(h)$, then $u{X}_j{u}^{†}=\pm X_j$ and $u{Z}_j{u}^{†}=\pm Z_j$ for all $j$. The sign changes reveal that which of the Pauli operators $I,X,Y$ and $Z$ is being to qubit $j$ by $u$, call this operator $v_j$. Together these operators we construct the Pauli product $v=\prod _{j=1}^n{v}_j$ which is equal to $u$, because they perform the same thing when conjugating every generator of ${\mathcal{P}}_n=⟨X_1,Z_1,...,X_n,Z_n⟩$.□

Given $k\le n$, the $k$-trivial stabilizer code on $n$ qubits is defined by

$T_k=\{|0{⟩}^{\otimes (n-k)}\otimes |\varphi ⟩:|\varphi ⟩\in ({\mathbb{C}}^2{)}^{\otimes k}\}.$

Theorem 5. For any stabilizer code $Q\in [[n,k]]$, there exists a unitary operator $u\in {\mathcal{C}}_n$ such that $Q=u{T}_k$. In other words, $Q$ and $T_k$ are (Clifford) unitarily equivalent.

Proof. Given code $Q$ stabilized by $S=⟨g_1,...,g_{n-k}⟩$. We take into account that the stabilizer of $T_k$ is generated by $Z_1,...,Z_{n-k}$. We need to find a unitary $u$ such that $u{Z}_i{u}^{†}=g_i$ for all $i$. In general, this unitary $u$ is not unique since we can redefine it by any $v\in {\mathcal{C}}_n$ which acts trivially on $T_k$. However, any choice of stabilizer basis of $Q$ induces a $u$. In fact, a choice of logical basis $|\overline{x}⟩$ corresponds to a full completion $g_1,...,g_{n-k},g_{n-k+1},...,g_n$ of the generators and the logical basis is determined by the eigenvalues of $g_{n-k+1},...,g_n$. The unitary $u$ defined by $u{Z}_i{u}^{†}=g_i$ for $i=1,...,n$ is a Clifford operator because the Pauli products on the left and right hand side are fully commuting sets. This unitary $u$ transforms input states as follows:

$\begin{array}{rl}|0{⟩}^{\otimes (n-k)}\otimes |\varphi ⟩=& \sum _{x\in {\mathbb{F}}_2^k}{\lambda }_x|0{⟩}^{\otimes (n-k)}\otimes |x⟩\\ & \mapsto \sum _{x\in {\mathbb{F}}_2^k}{\lambda }_x|0{⟩}^{\otimes (n-k)}\otimes |\overline{x}⟩.\end{array}$

□

In classical coding theory, it is usual to use finite fields larger than ${\mathbb{F}}_2$. The simplest example is ${\mathbb{F}}_4=\{0,1,\omega ,{\omega }^2\}$ with ${\omega }^3=1,{\omega }^2=\omega +1$. It is a field of characteristic 2 with the following two operations: 1) Conjugation: $\overline{0}=0,\overline{1}=1,\overline{\omega }={\omega }^2,\overline{{\omega }^2}=\omega$. 2) Trace: $\text{Tr}:{\mathbb{F}}_4\to {\mathbb{F}}_2,x\mapsto x+\overline{x}$. Let $\lambda :{\mathbb{F}}_2^{2n}\to {\mathbb{F}}_4^n$ be a mapping which sends each $\nu =(a|b)$ to $\lambda (\nu )=a\omega +b\overline{\omega }$. For $\nu =(a|b)$ and ${\nu }^{\mathrm{\prime }}=(a^{\mathrm{\prime }}|b^{\mathrm{\prime }})$ in ${\mathbb{F}}_2^{2n}$,

$\begin{array}{rl}\text{Tr}(⟨\lambda (\nu ),\overline{\lambda ({\nu }^{\mathrm{\prime }})}⟩)=& \text{Tr}(⟨(a\omega +b\overline{\omega }),(a^{\mathrm{\prime }}\overline{\omega }+b^{\mathrm{\prime }}\omega )⟩)\\ =& ⟨a,a^{\mathrm{\prime }}⟩\text{Tr}(1)+⟨a,b^{\mathrm{\prime }}⟩\text{Tr}(\overline{\omega })\\ & +⟨b,a^{\mathrm{\prime }}⟩\text{Tr}(\omega )+⟨b,b^{\mathrm{\prime }}⟩\text{Tr}(1)\\ =& ⟨a,b^{\mathrm{\prime }}⟩+⟨b,a^{\mathrm{\prime }}⟩=\nu J{{\nu }^{\mathrm{\prime }}}^t=⟨\nu ,{\nu }^{\mathrm{\prime }}{⟩}_{\text{s}}.\end{array}$

Here, the trace inner product turns into the symplectic inner product. The Pauli operators $I,X,Y\text{and}Z$ are associated with $0,1,{\omega }^2\text{and}\omega$, respectively. Given a linear code over ${\mathbb{F}}_4$ with parity check matrix $P_c$. Since ${\mathbb{F}}_4=\{a+b\omega :a,b\in \{0,1\}\}$, then any vector in the dual space of the code can be generated by summing together selected rows of $P_c$, each multiplied by $\omega$. It is shown that the 5-qubit code (over ${\mathbb{F}}_2$) is derived from the Hamming code $[5,3,3]$ over ${\mathbb{F}}_4$. In this way, we need to find Pauli products associated with the rows of $P_c$ and $\omega P_c$ as follows:

$\begin{array}{rl}& P_c=\left(\begin{array}{ccccc}1& \omega & \omega & 1& 0\\ 0& 1& \omega & \omega & 1\end{array}\right),\\ & r_1=(1\omega \omega 10)⟶g_1=X_1{Z}_2{Z}_3{X}_4{I}_5,\\ & r_2=(01\omega \omega 1)⟶g_2=I_1{X}_2{Z}_3{Z}_4{X}_5,\\ & \omega r_1=(\omega {\omega }^2{\omega }^2\omega 0)⟶g_3=Z_1{Y}_2{Y}_3{Z}_4{I}_5,\\ & \omega r_2=(0\omega {\omega }^2{\omega }^2\omega )⟶g_4=I_1{Z}_2{Y}_3{Y}_4{Z}_5.\end{array}$

It follows that $S=⟨g_1^{\mathrm{\prime }},g_2^{\mathrm{\prime }},g_3^{\mathrm{\prime }},g_4^{\mathrm{\prime }}⟩$ with $g_1^{\mathrm{\prime }}:=g_3{g}_2=$$Z_1{Z}_2{X}_3{X}_5$, $g_2^{\mathrm{\prime }}:=g_4{g}_1=X_1{X}_3{Z}_4{Z}_5$, $g_3^{\mathrm{\prime }}:=g_1$, and $g_4^{\mathrm{\prime }}:=g_2$ is the stabilizer for the 5-qubit code.

5.3 Graph codes

Let $\mathcal{G}$ be a graph with a set of $\mathcal{V}$ of $n$ vertices and a collection $\mathfrak{E}$ of edges. We associate the vertices to the numbers $1,2,...,n$. We are only interested in graphs without loops, i.e., there are no edges of the form $(i,i)$. The graph state $|\mathcal{G}⟩$ is defined as the stabilizer state stabilized by the following Pauli products:

(9)$g_i:=X_i{\displaystyle \prod _{j\in N(i)}{Z}_j\mathrm{\forall }i\in \mathcal{V},}$

where $N(i)=\{j\in \mathcal{V}:(i,j)\in \mathfrak{E}\}$. The corresponding parity check matrix for generators of a graph state is in the standard form, i.e., $G=(I|A)$. Let $C{P}_{ij}$ be the controlled phase operator (gate) between qubits $i$ and $j$,

$C{P}_{ij}:=\left(\begin{array}{cccc}1& 0& 0& 0\\ 0& 1& 0& 0\\ 0& 0& 1& 0\\ 0& 0& 0& -1\end{array}\right),$

and $|+⟩=\frac{|0⟩+|1⟩}{\sqrt{2}}$, the graph state $|\mathcal{G}⟩$ can be defined as [24]

(10)$|\mathcal{G}⟩={\displaystyle \prod _{(i,j)\in \mathfrak{E}}C{P}_{ij}|+{⟩}^{\otimes n}.}$

Each graph state $|\mathcal{G}⟩$ corresponds uniquely to a graph, i.e., two different graphs $\mathcal{G}=(\mathcal{V},\mathfrak{E})$ and ${\mathcal{G}}^{\mathrm{\prime }}=(\mathcal{V},{\mathfrak{E}}^{\mathrm{\prime }})$ cannot describe the same graph state, because

$\begin{array}{rl}|+{⟩}^{\otimes n}=& \prod _{(i,j)\in {\mathfrak{E}}^{\mathrm{\prime }}}C{P}_{ij}|{\mathcal{G}}^{\mathrm{\prime }}⟩=\prod _{(i,j)\in {\mathfrak{E}}^{\mathrm{\prime }}}C{P}_{ij}|\mathcal{G}⟩\\ =& \prod _{(i,j)\in {\mathfrak{E}}^{\mathrm{\prime }}}C{P}_{ij}\prod _{(i,j)\in \mathfrak{E}}C{P}_{ij}|+{⟩}^{\otimes n}\\ =& \prod _{(i,j)\in \mathfrak{E}+{\mathfrak{E}}^{\mathrm{\prime }}}C{P}_{ij}|+{⟩}^{\otimes n},\end{array}$

where $\mathfrak{E}+{\mathfrak{E}}^{\mathrm{\prime }}\ne \mathrm{\varnothing }$ denotes the symmetric difference of the edge sets, which is a contradiction. Another fact is that for any stabilizer state $|\mathcal{S}⟩$, there is a graph state $|\mathcal{G}⟩$ and a unitary operator $u\in {\mathcal{C}}_1^{\otimes n}$ such that $|\mathcal{S}⟩=u|\mathcal{G}⟩$ (local Clifford equivalence) [25].

Given a graph $\mathcal{G}$ and a classical linear code $\mathfrak{C}$, a graph code $(\mathcal{G},\mathfrak{C})$ is defined as the linear span of the states ${\mathit{Z}}^{\mathit{a}}|\mathcal{G}⟩$, where $\mathit{a}$ is any codeword in $\mathfrak{C}$. The simplest example of a graph code is yielded by a trivial graph with no edges. The distance of this code is 1 (see Remark 2).

Theorem 6. Given a graph $\mathcal{G}=(\mathcal{V},\mathfrak{E})$ and a linear code $\mathfrak{C}\in [n,k]$, let $Q=(\mathcal{G},\mathfrak{C})$ be the associated graph code. Then $Q\in [[n,k]]$.

Proof. Suppose that $Q\in [[n,k^{\mathrm{\prime }}]]$. We take into account that

$C{P}_{ij}=\frac{1}{2}(I+Z_i+Z_j-Z_i{Z}_j),$

then $Z_l$’s commute with $C{P}_{ij}$’s. For every $\mathit{a}=$$(a_1,...,a_n)\in \mathfrak{C}$, we define $|\mathit{a}⟩:={\mathit{Z}}^{\mathit{a}}|\mathcal{G}⟩$, therefore by applying (10)

$|\mathit{a}⟩={\displaystyle \prod _{l=1}^n{Z}_l^{a_l}{\displaystyle \prod _{(i,j)\in \mathfrak{E}}C{P}_{ij}|+{⟩}^{\otimes n}={\displaystyle \prod _{(i,j)\in \mathfrak{E}}C{P}_{ij}{\displaystyle \prod _{l=1}^n{Z}_l^{a_l}|+{⟩}^{\otimes n}.}}}}$

Since $|\mathfrak{C}|=2^k$ and $Z_l|+⟩=|-⟩$ where $|-⟩=\frac{|0⟩-|1⟩}{\sqrt{2}}$, then the set of states of the form ${\mathit{Z}}^{\mathit{a}}|+{⟩}^{\otimes n}$ constitutes an orthonormal basis of $2^k$ elements in which each qubit is $|+⟩$ or $|-⟩$. As $\prod _{(i,j)\in \mathfrak{E}}C{P}_{ij}$ is a unitary operator, it maps one orthonormal basis to another orthonormal basis, therefore $\text{dim}(Q)=2^k$ and $k^{\mathrm{\prime }}=k$.□

We recall that the support of a vector $\nu =({\nu }_1,...,{\nu }_n)$ is the set of indices $i$ for which ${\nu }_i\ne 0$ and is denoted by $\text{Supp}(\nu )$. After this note, we will construct a set of stabilizer generators for a graph code as follows.

Theorem 7. Given a graph $\mathcal{G}$ and a linear code $\mathfrak{C}\in [n,k]$, let ${{\mathit{a}}_1}^{\perp },...,{{\mathit{a}}_{n-k}}^{\perp }$ be a minimal weight generating set for the dual code ${\mathfrak{C}}^{\perp }$. The graph code $(\mathcal{G},\mathfrak{C})$ is a stabilizer code with the following stabilizer generators

$S_j={\displaystyle \prod _{i\in \text{Supp}({{\mathit{a}}_j}^{\perp })}{g}_i,}$

where $g_i$ is defined in Eq. (9).

Proof. Let $S$ be the stabilizer for $Q=(\mathcal{G},\mathfrak{C})$. We show that $S=⟨S_1,...,S_{n-k}⟩$. Independence of $S_i$’s follows from the linear independence of the binary vectors ${\mathit{a}}_i^{\perp }$’s. Since $[g_i,g_j]=0$ for all $i$ and $j$, then $S_i$’s commute. It remains to show that for every codeword $\mathit{a}\in \mathfrak{C}$, the state ${\mathit{Z}}^{\mathit{a}}|\mathcal{G}⟩$ is stabilized by $S_j$’s. For every $j$, we can rewrite $S_j$ as follows:

(11)$S_j={\displaystyle \prod _{i\in \text{Supp}({\mathit{a}}_j^{\perp })}{g}_i=(-1{)}^{\alpha }{\mathit{Z}}^{\mathit{b}}({\displaystyle \prod _{i\in \text{Supp}({\mathit{a}}_j^{\perp })}{X}_i),}}$

where $\alpha =0\text{or}1$, and $\mathit{b}$ is a binary vector. Since ${\mathit{a}}_j^{\perp }\in {\mathfrak{C}}^{\perp }$, then ${\mathit{Z}}^{\mathit{a}}$ and $\prod _{i\in \text{Supp}({\mathit{a}}_j^{\perp })}{X}_i$ commute, thus by applying Eq. (11) we have

$\begin{array}{rl}{S}_j{\mathit{Z}}^{\mathit{a}}|\mathcal{G}⟩=& (-1{)}^{\alpha }{\mathit{Z}}^{\mathit{b}}(\prod _{i\in \text{Supp}({\mathit{a}}_j^{\perp })}{X}_i){\mathit{Z}}^{\mathit{a}}|\mathcal{G}⟩\\ =& {\mathit{Z}}^{\mathit{a}}\prod _{i\in \text{Supp}({\mathit{a}}_j^{\perp })}{g}_i|\mathcal{G}⟩={\mathit{Z}}^{\mathit{a}}|\mathcal{G}⟩.\end{array}$

□

Graph codes play a key role in quantum technologies by yielding considerable protection against qubit loss, a dominant noise mechanism [26].

5.4 Cleaning lemma

Given an $[[n,k]]$ stabilizer code with stabilizer $S$. An operator (Pauli product) is said to be supported on a region $M$ (a subset of $n$ qubits) if it acts trivially on $M^c$ (the complement of $M$). The support of an operator $u$ is the minimal region on which $u$ is supported and is denoted by $\text{Supp}(u)$. According to Lemma 1, we can regard ${\mathcal{P}}_n$ as an $2n$-dimensional vector space on ${\mathbb{F}}_2$. We say a set of independent logical operators to mean one that maps to a linear independent set in the quotient vector space ${\mathcal{P}}_n/S$. We recall that two vectors are orthogonal (with respect to the symplectic inner product) if and only if the corresponding operators commute, thus $\mathcal{L}=S^{\perp }$ where $S^{\perp }$ is the orthogonal complement of $S$ in ${\mathcal{P}}_n$.

Lemma 5. Let $l(M)$ and $l(M^c)$ be the number of independent logical operators that can be supported on $M$ and $M^c$, respectively. Then $l(M)+l(M^c)=2k$.

Proof. Let ${\mathcal{P}}_M$ be the subspace of ${\mathcal{P}}_n$ which is supported on $M$. We can write $S$ as $S=S_M\oplus S_{M^c}\oplus \tilde{S}$, where $S_M=S\cap {\mathcal{P}}_M$ and $S_{M^c}=S\cap {\mathcal{P}}_{M^c}$ are the subspaces of $S$ which are supported on $M$ and $M^c$, respectively and $\tilde{S}$ includes whatever remains beyond $S_M\oplus S_{M^c}$. Let us define the restriction of a vector $\mathit{c}=(c_1,...,c_{2n})$ to $M$ as $\mathit{c}{|}_M:=\sum _{i\in M}(c_i{\mathit{e}}^i+c_{n+i}{\mathit{e}}^{n+i})$, where $\{{\mathit{e}}^i\}$ is the standard basis for ${\mathcal{P}}_n$. Let $\tilde{S}{|}_M$ denote the restriction of $\tilde{S}$ to $M$. We take into account that linearly independent vectors in $S_M+\tilde{S}$ remain linearly independent in $S_M+\tilde{S}{|}_M$, otherwise a nontrivial linear combination of the vectors would have a trivial restriction to $M$, thus would be in $S_{M^c}$. Since $S_{M^c}$ is trivially orthogonal to ${\mathcal{P}}_M$, then $(S^{\perp }{)}_M$ is the orthogonal complement of $(S_M+\tilde{S}){|}_M$ in ${\mathcal{P}}_M$. Hence,

(12)$\begin{array}{rl}\text{dim}(S^{\perp }{)}_M=& \text{dim}{\mathcal{P}}_M-\text{dim}(S_M+\tilde{S}{|}_M)\\ =& \text{dim}{\mathcal{P}}_M-\text{dim}{S}_M-\text{dim}\tilde{S}.\end{array}$

Similarly by replacing $M$ with $M^c$ we have

(13)$\begin{array}{rl}\text{dim}(S^{\perp }{)}_{M^c}=& \text{dim}{\mathcal{P}}_{M^c}-\text{dim}(S_{M^c}+\tilde{S}{|}_{M^c})\\ =& \text{dim}{\mathcal{P}}_{M^c}-\text{dim}{S}_{M^c}-\text{dim}\tilde{S}.\end{array}$

Since logical operators supported on $M$ ($M^c$) are elements of ${\mathcal{P}}_M$ (${\mathcal{P}}_{M^c}$) which commute with $S$ and are not contained in $S$, then by applying Eqs. (12) and (13)

$\begin{array}{rl}l(M)=& \text{dim}(S^{\perp }{)}_M-\text{dim}{S}_M\\ =& \text{dim}{\mathcal{P}}_M-2\text{dim}{S}_M-\text{dim}\tilde{S},\\ l(M^c)=& \text{dim}(S^{\perp }{)}_{M^c}-\text{dim}{S}_{M^c}\\ =& \text{dim}{\mathcal{P}}_{M^c}-2\text{dim}{S}_{M^c}-\text{dim}\tilde{S}.\end{array}$

It follows that

$\begin{array}{rl}l(M)+l(M^c)=& \text{dim}{\mathcal{P}}_M+\text{dim}{\mathcal{P}}_{M^c}-2(\text{dim}{S}_M\\ & +\text{dim}{S}_{M^c}+\text{dim}\tilde{S})\\ =& \text{dim}{\mathcal{P}}_n-2\text{dim}S=2n-2(n-k)=2k.\end{array}$

□

For a logical operator $u$, we say that $u$ can be cleaned on $M$, if there exists a logically equivalent operator $u^{\mathrm{\prime }}$, i.e., $u^{\mathrm{\prime }}=us$ where $s\in S$, such that $u^{\mathrm{\prime }}$ can be supported on $M^c$. Now we are ready to present the cleaning lemma [27, 28] as follows.

Corollary 3. Let $M$ be a region which does not support any nontrivial logical operator. Then any logical operator can be cleaned on $M$.

Proof. The assumption means that $l(M)=0$. Hence, by applying Lemma 5, it follows that $l(M^c)=2k$. Therefore, any logical operator may be supported on $M^c$. It means that any logical operator can be cleaned on $M$. In other words, for any logical operator $u$, we can choose an element $s=\prod _{i\in \mathrm{\Sigma }(M)}{g}_i^{x_i}\in S$, with $\mathrm{\Sigma }(M)=\{i:\text{Supp}(g_i)\cap$$M\ne \mathrm{\varnothing }\}$ and $x_i\in \{0,1\}$, such that $u^{\mathrm{\prime }}=us$ acts trivially on $M$.□

Given a lattice $\mathrm{\Lambda }=\{1,...,L{\}}^N$ ($L$ is sufficiently large) we say that a stabilizer code $Q$ with stabilizer $S=⟨g_1,...,g_m⟩$ is embeddable into $\mathrm{\Lambda }$, if we can associate the qubits to vertices of $\mathrm{\Lambda }$ such that each $g_i$ is supported only on one hypercube, say of size 1, of $\mathrm{\Lambda }$.

Theorem 8. Given an embeddable stabilizer code $Q\in [[n,k,d]]$ in an $N$-dimensional lattice, $d=O(n^{1-\frac{1}{N}}).$

Proof. We will prove the theorem for two-dimensional lattices, the higher dimensional case will be clear from $N=2$. Suppose that for some $M\gg 1$

(14)$d\ge M\sqrt{n}.$

For sufficiently large $L$, we can divide $\mathrm{\Lambda }$ into an even number of vertical strips, say $r$ strips, of width at most $\frac{M}{2}$ but still larger than 1. Let $u$ be a nontrivial logical operator on $\mathrm{\Lambda }$. According to Corollary 3, each vertical strip can be cleaned out by applying the generators whose supports overlap with that strip. We note that these supports are located on that strip or adjacent strips, but not on any other strips (Fig.2).

Fig.2 Applying the cleaning lemma.

Full size|PPT slide

By repeating this process, all even strips will be cleaned out and we obtain a logical operator $u^{\mathrm{\prime }}$ which is supported only on odd strips $u^{\mathrm{\prime }}=u_1^{\mathrm{\prime }}{u}_3^{\mathrm{\prime }}...u_{r-1}^{\mathrm{\prime }}$, where $u_i^{\mathrm{\prime }}$ is a Pauli product which is supported on the $i$-th strip. Since each generator $g_j$ overlaps with at most one odd strip and $u^{\mathrm{\prime }}\in N(S)$, then $u_i^{\mathrm{\prime }}\in N(S)$ for all $i=1,3,...,r-1$. Since $u^{\mathrm{\prime }}\notin S$, there is at least one odd strip $i$ such that $u_i^{\mathrm{\prime }}\notin S$ which means $u_i^{\mathrm{\prime }}$ is a nontrivial logical operator. But $w(u_i^{\mathrm{\prime }})<(\frac{M}{2})L=(\frac{M}{2})\sqrt{n}$ which is a contradiction with Eq. (14). Hence, $d=O(\sqrt{n})$.□

5.5 Generalization

The notion of stabilizer code can be generalized to qudits, i.e., $d$-level systems, where $d$ is a prime number. Here, the system has only a finite number of accessible states (degrees of freedom), thus the phase space needs to be discrete. In this case, the Hilbert spaces of constituents are ${\mathbb{C}}^d$ with the standard basis $|0⟩,...,|d-1⟩$. The shift operator and the clock operator are defined as follows:

$X|j⟩:=|j+1⟩,Z|j⟩:={\mathrm{e}}^{\frac{2\pi \mathrm{i}}{d}j}|j⟩,$

and modulo-$d$ arithmetic is used. These operators satisfy $X^d=Z^d=I$. We associate with each point $(x,p)\in {\mathbb{F}}_d^2$ in phase space a Weyl operator according $T(x,p):=X^x{Z}^p$. The Weyl operators can be conceived as generalized Pauli products. They satisfy the Weyl commutation relations:

$T(x,p)T(x^{\mathrm{\prime }},p^{\mathrm{\prime }})=e^{\frac{-2\pi i}{d}{p}^{\mathrm{\prime }}x}T(x+x^{\mathrm{\prime }},p+p^{\mathrm{\prime }}).$

It follows that two Weyl operators $T(x,p)$ and $T(x^{\mathrm{\prime }},p^{\mathrm{\prime }})$ commute if and only if the standard symplectic inner product vanishes

$[(x,p),(x^{\mathrm{\prime }},p^{\mathrm{\prime }})]:=(x,p)\left(\begin{array}{cc}0& -1\\ 1& 0\end{array}\right)(x^{\mathrm{\prime }},p^{\mathrm{\prime }}{)}^t=p{x}^{\mathrm{\prime }}-x{p}^{\mathrm{\prime }}.$

For $n$ qudits, we can encounter (position and momentum) coordinates $(x_1,p_1,...,x_n,p_n)$ in phase space with $\mathit{x}=(x_1,...,x_n),\mathit{p}=(p_1,...,p_n)\in {\mathbb{F}}_d^n$. The above inner product gives rise to the following form

(15)$[(\mathit{x},\mathit{p}),({\mathit{x}}^{\mathrm{\prime }},{\mathit{p}}^{\mathrm{\prime }})]=(\mathit{x},\mathit{p})\mathrm{\Omega }({\mathit{x}}^{\mathrm{\prime }},{\mathit{p}}^{\mathrm{\prime }}{)}^t,$

where $\mathrm{\Omega }:=\underset{j=1}{\overset{n}{⨁}}\left(\begin{array}{cc}0& -1\\ 1& 0\end{array}\right)$. The generalized Weyl operator is defined by

$\mathit{T}(\mathit{x},\mathit{p}):={\displaystyle \underset{j=1}{\overset{n}{⨂}}T(x_j,p_j).}$

Let $\mathfrak{W}(\mathit{x},\mathit{p}):={\mathrm{e}}^{\frac{-\pi \mathrm{i}}{d}⟨\mathit{x},\mathit{p}⟩}\mathit{T}(\mathit{x},\mathit{p})$. An isotropic subspace $\mathfrak{V}\subset {\mathbb{F}}_d^{2n}$ is a subspace on which the inner product of Eq. (15) vanishes. A character $\chi$ is a map from $\mathfrak{V}$ into the circle group $\mathbb{T}=\{z\in \mathbb{C}:|z|=1\}$. A generalized stabilizer code associated with $\mathfrak{V}$ and $\chi$ is defined as follows

$\begin{array}{rl}Q=& \{|\psi ⟩\in ({\mathbb{C}}^d{)}^{\otimes n}:{\chi }^{\ast }(\mathit{x},\mathit{p})\mathfrak{W}(\mathit{x},\mathit{p})|\psi ⟩\\ =& |\psi ⟩,\mathrm{\forall }(\mathit{x},\mathit{p})\in \mathfrak{V}\}.\end{array}$

The generalized Clifford group is defined as the set of unitary operators $u$ that map Weyl operators onto Weyl operators under conjugation, i.e.,

$u\mathfrak{W}(\mathit{x},\mathit{p})u^{†}\propto \mathfrak{W}(\mathfrak{G}(\mathit{x},\mathit{p})),$

where $\mathfrak{G}$ belongs to the symplectic group induced by Eq. (15) and $\propto$ is the symbol of proportionality.

Remark 3. We take into account that the direct analog of stabilizer states makes sense in the setting of continuous Weyl systems by describing singular states within an algebraic approach [29].

In the following section, we study stabilizer circuits as a very important class of quantum circuits. In fact, they are sufficient to implement many quantum algorithms and protocols.

6 Stabilizer circuits

In quantum computation, it is more convenient to work with circuit model rather than matrix equivalent representation. For example, four gates are allowed in the stabilizer formalism, including controlled NOT (CNOT), phase (P), Hadamard (H) and measurement (M) are given below:

Fig.3

Full size|PPT slide

where $\oplus$ is the addition modulo 2 and

$\begin{array}{rl}& \mathbf{C}\mathbf{N}\mathbf{O}\mathbf{T}=\frac{1}{2}(I_1{I}_2+Z_1{I}_2+I_1{X}_2-Z_1{X}_2),\\ & \mathit{P}=\frac{1}{\sqrt{2}}(I-\mathrm{i}Z),\mathit{H}=\frac{1}{\sqrt{2}}(X+Z).\end{array}$

6.1 Simulating the stabilizer gates

Up to a global phase, the Clifford group ${\mathcal{C}}_n$ is generated by one and two qubit gates in the set $\{\mathit{H},\mathit{P},\mathbf{C}\mathbf{N}\mathbf{O}\mathbf{T}\}$, which are called the Clifford gates [30]. Let $f$ and $g$ be two positive functions, we write $f\in O(g)$ if ${\text{limsup}}_{n\to \mathrm{\infty }}\frac{f(n)}{g(n)}<\mathrm{\infty }$, and $f\in \mathrm{\Theta }(g)$ if ${\text{limsup}}_{n\to \mathrm{\infty }}\frac{f(n)}{g(n)}<\mathrm{\infty }$ and ${\text{liminf}}_{n\to \mathrm{\infty }}\frac{f(n)}{g(n)}>0$.

Theorem 9. Simulating a Clifford gate on an $n$-qubit stabilizer state requires $\mathrm{\Theta }(n)$ time, while a measurement gate is simulated in $O(n^2)$ time for random outcomes and in $O(n^3)$ time for deterministic outcomes.

Proof. Given an $n$-qubit stabilizer state $|\psi ⟩$ with stabilizer $S$, we apply the idea of representing $|\psi ⟩$ by a stabilizer matrix $\mathfrak{M}$ whose rows are a set of generators of $S$. Accordingly, any computational basis state can be represented as follows, where signs $\pm$ denote global phases $\pm 1$ for the respective generator,

$\begin{array}{c}\pm \\ \pm \\ \pm \\ ⋮\\ \pm \end{array}\left(\begin{array}{ccccc}{Z}_1& I& I& \dots & I\\ I& Z_2& I& \dots & I\\ I& I& Z_3& \dots & I\\ ⋮& ⋮& ⋮& ⋮& ⋮\\ I& I& \dots & I& Z_n\end{array}\right).$

By simulating a Clifford gate $u$ on $|\psi ⟩$, $g_i$, the $i$-th row of $\mathfrak{M}$, is mapped to $u{g}_i{u}^{†}$, hence at most two columns of $\mathfrak{M}$ are updated. Therefore, $u$ is simulated in $\mathrm{\Theta }(n)$ time. We note that each qubit in $|\psi ⟩$ is either in a $|0⟩(|1⟩)$ state, deterministic outcome, or in an unbiased superposition of both states, random outcome. In the case of random outcome, we flip an unbiased coin to decide the outcome $x\in \{0,1\}$ and then update $\mathfrak{M}$ to match the outcome. Let $g_j$ be a row in $\mathfrak{M}$ with an $X(Y)$ operator in its $j$-th position. The global phase of $Z_j$ is set to +1(−1) if $x=0(1)$. Based on the fact that $g_j$ and $Z_j$ anti-commute, if any other rows in $\mathfrak{M}$ anti-commute with $Z_j$, we multiply them by $g_j$ to make them commute with $Z_j$. After that, we replace $g_j$ with $Z_j$. This process needs up to $n$ row multiplications, then the overall runtime is $O(n^2)$. In the case of deterministic outcome, we need to find out whether the qubit is in the $|0⟩(|1⟩)$ state. In other words, whether the qubit is stabilized by $Z(-Z)$. In this way, we can perform Gaussian elimination to convert $\mathfrak{M}$ into a row-echelon form as follows:

$\left(\begin{array}{cccccc}X& & & & & \\ & X& & & {\mathfrak{A}}_1& \\ & & & \ddots & & & & \\ & {\mathfrak{A}}_2& & & & X\\ \stackrel{}{Z}& & & & & \\ & Z& & & {\mathfrak{A}}_3& \\ & & & \ddots & & & & \\ & {\mathfrak{A}}_4& & & & Z\end{array}\right),$

where entries in ${\mathfrak{A}}_{\mathfrak{1}}$ (upper $X$-diagonal) are $I,X,Y$ or $Z$, entries in ${\mathfrak{A}}_{\mathfrak{2}}$ (lower $X$-diagonal) and ${\mathfrak{A}}_{\mathfrak{3}}$ (upper $Z$-diagonal) are $I$ or $Z$, and entries in ${\mathfrak{A}}_{\mathfrak{4}}$ (lower $Z$-diagonal) are only $I$. This process removes redundant operators from $\mathfrak{M}$, then it is possible to identify the row as $Z_j$. The $\pm$ phase of this row decides the outcome of the measurement. Since the Gaussian elimination process takes $O(n^3)$ time, thus the runtime is $O(n^3)$.□

6.2 Knill−Gottesman theorem

Given a quantum circuit $\mathcal{U}$ with $n$ input qubits as one bit string, e.g., $|0{⟩}^{\otimes n}$, by measuring the qubits, we would read out some sample bits $\phi \in \{0,1{\}}^n$, with probability $\mathbb{P}(\phi )=|⟨\phi |\tau ⟩{|}^2$, where $|\tau ⟩=\mathcal{U}|0{⟩}^{\otimes n}$. A classical simulation of a quantum circuit is the process of sampling from the output distribution efficiently using a classical probabilistic computer. By simulating a circuit, we will obtain an outcome $\phi$ that is in accordance with the probability distribution $\mathbb{P}(\phi )$.

Theorem 10. (Knill−Gottesman theorem [16]) Any quantum circuit that applies only the following elements can be simulated efficiently (in polynomial time) on a classical probabilistic computer.

● Preparation of qubits in computational basis states;

● Quantum gates from ${\mathcal{C}}_n$;

● Measurements in the computational basis.

Proof. Without loss of generality, we start with the state $|0{⟩}^{\otimes n}$ which is a stabilizer state with stabilizer $S=⟨Z_1,Z_2,...,Z_n⟩$. Let $u$ be a generator of ${\mathcal{C}}_n$ and $|{\psi }^{\mathrm{\prime }}⟩=u|\psi ⟩$. It follows that $|{\psi }^{\mathrm{\prime }}⟩$ is a stabilizer state with stabilizer $uS{u}^{†}=⟨u{Z}_1{u}^{†},u{Z}_2{u}^{†},...,u{Z}_n{u}^{†}⟩$. Implementing a generator $u$ implies updating the $n$ generators which describe the initial state. This step requires $O(n^2)$ operations on a classical computer [30]. If our circuit is a product of $m$ terms, each a generator of ${\mathcal{C}}_n$, then the computation can be simulated by a classical computer in $O(m{n}^2)$ time.□

A circuit satisfying the conditions of Theorem 10 is called a stabilizer circuit. Stabilizer circuits refer to quantum circuits including all of the four types of stabilizer gates, while unitary stabilizer circuits consist of only the Clifford gates. By adding any non-Clifford gate to the set of Clifford gates, we obtain a set of universal gates for quantum computation, while stabilizer circuits are probably not even universal for classical computation [30]. From Theorem 10, it follows that quantum algorithms employing the entanglement created by Clifford gates do not give any advantage over classical computers.

6.3 Tableau representation

Let $|\psi ⟩$ be an $n$-qubit stabilizer state with stabilizer $S=⟨g_1,g_2,...,g_n⟩$. We may write $S=⟨{\tilde{Z}}_1,{\tilde{Z}}_2,...,{\tilde{Z}}_n⟩$, where ${\tilde{Z}}_i$ acts on $|\psi ⟩$ just as $Z_i$ acts on $|0{⟩}^{\otimes n}$. In other words, we can think of the generators as surrogate $Z$ operators. The operators ${\tilde{Z}}_i$’s are called the canonical Z operators on a set of virtual qubits (syndrome qubits).

A destabilizer (group) D associated with a stabilizer $S=⟨g_1,g_2,...,g_k⟩$, is a stabilizer of ${\mathcal{P}}_n$, generated as $D=⟨d_1,d_2,...,d_k⟩$ such that for each $i$,

$\{d_i,g_i\}=0,[d_i,g_j]=0\mathrm{\forall }j\ne i.$

Just as stabilizer generators can be thought of as canonical $Z$ operators, destabilizer generators can be thought of as canonical $X$ operators.

Let $S$ be a stabilizer of ${\mathcal{P}}_n$ with $n$ generators. A full tableau is a pair $\mathfrak{T}=(S,D)$, where $D$ is a corresponding destabilizer.

Proposition 2. Given a full tableau $\mathfrak{T}=(S,D)$, every $u\in {\mathcal{P}}_n$ can be decomposed as $u=i^k\mathfrak{d}s$ in $O(n^2)$ time, where $k\in \{0,1,2,3\}$, $\mathfrak{d}\in D$ and $s\in S$.

Proof. Since $\mathfrak{T}$ is a full tableau, then generators of $S(D)$ are $n$ canonical $Z(X)$ operators and up to a global phase, they can together generate ${\mathcal{P}}_n$. Therefore, such a decomposition exists. Given $u\in {\mathcal{P}}_n$, $g_j(d_j)$ is in the factorization of $s(\mathfrak{d})$ if and only if $\{u,d_j\}=0$ ($\{u,g_j\}=0$). We note that checking each of the $2n$ anti-commutation relations takes $O(n)$ time. After finding $\mathfrak{d}$ and $s$, we compare the phases of $\mathfrak{d}s$ and $u$ to find $k$, which gives the desired decomposition in $O(n^2)$ time.□

The matrix representation of a full tableau $\mathfrak{T}=(S,D)$ is an $2n\times (2n+1)$ matrix $\mathcal{T}$ as follows:

$\mathcal{T}=\left(\begin{array}{ccc}{b}_1(d_1)& b_2(d_1)& {\alpha }_1\\ ⋮& ⋮& ⋮\\ b_1(d_n)& b_2(d_n)& {\alpha }_n\\ \stackrel{}{b_1}(g_1)& \stackrel{}{b_2}(g_1)& \stackrel{}{{\alpha }_{n+1}}\\ ⋮& ⋮& ⋮\\ b_1(g_n)& b_2(g_n)& {\alpha }_{2n}\end{array}\right),$

where ${\alpha }_i=0(1)$ if the global phase of the $i$-th generator is 1(−1). The standard initial tableau $\mathcal{I}$ is the following matrix,

$\mathcal{I}=\left(\begin{array}{ccc}I& \mathit{0}& \begin{array}{c}\stackrel{}{0}\\ ⋮\\ \underset{}{0}\end{array}\\ \mathit{0}& I& \begin{array}{c}\stackrel{}{0}\\ ⋮\\ 0\end{array}\end{array}\right).$

We say that two $n$-qubit unitary stabilizer circuits ${\mathcal{U}}_1$ and ${\mathcal{U}}_2$ are equivalent, if the final states of them are equal, i.e., ${\mathcal{U}}_1(|\psi ⟩)={\mathcal{U}}_2(|\psi ⟩)$ for all stabilizer states $|\psi ⟩$. By applying linearity, it follows that two equivalent stabilizer circuits have the same action on all states. In addition, there is a one-to-one correspondence between unitary stabilizer circuits and tableaus. That means, given a tableau matrix $\mathcal{T}$, there is a unitary stabilizer circuit $\mathcal{U}$ such that $\mathcal{T}$ is the final tableau when $\mathcal{U}$ is run on $\mathcal{I}$. This fact is based on a key theorem which says any unitary stabilizer circuit has an equivalent circuit in canonical form, i.e., it consists of 11 rounds in the following sequence [16],

$\begin{array}{rl}& \mathit{H}-\mathbf{C}\mathbf{N}\mathbf{O}\mathbf{T}-\mathit{P}-\mathbf{C}\mathbf{N}\mathbf{O}\mathbf{T}-\mathit{P}-\mathbf{C}\mathbf{N}\mathbf{O}\mathbf{T}\\ & -\mathit{H}-\mathit{P}-\mathbf{C}\mathbf{N}\mathbf{O}\mathbf{T}-\mathit{P}-\mathbf{C}\mathbf{N}\mathbf{O}\mathbf{T}.\end{array}$

Corollary 4. An $n$-qubit state $|\psi ⟩$ is a stabilizer state if and only if it can be obtained from $|0{⟩}^{\otimes n}$ by a stabilizer circuit.

Proof. Given a stabilizer state $|\psi ⟩$, let $\mathcal{T}$ be its tableau matrix and $\mathcal{U}$ be the unitary stabilizer circuit corresponding to $\mathcal{T}$. Therefore, $\mathcal{U}|0{⟩}^{\otimes n}=|\psi ⟩$. The proof of converse direction is clear.□

Corollary 5. Any $n$-qubit stabilizer state $|\psi ⟩$ can be transformed into the state $|0{⟩}^{\otimes n}$ by applying a stabilizer circuit.

Proof. According to Corollary 4, there is a unitary stabilizer circuit $\mathcal{U}$ such that $\mathcal{U}|0{⟩}^{\otimes n}=|\psi ⟩$. It suffices to reverse $\mathcal{U}$ to do the inverse transformation. In this way, we reverse the order of gates and replace every $\mathit{P}$ gate with $\mathit{P}\mathit{P}\mathit{P}$.□

There is a simulation algorithm based on applying tableaus which takes $O(n^2)$ time for measurements [16]. Furthermore, tableau representation has a key role in the development of simulation algorithms in the generalized stabilizer formalism [31].

6.4 Frame representation

Let $\mathfrak{M}$ be the stabilizer matrix of an $n$-qubit stabilizer state $|\psi ⟩$. By modifying the leading phases $\pm$ of $\mathfrak{M}$, we can construct $2^n-1$ additional orthogonal stabilizer states. These states, together with $|\psi ⟩$, form an orthonormal basis. This basis is specified by $|\psi ⟩$, and any of the other basis states specifies the same basis.

A set of $k\le 2^n$ stabilizer states $\{|{\psi }_j⟩{\}}_{j=1}^k$ which form an orthonormal basis for a subspace of $H^{\otimes n}$, is called an $n$-qubit frame $\mathcal{F}$ [32]. We represent $\mathcal{F}$ by a pair $(\mathfrak{M},\{{\varrho }_j{\}}_{j=1}^k)$, where $\mathfrak{M}$ is a stabilizer matrix and $\{{\varrho }_j{\}}_{j=1}^k$ is a set of distinct phase vectors with ${\varrho }_j\in \{+1,-1{\}}^n$. We represent $|{\psi }_j⟩$ by ${\mathfrak{M}}^{{\varrho }_j}$ denoting the ordered assignment of the elements in ${\varrho }_j$ as the $\pm 1$-phases of the rows in $\mathfrak{M}$. The size of the frame is denoted by $|\mathcal{F}|$, which is equal to $k$. As an example, for stabilizer states $|{\psi }_1⟩=\frac{|00⟩+|01⟩}{\sqrt{2}}$ and $|{\psi }_2⟩=\frac{|10⟩+|11⟩}{\sqrt{2}}$, with ${\varrho }_1:(+,+)$ and ${\varrho }_2:(-,+)$ we have

${\mathfrak{M}}^{{\varrho }_1}=\begin{array}{c}+\\ +\end{array}\left(\begin{array}{cc}Z& I\\ I& X\end{array}\right)\equiv |{\psi }_1⟩,$

${\mathfrak{M}}^{{\varrho }_2}=\begin{array}{c}-\\ +\end{array}\left(\begin{array}{cc}Z& I\\ I& X\end{array}\right)\equiv |{\psi }_2⟩.$

Consider state $|1⟩$ which is stabilized by $-Z$. Conjugating the stabilizer by the phase gate gives $\mathit{P}(-Z){\mathit{P}}^{†}=-Z$. However, in the vector representation we have $\mathit{P}|1⟩=\mathrm{i}|1⟩$. Hence, the global phase $i$ is not maintained by the stabilizer. This example shows that when simulating single stabilizer states, global phases are unobservable. However, when simulating stabilizer-state superpositions, global phases become relative. To see this, we note that acting a Clifford gate $u$ on $\mathcal{F}$ maps the basis $\{|{\psi }_j⟩\}$ to $\{{\mathrm{e}}^{\mathrm{i}{\theta }_j}|{\varphi }_j⟩\}$, where ${\mathrm{e}}^{\mathrm{i}{\theta }_j}$ is the global phase of the stabilizer state $|{\varphi }_j⟩$. In other words, this operation rotates $\mathcal{F}$ and along this rotation, the superposition $|\mathrm{\Psi }⟩=\sum _{j=1}^k{\nu }_j|{\psi }_j⟩$ maps to $|\mathrm{\Phi }⟩=\sum _{j=1}^k{\nu }_j{\mathrm{e}}^{\mathrm{i}{\theta }_j}|{\varphi }_j⟩$. Here, the global phase ${\mathrm{e}}^{\mathrm{i}{\theta }_j}$ of each $|{\varphi }_j⟩$ becomes relative with respect to $|\mathrm{\Phi }⟩$, thus we need to compute such phases.

Stabilizer frames provide a simulation algorithm based on the global-phase maintenance as follows. According to Corollary 4, for any stabilizer state $|\psi ⟩$ there exists a stabilizer circuit $\mathcal{U}$ such that $|\psi ⟩=\mathcal{U}|0{⟩}^{\otimes n}$. To compute the global phase of $|\psi ⟩$, we can keep an account of the global factors generated when each gate in $\mathcal{U}$ is simulated sequentially. In this way, the global phase of each state in $\mathcal{F}$ is maintained by using the amplitude vector $\mathbf{v}=({\nu }_1,...,{\nu }_k)\in {\mathbb{C}}^k$. Each ${\nu }_j$ forms a pair with phase vector ${\varrho }_j$, and in the process of simulating Clifford gates $u$, ${\nu }_j$ is updated according to the following algorithm.

Algorithm 2. (Updating global phases)

1) Set the $\pm$-phases of $\mathfrak{M}$ to ${\varrho }_j$.

2) Store nonzero amplitude $\alpha$ of the basis state $|\tau ⟩\equiv {\mathfrak{M}}^{{\varrho }_j}$.

3) Find state $|{\tau }^{\mathrm{\prime }}⟩$ and amplitude ${\alpha }^{\mathrm{\prime }}$ by computing $u(\alpha |\tau ⟩)={\alpha }^{\mathrm{\prime }}|{\tau }^{\mathrm{\prime }}⟩$.

4) Find $|{\tau }^{\mathrm{\prime }}⟩$ by computing $u\mathfrak{M}{u}^{†}$ and store its amplitude $\beta \ne 0$.

5) Update the global factor as ${\nu }_j\leftarrow \frac{{\nu }_j{\alpha }^{\mathrm{\prime }}}{\beta }$.

We note that in step 2, for $u=\mathit{H}$, it may be necessary to sample a sum of two nonzero (real and imaginary) basis amplitudes.

In order to sample the computational-basis amplitudes $\alpha$ and ${\alpha }^{\mathrm{\prime }}$, $\mathfrak{M}$ needs to be in row-echelon form (see Theorem 9). Therefore, simulating with global phase-maintenance takes $O(k{n}^3)$ time. We can improve this runtime by noting that during simulation, the form of $\mathfrak{M}$ is invariant, i.e., $\mathfrak{M}$ remains in row-echelon form. This invariance can be repaired with $O(n)$ row multiplications, each of which with $\mathrm{\Theta }(n)$ runtime. It results that updating $\mathfrak{M}$ takes $O(n^2)$ time. Hence, the overall runtime for simulating a Clifford gate is $O(n^2+kn)$.

In the next section, we study some important classes of quantum channels, which have a key role in quantum information theory.

7 Quantum channels

Let $\mathrm{\Phi }:{\mathbb{C}}^{n\times n}\to {\mathbb{C}}^{l\times l}$ be a linear map. $\mathrm{\Phi }$ is called positive, if for any positive semi-definite matrix $A\in {\mathbb{C}}^{n\times n}$, $\mathrm{\Phi }(A)\in {\mathbb{C}}^{l\times l}$ is so. Given a positive integer $m$, $\mathrm{\Phi }$ is called $m$-positive, if $\mathrm{\Phi }\otimes {\text{Id}}_m:{\mathbb{C}}^{n\times n}⨂{\mathbb{C}}^{m\times m}\to {\mathbb{C}}^{l\times l}⨂{\mathbb{C}}^{m\times m}$ is a positive map, where ${\text{Id}}_m:{\mathbb{C}}^{m\times m}\to {\mathbb{C}}^{m\times m}$ is the identity map. $\mathrm{\Phi }$ is called completely positive, if for any positive integer $m$, $\mathrm{\Phi }$ is $m$-positive. $\mathrm{\Phi }$ is called trace-preserving, if $\text{tr}(\mathrm{\Phi }(A))=\text{tr}(A)$, for every $A$. A completely positive and trace-preserving map is called quantum channel. For example, Pauli channel ${\mathrm{\Phi }}_P$ maps an input state with density operator $\rho$ as follows:

${\mathrm{\Phi }}_P(\rho )=p_{0}I\rho I+p_{x}X\rho X+p_{y}Y\rho Y+p_{z}Z\rho Z,$

where $p_i\ge 0$ and $\sum _i{p}_i=1$. In the case of $p_x=p_y=p_z=\frac{p}{3}$, the Pauli channel is called the depolarizing channel, which is one of the most important instances of diagonal channels [33].

7.1 Stabilizer channels

A quantum channel $\mathrm{\Phi }$ that maps any stabilizer state $|\psi ⟩⟨\psi |$ to a stabilizer state $\mathrm{\Phi }(|\psi ⟩⟨\psi |)$ is called a stabilizer channel. Stabilizer channels include two classes of quantum channels. The first one is the class of Clifford channels, i.e. channels that map $\rho$ to $u\rho u^{†}$ where $u$ is a Clifford operator. The second one is the class of nonunitary channels on the space of stabilizer states, which map any state to a determined state.

A Pauli reset channel associated with a Pauli product $u$ is an example of stabilizer channels, which sets any given qubit to a +1 eigenvector of $u$. This channel is denoted by $R_u$ and can be written as follows:

(16)$R_u(\rho )={\displaystyle \frac{I+u}{2}}\rho {\displaystyle \frac{I+u}{2}}+{\mathit{C}}_{u\to -u}{\displaystyle \frac{I-u}{2}}\rho {\displaystyle \frac{I-u}{2}},$

where ${\mathit{C}}_{u\to -u}$ is the Clifford channel that maps $u$ to $-u$. We note that $\frac{I\pm u}{2}$ is the projector onto the $\pm 1$ eigenspace of $u$. Stabilizer channels give rise to calculate the expectation value for an observable on the final state of a circuit by using the Monte Carlo method [34].

Theorem 11. Any quantum channel $\mathrm{\Phi }$ can be decomposed as $\mathrm{\Phi }=\sum _i{\lambda }_i{\mathrm{\Psi }}_i$, where ${\mathrm{\Psi }}_i$’s are stabilizer channels and ${\lambda }_i\in \mathbb{R}$ with $\sum _i{\lambda }_i=1$.

Proof. For Pauli products $u$ and $u^{\mathrm{\prime }}$, let ${\mathrm{\Phi }}_{u\to u^{\mathrm{\prime }}}$ be the superoperator (generally unphysical channel) that maps $u$ to $u^{\mathrm{\prime }}$ and every other Pauli product to $0$. Since Pauli products span the space of operators on $n$ qubits, thus $\{{\mathrm{\Phi }}_{u\to u^{\mathrm{\prime }}}\}$ is a basis for the space of $n$ qubit channels. For Pauli products $u$ and $v$ we define $\mathrm{△}(u,v):=1(-1)$ when $u$ and $v$ commute (anti-commute). Since every nonidentity Pauli product $u$ commutes with exactly half of the Pauli products and anti-commutes with the remaining elements, then

(17)${\displaystyle \sum _v\mathrm{△}(u,v)=\{\begin{array}{ll}{4}^n& \text{u}=I,\\ 0& \text{otherwise.}\end{array}}$

Let ${\mathrm{\Phi }}_v$ be the channel that maps $\rho$ to $v\rho v^{†}$, then by applying Eq. (17) and the fact that $\mathrm{△}(u,v)\mathrm{△}(u^{\mathrm{\prime }},v)=\mathrm{△}(u{u}^{\mathrm{\prime }},v)$ we have

(18)$\begin{array}{rl}\sum _v\mathrm{△}(u,v){\mathrm{\Phi }}_v(u^{\mathrm{\prime }})=& \sum _v\mathrm{△}(u,v)v{u}^{\mathrm{\prime }}{v}^{†}\\ =& u^{\mathrm{\prime }}\sum _v\mathrm{△}(u,v)\mathrm{△}(u^{\mathrm{\prime }},v)\\ =& \{\begin{array}{ll}{4}^n{u}^{\mathrm{\prime }}& u^{\mathrm{\prime }}=u,\\ 0& \text{otherwise}\end{array}=4^n{\mathrm{\Phi }}_{u\to u}(u^{\mathrm{\prime }}).\end{array}$

It shows that ${\mathrm{\Phi }}_{u\to u}$ can be decomposed as a linear combination of stabilizer channels with real coefficients summing to 1. By applying Eq. (16) we obtain the following decomposition for ${\mathrm{\Phi }}_{I\to u}$ where $u\ne I$,

(19)${\mathrm{\Phi }}_{I\to u}=R_u{\mathrm{\Phi }}_{I\to I}-{\mathrm{\Phi }}_{I\to I}.$

For $u\ne u^{\mathrm{\prime }}$ and $u,u^{\mathrm{\prime }}\ne I$, we can decompose ${\mathrm{\Phi }}_{u\to u^{\mathrm{\prime }}}$ as follows

(20)${\mathrm{\Phi }}_{u\to u^{\mathrm{\prime }}}={\mathit{C}}_{u\to u^{\mathrm{\prime }}}{\mathrm{\Phi }}_{u\to u},$

where ${\mathit{C}}_{u\to u^{\mathrm{\prime }}}$ is the Clifford channel that maps $u$ to $u^{\mathrm{\prime }}$. We take into account that a quantum channel cannot have a superoperator of the form ${\mathrm{\Phi }}_{u\to I}$ as a component, since this superoperator maps two operators $\frac{I+u}{2}$ and $\frac{I-u}{2}$ which have equal traces to operators with nonequal traces. Equations (18)−(20) show that each allowed basis element ${\mathrm{\Phi }}_{u\to u^{\mathrm{\prime }}}$ can be decomposed as desired, so can any quantum channel.□

This decomposition is more important than the decomposition of unitary channels as the complex linear combinations of Pauli channels [16]. In fact, the importance of this decomposition is that it can represent both unitary and non-unitary channels. As an example, let ${\mathrm{\Psi }}_T:\rho \mapsto T\rho T^{†}$, ${\mathrm{\Psi }}_Z:\rho \mapsto Z\rho Z$ and ${\mathrm{\Psi }}_{\mathit{P}}:\rho \mapsto \mathit{P}\rho {\mathit{P}}^{†}$ be the channels corresponding to $T:=\sqrt{\mathit{P}}$, $Z$ and $\mathit{P}$ gates, respectively. We have the following stabilizer decomposition

${\mathrm{\Psi }}_T={\displaystyle \frac{1}{2}}\mathit{I}+{\displaystyle \frac{1-\sqrt{2}}{2}}{\mathrm{\Psi }}_Z+{\displaystyle \frac{\sqrt{2}}{2}}{\mathrm{\Psi }}_{\mathit{P}},$

where $\mathit{I}$ is the identity channel.

We note that the stabilizer decomposition is not unique and ${\lambda }_i$’s may be negative. Each term in this decomposition describes a physical process and only when ${\lambda }_i\ge 0$ for all $i$, they can be interpreted as probabilities of physical processes. Generally, ${\lambda }_i$’s may be considered as a quasiprobability distribution. Accordingly, we can define negativity of a decomposition as follows: $\varsigma =\sum _{i:{\lambda }_i<0}|{\lambda }_i|$. In fact, $\varsigma >0$ indicates nonclassical behaviour and traces back to the development of the Wigner function [35].

7.2 Capacity of the erasure channel

The capacity of a quantum channel is the highest rate of reliable information transmission through many independent uses of the channel. To determine reliability, we need to compare the input and output states, ${\rho }_{\text{in}}$ and ${\rho }_{\text{out}}$, by applying the following functional which is called the fidelity, $\mathit{F}=⟨\psi |{\rho }_{\text{out}}|\psi ⟩$, where ${\rho }_{\text{in}}=|\psi ⟩⟨\psi |$ and ${\rho }_{\text{out}}$ is typically a mixed state. The quantum capacity ${\mathrm{C}}_{\mathrm{\Phi }}$ of a quantum channel $\mathrm{\Phi }$ is the largest number $\mathrm{C}$ such that for any $\mathrm{R}<\mathrm{C}$ and any $ϵ>0$, there are block sizes $k$ and $n$ and a quantum error-correcting code mapping states $|\psi ⟩$ of $k$ qubits into $n$ independent uses of the channel with $\frac{k}{n}>\mathrm{R}$, such that every state $|\psi ⟩$ can be recovered with fidelity at least $1-ϵ$ at the receiving end.

The encoder $\mathcal{E}$ and decoder $\mathcal{D}$ are completely positive and trace preserving maps such that $\mathcal{E}$ maps $k$ qubits into $n$ intermediate systems, then each of them is sent through an independent instance of the channel $\mathrm{\Phi }$, and finally $\mathcal{D}$ maps the $n$ channel outputs into $k$ qubits (Fig.4).

Fig.4 Quantum information transfer using a code has a rate $\frac{k}{n}$ of $\frac{3}{4}$.

Full size|PPT slide

A quantum erasure channel with probability $p$ is a quantum channel from states in $H\simeq {\mathbb{C}}^2$ into states in $H\oplus \mathbb{C}|2⟩\simeq {\mathbb{C}}^3$ defined by

${\mathrm{\Phi }}_p:|\psi ⟩⟨\psi |⟼(1-p)|\psi ⟩⟨\psi |+p|2⟩⟨2|,$

where $|2⟩$ is an orthogonal state to $H$ and corresponds to a lost qubit. When we apply the erasure channel, each qubit is erased independently with probability $p$. An erased qubit is subjected to a random uniform Pauli error ($I,X,Y$ or $Z$ with equal probability $\frac{1}{4}$) and we know that this qubit is erased.

For $n$ qubits, the characteristic vector of the erased locations, ${\mathcal{E}}^p=(({\mathcal{E}}^p{)}_1,...,({\mathcal{E}}^p{)}_n)$, is defined as an element of ${\mathbb{F}}_2^n$ which each of its components follows a Bernoulli distribution of probability $p$. When a quantum state is subjected to a random Pauli error $E=E_1...E_n\in {\mathcal{P}}_n$, the qubit in location $i$ is lost if and only if $({\mathcal{E}}^p{)}_i=1$. And $E_i=I$ if $({\mathcal{E}}^p{)}_i=0$. We say that erasure ${\mathcal{E}}^p$ covers the error $E$, if $\text{Supp}(E)\subset {\mathcal{E}}^p$, i.e., the support of $E$ is included in the set of erased locations.

An encoded state $|\psi ⟩$ is transformed by a random error $E$ into a state $E|\psi ⟩$ for which we know that ${\mathcal{E}}^p$ covers $E$. To recover the original state, we need to compute the corresponding syndrome of $E$ and then infer an error $E^{\mathrm{\prime }}$ covered by ${\mathcal{E}}^p$. If $E$ and $E^{\mathrm{\prime }}$ are in the same coset of ${\mathcal{P}}_n/S$, then $E^{\mathrm{\prime }}E|\psi ⟩=|\psi ⟩$ and therefore the effect of $E$ is corrected. In this case, the erasure is called correctable. If $E^{\mathrm{\prime }}$ is not equivalent to $E$, we cannot recover the quantum state in general. In this case, the erasure is called non-correctable. To see an example of a non-correctable erasure, refer to Ref. [36].

The capacity of ${\mathrm{\Phi }}_p$ is upper bounded by $1-2p$, which follows from the no-cloning theorem, see Ref. [37]. Hence, it does not rely on the quantum code structure. Therefore, we can find achievable rates of stabilizer codes over ${\mathrm{\Phi }}_p$ and then the capacity is derived. A family of quantum codes $\mathcal{Q}=\{Q_n{\}}_{n=1}^{\mathrm{\infty }}$ is called capacity achieving if for sufficiently large $n$, we can find a code $Q_n\in \mathcal{Q}$ with rate arbitrarily close to the capacity. Theorem 12 shows that the family of stabilizer codes is capacity achieving over ${\mathrm{\Phi }}_p$, thus ${\mathrm{C}}_{{\mathrm{\Phi }}_p}=1-2p$.

Theorem 12. ([36]) Let $\mathcal{Q}$ be a family of stabilizer codes of rates $\mathfrak{R}$ and achieving vanishing decoding error probability over ${\mathrm{\Phi }}_p$. Furthermore, suppose that every code $Q\in \mathcal{Q}$ has a set of generators of its stabilizer whose weights are upper bounded by $m$. Then

$\mathfrak{R}\le (1-2p){\displaystyle \frac{1-(1-p{)}^{m-1}}{1-(1-2p)(1-p{)}^{m-1}}}.$

Compared to Pauli errors, erasures or errors with known locations are a more desirable error type for quantum error-correcting codes. Therefore, transforming physical noise into erasures can considerably improve the performance of quantum error correction [38].

8 Tomography

The main task of tomography is to reconstruct a full classical description of an $n$-qubit state from experimental data. In the process of developing methods of tomography, the following question entitled shadow tomography problem is raised. Given an $n$-qubit state $\rho$ and two-outcome measurements ${\mathcal{M}}_1,{\mathcal{M}}_2,...,{\mathcal{M}}_m$, estimate $\text{tr}[{\mathcal{M}}_i\rho ]$ up to error $ϵ$, for $i=1,2,...,m$. This problem is solved by designing a quantum procedure with $\tilde{O}({ϵ}^{-4}\cdot {\text{log}}^{4}m\cdot \text{log}n)$ copies of state, where $\tilde{O}$ hides factors which are polynomial in $\text{log log}m,\text{log log}n$ and $\text{log}{ϵ}^{-1}$ [39].

After this brief introductory note, let us describe the framework of classical shadows. Let $\rho$ be an unknown $n$-qubit state. First we apply a set of unitary evolutions $\rho \mapsto u\rho u^{†}$, where $u$ is randomly selected from an ensemble $\mathfrak{U}$ and then we measure the rotated state in the computational basis $\{|b⟩:b\in \{0,1{\}}^n\}$. Here, different ensembles lead to different versions of procedure and in practical scheme, each ensemble unitary should be realizable as an efficient quantum circuit. We suppose that this collection is tomographically complete, i.e., for each $\tau \ne \rho$ there are $u\in \mathfrak{U}$ and $b$ such that $⟨b|u\tau u^{†}|b⟩\ne$$⟨b|u\rho u^{†}|b⟩$. The framework of classical shadow estimation is based on the following algorithm.

Algorithm 3. (Constructing classical shadow)

1) Prepare a copy of the unknown quantum state $\rho$.

2) Sample $u\sim \mathfrak{U}$ randomly.

3) Transform $u\mapsto u\rho u^{†}$.

4) Perform a measurement in the computational basis.

5) Apply the inverse of $u$ to the resulting state from 4 for collapsing $\rho$ to $u^{†}|\hat{b}⟩⟨\hat{b}|u$, where $\mathbb{P}(\hat{b}=b)=⟨b|u\rho u^{†}|b⟩$.

6) Let ${\mathcal{M}}_{\mathfrak{U}}(\rho ):=\mathbb{E}(u^{†}|\hat{b}⟩⟨\hat{b}|u)={\mathbb{E}}_{u\sim \mathfrak{U}}\sum _{b\in \{0,1{\}}^n}⟨b|u\rho u^{†}|b⟩u^{†}|b⟩⟨b|u$.

7) Construct a classical snapshot by computing $\hat{\rho }={\mathcal{M}}_{\mathfrak{U}}^{-1}(u^{†}|\hat{b}⟩⟨\hat{b}|u).$

State $\hat{\rho }$ is called classical shadow, which has a unit trace, but need not be positive semi-definite. We note that tomographically completeness ensures that ${\mathcal{M}}_{\mathfrak{U}}^{-1}$ exists.

Classical shadow is a useful tool in numerical experiments based on random Clifford measurements [40]. We know that a stabilizer circuit can be simulated efficiently in $O(n^2)$ time by applying the algorithm based on tableau representation. This algorithm enables us to simulate systems efficiently with even more than 160 qubits in practice. To test the performance of predicting with classical shadows, we need to implement repeatedly the following efficient protocol.

1) Sample a Clifford unitary $u$ from ${\mathcal{C}}_n$ by applying the algorithm proposed in Ref. [41].

2) The action of $u$ on $X$- and $Z$-type operators is fully characterized by parameters

$(\alpha ,\beta ,\gamma ,\delta ,r,t)$ as follows:

$\begin{array}{rl}& u{X}_j{u}^{†}=(-1{)}^{r_j}\prod _{i=1}^n{X}_i^{{\alpha }_{ji}}{Z}_i^{{\beta }_{ji}},\\ & u{Z}_j{u}^{†}=(-1{)}^{t_j}\prod _{i=1}^n{X}_i^{{\gamma }_{ji}}{Z}_i^{{\delta }_{ji}},\end{array}$

where $j=1,2,...,n$ and $r_j,t_j,{\alpha }_{ji},{\beta }_{ji},{\gamma }_{ji}$ and ${\delta }_{ji}\in \{0,1\}$.

3) A parameterized unitary $u$ by $(\alpha ,\beta ,\gamma ,\delta ,r,t)$ can be applied on stabilizer states by changing the stabilizer generators and the destabilizer generators.

4) A computational basis measurement can be simulated by the improved algorithm based on tableau representation.

9 Discussion

In this section, we present some research lines as follows.

$\bullet$ The family of quantum low-density parity-check (qLDPC) codes is a subclass of CSS codes, which plays a central role in classical error correction [43]. Existence of qLDPC codes whose minimal distance scales linearly with the number of qubits is one of the major open problems in quantum information [44]. Furthermore, to see a set of open problems on geometric and combinatorial aspects of qLDPC codes, refer to Ref. [45].

$\bullet$ The $XP$ stabilizer formalism is an extension of the stabilizer formalism which includes fractional $\frac{2\pi }{n}$ rotations around the $Z$ axis, where $n$ is an integer. There is an equivalence between $XP$ stabilizer states and weighted hypergraph states. To see a set of open problems in the $XP$ stabilizer formalism, refer to Ref. [46].

10 Conclusion

The process of measuring a Pauli observable is discussed. It is shown that there exists a stabilizer witness consisting of a full set of generators, which is coarser than the GHZ witness. Moreover, with less than $n$ generators, it is not possible to detect genuine $n$-qubit entanglement. A stabilizer code is constructed from a given linear code. The evolution of a quantum system in the presence of noise is discussed by giving the error-correcting criteria. Moreover, the process of syndrome extraction for correctable errors is discussed. By applying logical bases, it is shown that any stabilizer code is unitarily equivalent to a trivial code. Given a graph code, its stabilizer generators are obtained. By applying the cleaning lemma, the distance of a stabilizer code embeddable in a lattice is given. By applying stabilizer matrices, the runtime of simulating stabilizer gates is obtained. The Knill−Gottesman theorem on classical simulation of stabilizer circuits is discussed. It is shown that given a full tableau, every Pauli product can be decomposed efficiently into a product of a stabilizer and a destabilizer. An algorithm for updating global phases by applying frame representation is given. Resolution of a quantum channel into a sum of stabilizer channels is shown. A family of capacity achieving stabilizer codes is applied to obtain the capacity of the quantum erasure channel. An algorithm for constructing classical shadow is given.

References

[1] D.Gottesman, Stabilizer codes and quantum error correction, arXiv: quant-ph/9705052, Caltech Ph.D thesis, 1997

[2] K.Fujii, Stabilizer formalism and its applications, in: Quantum Computation with Topological Codes, Springer Briefs in Mathematical Physics, Vol. 8, Singapore: Springer, 2015

[3] D.Gottesman, The Heisenberg representation of quantum computers, arXiv: quant-ph/9807006 (1998)

[4] F. R. F. Pereira , S. Mancini , G. G. La Guardia . Stabilizer codes for open quantum systems. Sci. Rep., 2023, 13(1): 10540

[5] A. Dymarsky , A. Shapere . Quantum stabilizer codes, lattices, and CFTs. J. High Energy Phys., 2021, 2021(3): 160

[6] D. Schlingemann , R. F. Werner . Quantum error-correcting codes associated with graphs. Phys. Rev. A, 2001, 65(1): 012308

[7] A. Dahlberg , S. Wehner . Transforming graph states using single-qubit operations. Philos. Trans. Royal Soc. A, 2018, 376(2123): 20170325

[8] D. Markham , B. C. Sanders . Graph states for quantum secret sharing. Phys. Rev. A, 2008, 78(4): 042309

[9] J. Ribeiro , G. Murta , S. Wehner . Fully device-independent conference key agreement. Phys. Rev. A, 2018, 97(2): 022307

[10] M.ChristandlS.Wehner, Quantum anonymous transmissions, in: Advances in Cryptology – ASIACRYPT (Ed. R. Bimal), pp 217–235, Berlin: Springer, 2005

[11] R. Jozsa , D. S. Abrams , J. P. Dowling , C. P. Williams . Quantum clock synchronization based on shared prior entanglement. Phys. Rev. Lett., 2000, 85(9): 2010

[12] V. Veitch , S. A. Hamed Mousavian , D. Gottesman , J. Emerson . The resource theory of stabilizer quantum computation. New J. Phys., 2014, 16(1): 013009

[13] C. H. Bennett , S. J. Wiesner . Communication via one- and two-particle operators on Einstein‒Podolsky‒Rosen states. Phys. Rev. Lett., 1992, 69(20): 2881

[14] D.M. GreenbergerM.A. HorneA.Zeilinger, Bell’s Theorem, Quantum Theory, and Conceptions of the Universe, Kluwer, 1989

[15] C. H. Bennett , G. Brassard , C. Crepeau , R. Jozsa , A. Peres , W. Wootters . Teleporting an unknown quantum state via dual classical and Einstein‒Podolsky‒Rosen channels. Phys. Rev. Lett., 1993, 70(13): 1895

[16] S. Aaronson , D. Gottesman . Improved simulation of stabilizer circuits. Phys. Rev. A, 2004, 70(5): 052328

[17] P. Selinger . Generators and relations for n-qubit Clifford operators. Log. Methods Comput. Sci., 2015, 11(2): 1

[18] M. Horodecki , P. Horodecki , R. Horodecki . Asymptotic manipulations of entanglement can exhibit genuine irreversibility. Phys. Rev. Lett., 2001, 86(25): 5844

[19] C. A. Sackett , D. Kielpinski , B. E. King , C. Langer , V. Meyer , C. J. Myatt , M. Rowe , Q. A. Turchette , W. M. Itano , D. J. Wineland , C. Monroe . Experimental entanglement of four particles. Nature, 2000, 404(6775): 256

[20] G. Tóth , O. Gühne . Entanglement detection in the stabilizer formalism. Phys. Rev. A, 2005, 72(2): 022340

[21] D. Dieks . Communication by EPR devices. Phys. Lett. A, 1982, 92(6): 271

[22] E.KnillR.LaflammeL.Viola, A theory of quantum error correcting codes, Phys. Rev. Lett. 84(11), 2525 (2000)

[23] J.Preskill, Lecture Notes for Physics 229: Quantum Information and Computation, Create Space Independent Publishing Platform, 2015

[24] M.HeinW.DürJ.EisertR.RaussendorfM.Van den NestH.J. Briegel, Entanglement in graph states and its applications, arXiv: quant-ph/0602096 (2006)

[25] D. Schlingemann . Stabilizer codes can be realized as graph codes. Quantum Inf. Comput., 2002, 2(4): 307

[26] T. J. Bell , L. A. Pettersson , S. Paesani . Optimizing graph codes for measurement-based loss tolerance. PRX Quantum, 2023, 4(2): 020328

[27] J. Haah , J. Preskill . Logical operator tradeoff for local quantum codes. Phys. Rev. A, 2012, 86(3): 032308

[28] S.BravyiB.Terhal, A no‒go theorem for a two-dimensional self-correcting quantum memory based on stabilizer codes, New J. Phys. 11(4), 043029 (2009)

[29] A. R. Arab . On states of quantum theory. Int. J. Geom. Methods Mod. Phys., 2022, 19(14): 2250221

[30] M.A. NielsenI.L. Chuang, Quantum Computation and Quantum Information, 10th Anniversary Edition, Cambridge University Press, 2010

[31] T.J. Yoder, A generalization of the stabilizer formalism for simulating arbitrary quantum circuits, www.scottaaronson.com/showcase2/report/ted-yoder.pdf (2012)

[32] H. J. García , I. L. Markov . Simulation of quantum circuits via stabilizer frames. IEEE Trans. Comput., 2015, 64(8): 2323

[33] A. R. Arab . On diagonal quantum channels. Rep. Math. Phys., 2021, 88(1): 59

[34] R. S. Bennink , E. M. Ferragut , T. S. Humble , J. A. Laska , J. J. Nutaro , M. G. Pleszkoch , R. C. Pooser . Unbiased simulation of near-Clifford quantum circuits. Phys. Rev. A, 2017, 95(6): 062337

[35] E. Wigner . On the quantum correction for thermodynamic equilibrium. Phys. Rev., 1932, 40(5): 749

[36] N.DelfosseG.Zémor, Upper bounds on the rate of low density stabilizer codes for the quantum erasure channel, Quantum Inf. Comput. 13(9‒10), 793 (2013)

[37] C. H. Bennett , D. P. DiVincenzo , J. A. Smolin . Capacities of quantum erasure channels. Phys. Rev. Lett., 1997, 78: 3217

[38] M. Kang , W. C. Campbell , K. R. Brown . Quantum error correction with metastable states of trapped ions using erasure conversion. PRX Quantum, 2023, 4(2): 020358

[39] S.Aaronson, Shadow tomography of quantum states, arXiv: 1711.01053 (2017)

[40] H. Y. Huang , R. Kueng , J. Preskill . Predicting many properties of a quantum system from very few measurements. Nat. Phys., 2020, 16(10): 1050

[41] R. Koenig , J. A. Smolin . How to efficiently select an arbitrary Clifford group element. J. Math. Phys., 2014, 55(12): 122202

[42] A.M. Steane, A Tutorial on Quantum Error Correction, Quantum Computers, Algorithms and Chaos, pp 1–32, Amsterdam: IOS Press, 2006

[43] R. G. Gallager . Low-density parity-check codes. IRE Trans. Inf. Theory, 1962, 8(1): 21

[44] L. Eldar , M. Ozols , K. Thompson . The need for structure in quantum LDPC codes. IEEE Trans. Inf. Theory, 2020, 66(3): 1460

[45] N. P. Breuckmann , J. N. Eberhardt . Quantum low-density parity-check codes. PRX Quantum, 2021, 2(4): 040101

[46] M. A. Webster , B. J. Brown , S. D. Bartlett . The XP stabiliser formalism: A generalisation of the Pauli stabiliser formalism with arbitrary phases. Quantum, 2022, 6: 815

[47] A. L. Grimsmo , S. Puri . Quantum error correction with the Gottesman‒Kitaev‒Preskill code. PRX Quantum, 2021, 2(2): 020101

Acknowledgements

This work was performed in the Laboratory of Combinatorial and Geometric Structures, School of Applied Mathematics and Informatics, MIPT. I would like to thank Prof. Andrei M. Raigorodskii, Dr. Andrey B. Kupavskii and my colleagues.

RIGHTS & PERMISSIONS

2024 Higher Education Press