Shor Code

The Shor code protects one qubit using nine physical qubits arranged in three blocks of three. Checks within a block locate bit flips; checks between blocks locate phase flips. Together they correct an arbitrary error on any one physical qubit, including coherent noise and noise coupled to an environment. This is the $[[9,1,3]]$ code introduced by Shor (1995).

Its most instructive feature is degeneracy: a phase flip on any of the three qubits in the same block has exactly the same effect on the encoded state. Recovery can reverse that effect without learning which qubit flipped. The discussion below assumes ideal encoding, check measurements, and corrections; noisy operations require the additional methods of fault tolerance.

Required background. Three-Qubit Codes explains bit- and phase-repetition encoding. Stabilizer Formalism supplies commuting Pauli checks, their syndromes, and code projectors.

Three blocks of cat states

Use blocks $A=(1,2,3)$, $B=(4,5,6)$, and $C=(7,8,9)$, with qubit 1 on the left in tensor strings. Define the normalized states

$$\lvert G_\pm\rangle =\frac{\lvert000\rangle\pm\lvert111\rangle}{\sqrt2}.$$

The logical basis is

$$\begin{aligned} \lvert0_L\rangle&=\lvert G_+\rangle^{\otimes3},\\ \lvert1_L\rangle&=\lvert G_-\rangle^{\otimes3}. \end{aligned}$$

These states are orthogonal because $\langle G_+\vert G_-\rangle=0$. Encoding maps an unknown $\alpha\lvert0\rangle+\beta\lvert1\rangle$ to the superposition $\alpha\lvert0_L\rangle+\beta\lvert1_L\rangle$. It does not make nine copies of the input.

To see the construction, first encode into the phase-repetition states $\lvert+++\rangle$ and $\lvert---\rangle$. Encode each of these three qubits using $\lvert0\rangle\mapsto\lvert000\rangle$ and $\lvert1\rangle\mapsto\lvert111\rangle$. Thus $\lvert+\rangle$ becomes $\lvert G_+\rangle$ and $\lvert-\rangle$ becomes $\lvert G_-\rangle$. The outer encoding protects phase information; the inner encoding adds protection against bit flips.

Each component repetition code has full Pauli distance one: it protects against one type of error while leaving the other type unprotected. Consequently, multiplying two claimed distances of three is not a valid proof. We will prove the distance of the combined code directly.

Eight checks and two logical operators

Let $X_A=X_1X_2X_3$, with analogous definitions for $X_B$ and $X_C$. Choose the checks

$$\begin{aligned} g_1&=Z_1Z_2,&g_2&=Z_2Z_3,\\ g_3&=Z_4Z_5,&g_4&=Z_5Z_6,\\ g_5&=Z_7Z_8,&g_6&=Z_8Z_9,\\ g_7&=X_AX_B,&g_8&=X_BX_C. \end{aligned}$$

The first six check whether neighboring bits agree within each block. The last two compare the $XXX$ eigenvalues of neighboring blocks. Although a single $X$ anticommutes with a single $Z$, an outer check overlaps each inner check at zero or two sites, so all eight commute. They are independent and stabilize both logical basis states. Their common $+1$ eigenspace therefore has dimension $2^{9-8}=2$, with projector

$$P=\prod_{a=1}^{8}\frac{I+g_a}{2}.$$

This separate choice of all-$X$ and all-$Z$ generators makes the Shor code a CSS code. The stabilizer description follows the general construction in Gottesman (1997).

The six solid brackets indicate $ZZ$ checks. Each dashed bracket indicates an $X$ on every qubit of its two blocks. The checks compare relations within and between blocks; they do not measure the logical amplitudes $\alpha$ and $\beta$. Brackets show operator support, not a measurement circuit.

For the chosen logical basis,

$$\overline X=Z_1Z_4Z_7, \qquad \overline Z=X_1X_2X_3.$$

A physical $Z$ exchanges $G_+$ and $G_-$ in its block. One $Z$ in every block therefore exchanges the logical basis states, which explains the name $\overline X$. Conversely, $XXX$ has eigenvalues $+1$ and $-1$ on $G_+$ and $G_-$, so $X_A$ acts as logical $Z$. Physical Pauli letters do not determine logical Pauli names; their action on the chosen basis does. The two representatives anticommute and commute with all checks.

Decoding with two repetition rules

Write a syndrome bit as $s_a=0$ for a $+1$ check result and $s_a=1$ for a $-1$ result. Arrange the syndrome as the three inner pairs followed by the outer pair:

$$s=(s_1s_2,\ s_3s_4,\ s_5s_6;\ s_7s_8).$$

An $X$ or $Y$ error changes the inner pair in its block. A $Z$ or $Y$ error changes the outer pair. Both decoding steps use the same small table:

Pair	Inner correction within that block	Outer phase correction
$00$	None	None
$10$	$X$ on the first qubit	$Z_1$ in block $A$
$11$	$X$ on the second qubit	$Z_4$ in block $B$
$01$	$X$ on the third qubit	$Z_7$ in block $C$

For example, an $X$ at the second position anticommutes with both adjacent $ZZ$ checks, giving $11$. A phase flip in block $B$ anticommutes with both outer checks, also giving $11$. The same binary pattern describes two different comparisons, so keep track of which pair was measured.

Apply the inner corrections in each block, then the outer correction. Call the resulting Pauli $C_s$. This specifies a recovery for all 256 syndromes, including those caused by several errors. It guarantees success for arbitrary one-qubit noise; success for larger errors depends on their pattern.

A worked Y error

Suppose $Y_5$ occurs. Its syndrome is

$$s(Y_5)=(00,11,00;11).$$

The inner step applies $X_5$ and the outer step applies $Z_4$. Since $Y_5=iX_5Z_5$, their combined action leaves

$$C_sY_5=Z_4X_5Y_5=iZ_4Z_5=i g_3.$$

Every code state is a $+1$ eigenstate of $g_3$, so recovery restores the original state up to an irrelevant phase. It need not literally apply the same Pauli that caused the error.

The syndrome projectors and recovery channel are

$$\begin{aligned} \Pi_s&=\prod_{a=1}^{8}\frac{I+(-1)^{s_a}g_a}{2},\\ \mathcal R(\rho)&=\sum_s C_s\Pi_s\rho\Pi_s C_s^\dagger. \end{aligned}$$

Each $C_s$ has syndrome $s$ and takes its sector back to the code space. Because the projectors sum to $I$, this channel preserves trace on the whole nine-qubit space. The syndrome-measurement page explains the associated measurement instrument and why retaining or discarding the classical result matters.

Why indistinguishable errors can be corrected

Within block $A$, the stabilizers imply

$$Z_1P=Z_2P=Z_3P.$$

Thus these errors have both the same syndrome and the same action on every encoded state. Correction by $Z_1$ reverses any of them. The same reasoning applies to blocks $B$ and $C$. This is degeneracy, rather than a failure to measure enough information.

The identity and 27 single-qubit Paulis occupy

$$1+9+9+3=22$$

different syndrome sectors: one for the identity, nine each for $X_j$ and $Y_j$, and three for the blockwise $Z$ classes. Each sector has dimension two, so these errors occupy 44 of the 512 Hilbert-space dimensions. The code is not a perfect packing such as the five-qubit code.

More formally, order the error operators as $I$, the nine $X_j$, the nine $Y_j$, and the nine $Z_j$. The Knill–Laflamme condition is

$$PE_a^\dagger E_bP=C_{ab}P.$$

Here

$$C=I_{19}\oplus J_3\oplus J_3\oplus J_3,$$

where $J_3$ is the $3\times3$ all-ones matrix. Its off-diagonal entries express the equality of the three phase errors in each block. The matrix has rank 22; it need not be diagonal for correction to work.

This condition corrects the linear span of the listed operators. For instance, a rotation $e^{-i\theta Y_5/2}$ is a combination of $I$ and $Y_5$ and is corrected for every $\theta$, not merely to first order. An arbitrary one-qubit interaction with an environment likewise expands in $I,X,Y,Z$. The environment coefficients can be unknown and nonorthogonal. Logical-state independence of $C$ ensures that recovery preserves superpositions and entanglement with an untouched reference. See Why Quantum Error Correction Is Possible for the general argument.

The correctable span can also contain coherent sums of operators on different sites. This does not imply that every operator acting simultaneously on two qubits is correctable.

Distance three and errors that imitate one another

Distance concerns a Pauli that commutes with all checks but acts nontrivially on the logical qubit. Global Pauli phases are ignored in this statement; a scalar such as $-I$ is not a nontrivial logical operation.

Represent a Pauli, up to phase, by bit strings $(x,z)$, where $x_j$ records an $X$ component and $z_j$ a $Z$ component. Commutation with the inner $ZZ$ checks forces $x$ to be constant within each block. An operator of weight at most two must therefore have $x=0$.

Let $a,b,c$ be the parity of its $Z$ support in the three blocks. Commutation with the outer checks gives $a=b=c$. Weight at most two rules out three odd parities, so all are even. The only nonidentity possibilities are two $Z$ operators in a single block, and these are stabilizers. Thus no nontrivial logical Pauli has weight one or two. The displayed weight-three $\overline X$ and $\overline Z$ prove $d=3$.

Every error on one physical qubit is consequently correctable. Every Pauli of weight two satisfies the detection condition $PEP=c_EP$, but a stabilizer has $c_E=1$ and raises no alarm: it does no damage to the encoded state.

Other weight-two errors can imitate weight-one errors while acting differently on the code:

Actual error	Same syndrome as	Residual after the stated recovery
$Z_1Z_2$	$I$	$I_L$
$X_1X_2$	$X_3$	$\overline Z$
$Z_1Z_4$	$Z_7$	$\overline X$

For example, $X_1X_2$ causes the decoder to apply $X_3$, leaving $X_1X_2X_3=\overline Z$. This ambiguity is different from degeneracy: $Z_1$ and $Z_2$ act identically on the code, whereas $X_1X_2$ and $X_3$ differ by a logical operation. Returning to the code space alone does not establish successful recovery.

Independent depolarizing noise

For a concrete error-rate calculation, take independent noise on each qubit with

$$\mathcal D_p(\rho)=(1-p)\rho +\frac p3(X\rho X+Y\rho Y+Z\rho Z).$$

Here $p$ is the probability of a nonidentity Pauli; complete depolarization occurs at $p=3/4$. Use the recovery specified by the two repetition rules, including its action on syndromes from multiple errors. The resulting logical channel is a Pauli channel, but generally not a depolarizing channel: the code and decoder treat the two logical axes differently.

There are $\binom92 3^2=324$ weight-two Pauli strings. Their residual logical classes are

Residual class	Number	Contribution at order $p^2$
$I_L$	$180$	No logical error
$\overline X$	$108$	$12p^2$
$\overline Y$	$0$	Zero
$\overline Z$	$36$	$4p^2$

Thus the probability of a nonidentity logical Pauli is

$$p_L=16p^2+O(p^3).$$

The 36 logical-$Z$ failures have two bit-flip components in one block. The 108 logical-$X$ failures have phase-flip components in two different blocks. Exercise 7 derives these counts. In particular, an isotropic physical Pauli distribution can produce anisotropic logical noise.

An exact calculation at larger $p$ can enumerate the $4^9$ Pauli strings. If $N_{w,L}$ counts strings of weight $w$ with residual logical class $L$, then

$$p_L(p)=\sum_{w=0}^{9}\sum_{L\ne I_L} N_{w,L}\left(\frac p3\right)^w(1-p)^{9-w}.$$

This expression also explains two checks: $p_L(0)=0$, and $p_L(3/4)=3/4$ because uniform physical Paulis give equally many strings in each logical class. Neither the small-$p$ coefficient nor the exact finite-code result is a fault-tolerance threshold. Noisy check extraction, correlations, and repeated correction change the problem.

Exercises

1. Read the logical operators from the codewords

Prove that the codewords are orthonormal and stabilized by all eight checks. Explain why the physical $Z$ product represents logical $X$, and the physical $X$ product represents logical $Z$.

Solution

Each cat state is normalized and their overlap vanishes, so the tensor products are orthonormal. Adjacent $ZZ$ checks give $+1$ on both $000$ and $111$. Also $XXX\lvert G_\pm\rangle=\pm\lvert G_\pm\rangle$. Each outer check multiplies two equal block eigenvalues, giving $+1$ for either logical codeword.

The operator $Z_1Z_4Z_7$ exchanges all three cat signs, so it exchanges $0_L$ and $1_L$. The operator $X_1X_2X_3$ multiplies $0_L$ by $+1$ and $1_L$ by $-1$. These are exactly the actions defining logical $X$ and logical $Z$. Their overlap at qubit 1 contributes one anticommutation.

2. Reconstruct the concatenated checks

Starting from outer phase repetition and inner bit repetition, derive the two six-qubit checks. Why does this construction still require a separate distance argument?

Solution

The outer checks are $X_AX_B$ and $X_BX_C$. Inner bit repetition replaces the $X$ of each outer qubit by the product of three physical $X$ operators. This yields $g_7=X_1X_2X_3X_4X_5X_6$ and $g_8=X_4X_5X_6X_7X_8X_9$. The six inner checks are the two adjacent $ZZ$ pairs in each block.

Each repetition code separately has a weight-one logical Pauli on its unprotected axis and therefore full distance one. Its ability to correct a particular type of error is insufficient for multiplying full quantum-code distances. The direct commutation argument above establishes the combined code’s distance three.

3. Apply the syndrome rule

Find the syndromes and recovery residuals for $Z_2$, $X_8$, and $Y_5$. Use the specified two-stage decoder.

Solution

The syndromes are

$$\begin{aligned} s(Z_2)&=(00,00,00;10),\\ s(X_8)&=(00,00,11;00),\\ s(Y_5)&=(00,11,00;11). \end{aligned}$$

The corrections are $Z_1$, $X_8$, and $Z_4X_5$. They leave $Z_1Z_2=g_1$, $I$, and $iZ_4Z_5=i g_3$, respectively. Each acts as a scalar on the code. The phase in the third result has no effect on the recovered density operator.

4. Understand the degenerate error matrix

Derive the nonzero entries and eigenvalues of $C$ in the Knill–Laflamme condition. What does a zero eigenvalue mean here?

Solution

Each Pauli squared gives $I$, so each diagonal entry is one. Distinct errors with different syndromes give zero projected cross terms. The exceptions are $Z$ errors within one block: their products are stabilizers, giving off-diagonal entries one. Therefore $C=I_{19}\oplus J_3\oplus J_3\oplus J_3$.

Each $J_3$ has eigenvalues $3,0,0$. Thus $C$ has nineteen eigenvalues one, three eigenvalues three, and six zero eigenvalues. A null direction such as $Z_1-Z_2$ annihilates the code. It expresses redundant error descriptions, not a lost logical state.

5. Correct a finite coherent rotation

Apply $U=\cos(\theta/2)I-i\sin(\theta/2)Y_5$ to an encoded state, possibly entangled with a reference. Show that syndrome measurement and correction restore it for every angle.

Solution

Let $\lvert\Psi\rangle$ include the untouched reference. The two terms lie in the zero syndrome and the $Y_5$ syndrome, so their probabilities are $\cos^2(\theta/2)$ and $\sin^2(\theta/2)$, independent of the logical state. The zero branch requires no correction. In the second branch, $C_sY_5=i g_3$; hence the factor $-i$ in $U$ cancels the residual $i$ and the branch is proportional to $\lvert\Psi\rangle$.

After discarding the syndrome, the output is

$$\left[\cos^2\frac\theta2+\sin^2\frac\theta2\right] \lvert\Psi\rangle\langle\Psi\rvert =\lvert\Psi\rangle\langle\Psi\rvert.$$

Linearity extends the result to mixed reference-entangled inputs. No small-angle approximation has been used.

6. Separate harmless degeneracy from a logical mistake

Compare $Z_1Z_2$, $X_1X_2$, and $Z_1Z_4$. Does distance three imply that all weight-two errors cause logical failure?

Solution

$Z_1Z_2$ is a stabilizer and needs no correction. The two inner bit flips $X_1X_2$ produce pair $01$ in block $A$, causing correction $X_3$ and leaving $\overline Z$. The two phase flips $Z_1Z_4$ produce outer pair $01$, causing correction $Z_7$ and leaving $\overline X$.

Distance three guarantees correction of all weight-one errors and excludes lower-weight nontrivial logical operators. It does not require every larger error to fail. Some are stabilizers, and others happen to be reversed by the chosen decoder. Here 180 of the 324 weight-two Pauli strings have identity residual logical class.

7. Count the leading logical noise

Derive the 36 and 108 weight-two failures in the table. Explain why no logical $Y$ appears at this order. For an optional computational extension, enumerate all Pauli strings and check the uniform-noise limit.

Solution

A logical $Z$ needs two bit-flip components in one block. Choose the block, a pair of sites, and either $X$ or $Y$ at each site:

$$3\binom32 2^2=36.$$

A logical $X$ needs phase-flip components in two distinct blocks. Choose two blocks, a site in each, and either $Z$ or $Y$ at each site:

$$\binom32 3^2 2^2=108.$$

With only two affected qubits, the first event requires the same block and the second requires different blocks. They cannot occur together, so there is no logical $Y$ at weight two. Each particular weight-two Pauli has probability $(p/3)^2(1-p)^7$. Higher weights enter at order $p^3$, giving

$$\begin{aligned} p_L&=(36+108)\frac{p^2}{9}+O(p^3)\\ &=16p^2+O(p^3). \end{aligned}$$

For the extension, compute each string’s syndrome, apply the two correction rules, and classify the residual by its commutation with $\overline X$ and $\overline Z$. Each of the four logical classes contains 65,536 strings. At $p=3/4$ all $4^9$ strings are equally probable, so three quarters produce a nonidentity logical Pauli. This exact limit does not justify using the leading $16p^2$ approximation at large $p$.

References

• D. Gottesman, Stabilizer Codes and Quantum Error Correction, Ph.D. thesis, California Institute of Technology, 1997, doi:10.7907/rzr7-dt72, arXiv:quant-ph/9705052.
• E. Knill and R. Laflamme, “Theory of quantum error-correcting codes,” Physical Review A 55, 900–911, 1997, doi:10.1103/PhysRevA.55.900.
• P. W. Shor, “Scheme for reducing decoherence in quantum computer memory,” Physical Review A 52, R2493–R2496, 1995, doi:10.1103/PhysRevA.52.R2493.