Color Codes

A two-dimensional color code puts a qubit at each vertex of a suitable three-colored lattice and measures both an $X$ check and a $Z$ check on each face. The geometry makes logical operators deformable, while the matched check supports permit useful transversal Clifford gates. A seven-qubit triangular patch makes these ideas concrete: it is the Steane code drawn so that its faces, boundaries, and phase-gate pattern become visible.

We develop this small patch first, then explain which features extend to larger patches and closed surfaces. Throughout, checks have eigenvalue $+1$ in the code space. Claims about distance refer to ideal Pauli errors on data qubits; noisy measurement circuits require an additional analysis.

Required background. Stabilizer Formalism explains signed checks and logical Pauli operators. CSS Codes supplies binary check matrices and their row spaces.

Helpful background. Steane Code develops the same seven-qubit code from classical coding theory. Surface Code gives a comparison with another local two-dimensional family.

Face Checks on a Seven-Qubit Triangle

Each face in the diagram supplies two observables. For example, the face labeled $r$ supplies $X_1X_2X_3X_4$ and $Z_1Z_2Z_3Z_4$. The labels $r,g,b$ stand for red, green, and blue, but are combinatorial names: they distinguish faces, not physical Pauli axes. Grayscale shading makes the same distinction in the figure.

Every face supplies an $X$ check and a $Z$ check. The bold side supports $X_1X_2X_5$ or $Z_1Z_2Z_5$, a logical operator of weight three. Filled vertices receive $S$ and open vertices receive $S^\dagger$ in the phase-gate construction below. Face labels and vertex numbers fix the geometry without requiring color vision.

The three supports are

$$\begin{aligned} r&=\{1,2,3,4\},\\ g&=\{2,3,5,6\},\\ b&=\{3,4,6,7\}. \end{aligned}$$

Write $X_f=\prod_{j\in f}X_j$ and $Z_f=\prod_{j\in f}Z_j$. The six generators are $X_r,X_g,X_b,Z_r,Z_g,Z_b$. Opposite Pauli types anticommute once for each shared vertex, so

$$X_f Z_{f'}=(-1)^{|f\cap f'|}Z_{f'}X_f.$$

A face overlaps itself on four vertices; distinct faces overlap on two. Every sign is therefore positive. This even-overlap calculation is the reason the measurements are compatible.

Let $M$ be the face–vertex incidence matrix, with columns numbered from one to seven:

$$M=\begin{pmatrix} 1&1&1&1&0&0&0\\ 0&1&1&0&1&1&0\\ 0&0&1&1&0&1&1 \end{pmatrix}.$$

The binary relation $MM^{\mathsf T}=0$ expresses the same commutation property. Its three rows are independent, giving six independent stabilizer constraints and

$$k=7-2\operatorname{rank}M=1.$$

Thus the common eigenspace has dimension two. The seven physical qubits store one logical qubit, not seven copies of its unknown state.

Choose the logical representatives

$$\overline X=X_1X_2\cdots X_7, \qquad \overline Z=Z_1Z_2\cdots Z_7.$$

Both commute with every weight-four face check. They anticommute with each other because their common support has odd size. Multiplying either by a same-type face check removes that face from its support. For instance,

$$\overline X X_b=X_1X_2X_5.$$

On a code state, $X_b$ acts as the identity, so the short side and the all-seven product perform the same logical operation. The other two faces produce the sides $\{5,6,7\}$ and $\{1,4,7\}$. The corresponding $Z$ products behave identically.

This is exactly the Steane stabilizer after a coordinate permutation: color-code vertices $1,\ldots,7$ correspond respectively to Steane-page positions $4,6,7,5,2,3,1$. The normalized basis states can therefore be used after that relabeling. Bombín and Martín-Delgado’s color-code construction supplies the geometric interpretation and scalable families.

Syndromes, Logical Deformations, and Distance

Use the binary error label $E=X(x)Z(z)$, ignoring its scalar phase for syndrome calculations. List the $Z$-check bits first and the $X$-check bits second:

$$\begin{aligned} s(E)&=(s_Z,s_X),\\ s_Z&=Mx^{\mathsf T},\qquad s_X=Mz^{\mathsf T}. \end{aligned}$$

A bit is one when the corresponding outcome is $-1$. If $h_j$ denotes column $j$ of $M$, then $X_j$ produces $(h_j,000)$, $Z_j$ produces $(000,h_j)$, and $Y_j$ produces $(h_j,h_j)$.

Vertex $j$	Column $h_j$ in face order $r,g,b$
1	$100$
2	$110$
3	$111$
4	$101$
5	$010$
6	$011$
7	$001$

For example, $X_3$ flips all three $Z$-face outcomes, whereas $X_1$ flips only the $r$ outcome. These patterns reflect the central vertex and boundary corner in the drawing. The seven columns are distinct and nonzero, so all 21 single-qubit Pauli errors have distinct nonzero syndromes.

The same observation proves the lower bound on distance. A weight-one binary vector cannot be in $\ker M$ because no column vanishes. A weight-two vector cannot be in $\ker M$ because no two columns are equal. For a Pauli of total weight at most two to commute with all checks, both $x$ and $z$ would have to be such kernel vectors. Both must therefore vanish.

The boundary product $X_1X_2X_5$ is a nontrivial commuting Pauli of weight three, establishing

$$[[n,k,d]]=[[7,1,3]].$$

It is nontrivial because it anticommutes with $\overline Z$. The proof concerns the full Pauli distance, including mixed $X,Y,Z$ errors; it does not just count the length of a drawn side.

Same syndrome can mean different logical action

Consider $X_1$ and $X_2X_5$. Their syndromes agree because $h_2+h_5=h_1$ over $\mathbb F_2$. A decoder choosing the single-error correction $X_1$ succeeds on the first error but leaves $X_1X_2X_5=\overline X$ on the code after the second. No measurement of these checks can distinguish the two errors by itself.

By contrast, multiplying any error by a stabilizer leaves both its syndrome and its action on encoded information unchanged. Decoding should therefore choose a logical class, accounting for the probabilities of all errors in that class. Selecting one most likely microscopic error and selecting the most likely class are different optimization problems.

What the colored boundaries mean

In a larger color-code lattice, a colored string is defined on a corresponding shrunk lattice: faces of one color become vertices, and suitable connections join them. Such a string may end on the boundary of that color. The boundary label specifies an allowed endpoint, not a Pauli axis. Multiplying face checks moves strings through the lattice without changing their logical action.

Color codes also admit branching string nets, in which three colored pieces join. Their local intersections must still satisfy the stabilizer commutation conditions. The three sides of this small patch are equivalent logical representatives; they are not three separate logical qubits. More generally, boundary conditions decide which deformations are allowed and which extended operators are nontrivial. An arbitrary cut through a closed lattice need not retain commuting checks or the intended encoded dimension.

Larger Lattices and the Closed-Surface Count

The usual closed construction uses a connected trivalent lattice on an orientable surface, with faces properly three-colored. “Trivalent” means that three edges meet at each vertex. One face of each color meets there. Face boundaries have even length, and the standard cellulations have even overlap between every pair of face supports. Putting paired $X$ and $Z$ checks on those supports again gives a CSS code.

For a regular growing family, face sizes and the number of checks touching a qubit stay bounded. This is the sparse-check property of a quantum LDPC code. Bounded check weight is useful for measurement circuits, but says nothing by itself about the encoding rate or physical gate error rate.

Let $V,E,F$ count vertices, edges, and faces on a closed surface of genus $g$. Trivalence and Euler’s relation give

$$3V=2E,\qquad V-E+F=2-2g,$$

and hence $F=V/2+2-2g$. There is an important dependency among checks: the product of all red $X$ faces equals the product of all green $X$ faces and also the product of all blue $X$ faces. Each is the all-vertex $X$ operator, since every vertex belongs to exactly one face of each color. There are two independent relations per Pauli sector.

For the standard connected closed construction, these are the only dependencies, so each sector has rank $F-2$. Therefore

$$\begin{aligned} k&=V-2(F-2)\\ &=4g. \end{aligned}$$

A sphere encodes no logical qubit; a torus encodes four. This closed-surface formula cannot be applied to a triangular patch by setting $g=0$: removing checks and introducing colored boundaries changes the rank relations. The seven-qubit patch’s direct calculation already gave $k=1$.

On familiar planar triangular families, $n$ grows proportionally to area and $d$ grows proportionally to linear size, while $k=1$. Thus $n=O(d^2)$ and $k/n$ tends to zero. Precise qubit counts depend on the tiling and boundary construction. The smallest triangle alone does not establish an asymptotic scaling law.

Color-code and surface-code structures are closely related. Kubica, Yoshida, and Pastawski prove local Clifford equivalences; in two dimensions a closed color code unfolds into two toric-code copies. Bounded versions require their prescribed boundaries and gluing. These transformations preserve encoded information, but do not identify every physical noise model or measurement circuit. A local Clifford can turn an independent physical error into a correlated error on the transformed qubits.

Transversal Clifford Gates and Their Signs

The equal $X$- and $Z$-check supports make bitwise Hadamard particularly simple: $H^{\otimes7}$ exchanges $X_f$ with $Z_f$, and exchanges $\overline X$ with $\overline Z$. It implements logical Hadamard. A generic CSS code with unequal check spaces need not have this property.

Between two identically labeled blocks, coordinatewise CNOT also implements logical CNOT. Physical propagation sends a control $X_f$ to the product of that check on both blocks and sends a target $Z_f$ to the analogous product. The logical representatives transform in the same way. These operations are transversal: no elementary gate couples two qubits within one block. This restricts error spread, although preparation, check extraction, and recovery still need their own fault-tolerant circuits.

Alternating phase gates

For the figure’s filled and open vertices, set

$$A=\{1,3,5,7\},\qquad B=\{2,4,6\},$$

and apply $S=\operatorname{diag}(1,i)$ on $A$, with $S^\dagger$ on $B$:

$$U_P=\bigotimes_{j\in A}S_j \bigotimes_{j\in B}S_j^\dagger.$$

The two single-qubit conjugations are

$$SXS^\dagger=iXZ, \qquad S^\dagger XS=-iXZ.$$

Each face has two filled and two open vertices. The resulting phase is $i^2(-i)^2=1$, so

$$\begin{aligned} U_P X_f U_P^\dagger&=X_fZ_f,\\ U_P Z_f U_P^\dagger&=Z_f. \end{aligned}$$

The positive stabilizer group is preserved. On the all-seven logical $X$, however, there are four filled and three open vertices. Consequently,

$$\begin{aligned} U_P\overline X U_P^\dagger &=i\overline X\overline Z=\overline Y,\\ U_P\overline Z U_P^\dagger&=\overline Z. \end{aligned}$$

Thus $U_P$ implements logical $S$. The factor $i$ matters: $\overline Y=i\overline X\overline Z$ is Hermitian, whereas $\overline X\overline Z$ is not. Uniform $S^{\otimes7}$ preserves this particular code but implements logical $S^\dagger$, because $i^7=-i$.

For a general face of even weight $w$, uniform $S$ produces a sign $(-1)^{w/2}$. It preserves a positive face check in this way only when $w$ is divisible by four. A weight-six face gives a minus sign. On a bipartite patch where every face alternates between equal numbers of $A$ and $B$ vertices, the alternating operation cancels the phases for every face. The global logical phase must still be calculated for the chosen logical representatives.

Why Clifford gates are not a universal set

Hadamard, phase, CNOT, and Pauli gates generate the Clifford group. A non-Clifford resource is still required for universal computation, for example through state injection and protected gates.

For growing two-dimensional local stabilizer codes with sufficiently large distance, the Bravyi–König theorem restricts code-preserving constant-depth circuits of bounded geometric range to logical Clifford operations. “Constant depth” means bounded independently of code size; it does not mean any finite circuit on seven qubits. Higher-dimensional color codes and gauge fixing use different constructions and assumptions. They do not add a universal transversal gate set to the unchanged two-dimensional patch.

Decoding with Correlated Face Outcomes

At an interior vertex, one $X$ error can flip three $Z$-face checks. This differs from the two endpoints of a bulk surface-code error chain. Three clicks need not mean three independent faults. Our central vertex gives the smallest exact illustration: $X_3$ simultaneously produces $s_Z=111$.

Delfosse’s projection decoder relates color-code decoding to surface-code problems. The projected corrections must be combined and lifted to a valid correction on the original vertices. Their correlations and possible logical classes matter; independently choosing corrections in several projections does not automatically solve the original maximum-likelihood problem.

With perfect checks, this is a data-error decoding problem. With repeated faulty measurements, a decoder instead receives changes in reported check outcomes over time. A phenomenological model assigns noise directly to data and reports. A circuit model specifies faults in the gates, ancillas, measurements, and resets that generate those reports. An ancilla fault can spread through a multi-qubit face measurement and create a correlated data error. The syndrome-measurement discussion explains why the measurement schedule is part of this analysis.

Neither ideal transversal gates nor a finite code distance establishes a threshold or ranks hardware architectures. Larger face checks can increase extraction cost; favorable logical gates can reduce other costs. Comparisons must use the same task, noise assumptions, retained measurement rounds, and total qubit resources. Repeated active correction also differs from passive protection by a Hamiltonian: a commuting-check energy gap alone does not establish a self-correcting memory at nonzero temperature. See Topological Codes for that distinction, and Error-Correction Case Studies for experimental comparisons.

Exercises

1. Establish the small patch’s parameters

Use $M$ to prove $k=1$ and $d=3$, including errors with mixed Pauli types.

Solution

The first row is isolated by column one; after removing it, column two isolates the second, and the third is nonzero. Hence the rank is three. Even row weights and even pairwise overlaps give $MM^{\mathsf T}=0$, so $k=7-3-3=1$. Distinct nonzero columns exclude every nonzero kernel vector of weight one or two. A normalizing Pauli of total weight below three would require both binary components to be such vectors, so it is the identity up to phase. The commuting $X_1X_2X_5$ anticommutes with $\overline Z$, proving that it is a nontrivial weight-three logical operator. Therefore $d=3$.

2. Deform a logical operator and distinguish an error

Show that $X_1X_2X_5$ and $X_5X_6X_7$ implement the same logical action. Then compare errors $X_1$ and $X_2X_5$.

Solution

The first logical representative is $\overline X X_b$ and the second is $\overline X X_r$. Their product is $X_bX_r$, a stabilizer. The two errors have the same syndrome because $110+010=100$ over $\mathbb F_2$, but their product is the logical $X_1X_2X_5$. Thus the first comparison differs by a harmless stabilizer, while the second differs by a logical operation. Recovery $X_1$ corrects the single error and converts the double error into a logical bit flip.

3. Put a color code on a cube

Put qubits on the eight vertices of a cube and paired checks on its six faces. Give opposite faces the same color. Determine the encoded dimension, and compare it with a torus.

Solution

Every face has four vertices and adjacent faces share two; opposite faces share none. The six face rows have rank four: the products of each opposite pair all equal the all-eight support, giving two independent relations. Thus $k=8-2(4)=0$. The cube is a cellulation of a sphere, consistent with $k=4g=0$. For a standard closed toroidal color code the same general counting gives $k=4$. A planar triangular patch has boundary checks and must be counted separately.

4. Track phase signs on four and six vertices

Compute the action of uniform $S$ on an $X$ face of weight four and of weight six. Explain how an alternating bipartite pattern changes the result. Determine the logical phase direction for the seven-qubit patch.

Solution

Uniform $S$ gives $X_f\mapsto i^{|f|}X_fZ_f$. The sign is $+1$ for weight four and $-1$ for weight six. The latter sends the positive $X_f$ constraint to the opposite signed product and does not preserve that positive code space. With $m$ vertices in each part, the alternating phase is $i^m(-i)^m=1$. In the seven-qubit patch, four $S$ and three $S^\dagger$ gates give phase $i$ on $\overline X$, hence logical $S$. Seven uniform $S$ gates give $-i$, hence logical $S^\dagger$.

5. Three clicks from one physical error

Suppose the only noise is $X_3$ with probability $p=0.02$. Find each $Z$-face click probability and the probability of all three clicks. Compare with a model treating the three clicks as independent while keeping their marginal probabilities.

Solution

The only outcomes are $000$ with probability $0.98$ and $111$ with probability $0.02$. Each marginal click probability is $0.02$, and the joint probability is also $0.02$. The independent model instead gives $p^3=0.000008$, smaller by a factor of 2500. It also assigns positive probability to isolated clicks that are impossible in the stated model. A decoder must retain the common physical cause of the outcomes.

6. Read a logical bit destructively

Measure all seven data qubits in the $Z$ basis. Explain how one flipped classical measurement bit can be corrected before reporting the logical $Z$ outcome.

Solution

Without readout errors, the measured binary word $y$ satisfies $My^{\mathsf T}=0$ because all $Z$-face checks are positive. A bit flip at $j$ produces syndrome $h_j$, whose distinct nonzero column identifies the location. Correct that bit. The parity of the corrected seven-bit word gives the eigenvalue $(-1)^{\sum_j y_j}$ of $\overline Z$. This is a destructive measurement: the individual outcomes reveal a computational-basis word, so they do not preserve an arbitrary logical superposition. Two readout errors can imitate one and give the wrong logical parity, just as in the earlier error collision.

7. What local equivalence preserves

Let a Clifford circuit $U$ map one code space to another. Under the two-qubit CNOT conjugation $X_1\mapsto X_1X_2$, what happens to a stochastic $X_1$ error of probability $p$? Does preservation of encoded information imply preservation of an independent-error model?

Solution

The transformed channel is

$$\mathcal E'(\rho)=(1-p)\rho +pX_1X_2\rho X_1X_2.$$

The two transformed qubits flip together with probability $p$; each marginal flip probability is $p$. Independent flips with those marginals would instead have joint probability $p^2$ and would introduce single-flip events. A code equivalence transforms both the logical states and the noise channel. Comparing performance after the map requires the transformed noise, not a newly assumed independent model.

References

• H. Bombín, “Gauge color codes: optimal transversal gates and gauge fixing in topological stabilizer codes,” New Journal of Physics 17, 083002 (2015), doi:10.1088/1367-2630/17/8/083002, arXiv:1311.0879.
• H. Bombín and M. A. Martín-Delgado, “Topological quantum distillation,” Physical Review Letters 97, 180501 (2006), doi:10.1103/PhysRevLett.97.180501, arXiv:quant-ph/0605138.
• S. Bravyi and R. König, “Classification of topologically protected gates for local stabilizer codes,” Physical Review Letters 110, 170503 (2013), doi:10.1103/PhysRevLett.110.170503, arXiv:1206.1609.
• N. Delfosse, “Decoding color codes by projection onto surface codes,” Physical Review A 89, 012317 (2014), doi:10.1103/PhysRevA.89.012317, arXiv:1308.6207.
• A. Kubica, B. Yoshida, and F. Pastawski, “Unfolding the color code,” New Journal of Physics 17, 083026 (2015), doi:10.1088/1367-2630/17/8/083026, arXiv:1503.02065.