Rewiring stabilizer codes

A stabilizer code stores k logical qubits in n physical qubits by specifying that a physical state is an eigenstate of n − k given stabilizer operators (generators) with eigenvalue 1. The space of physical states is denoted the codespace. The stabilizer generators (g₀, g₁, ... g_n−k−1 $\in$ G) are typically taken to belong to the Pauli group—meaning that they are products of Pauli operators (I, X, Y, Z) acting on the physical qubits. They therefore all have eigenvalues ±1. The generators should be independent, and the space generated by their products is denoted S. For the codespace to be non-trivial, the stabilizers (and hence the generators) must commute with one-another. The generators for a stabilizer code are not unique: the same set S is generated if g_i g_j replaces g_i, for any j.

In addition to the stabilizers, one can define logical operators, which map the codespace onto itself. The space of logical operators is generated by $2k$ members of the Pauli group, which can be labeled ${\bar{X}}_{1},\,\cdots \,{\bar{X}}_{k},{\bar{Z}}_{1},\,\cdots \,{\bar{Z}}_{k}$, with ${\bar{X}}_{j}$ anticommuting with ${\bar{Z}}_{j}$, but commuting with all other logical generators. The labeling of the logical operators is not unique. Any member of the Pauli group that commutes with the stabilizers, but is not itself a stabilizer, is a logical operator.

Consider two stabilizer codes $S,{S}^{{\prime} }$ that differ by only one anticommuting generator: S is generated by $G=\{{g}_{0},{g}_{1},\,\cdots \,{g}_{n-k-1}\}$, while ${S}^{{\prime} }$ is generated by ${G}^{{\prime} }=\{{g}_{0}^{{\prime} },{g}_{1},{g}_{2},\,\cdots \,{g}_{n-k-1}\}$, with anticommutator $\{{g}_{0},{g}_{0}^{{\prime} }\}=0$. As is readily verified by its action on the generators, the unitary operator $U=(1+{g}_{0}^{{\prime} }{g}_{0})/\sqrt{2}$ maps the codespace of S to the codespace of ${S}^{{\prime} }$. One can further see that when acting on a state $| \psi \rangle$ in the codespace of S,

$$\begin{eqnarray}&&U| \psi \rangle =\sqrt{2}{P}_{1}| \psi \rangle =\sqrt{2}{g}_{0}{P}_{-1}| \psi \rangle ,\end{eqnarray} \tag{ 1 }$$

where ${P}_{\pm 1}=(1\pm {g}_{0}^{{\prime} })/2$ are projectors into the space spanned by the ±1 eigenstates of ${g}_{0}^{{\prime} }$. This relationship suggests an algorithm. Starting from a state $| \psi \rangle$, one measures ${g}_{0}^{{\prime} }$. If the result of the measurement is −1, one applies g₀ to the new state, otherwise one leaves it alone. Due to equation (1), this procedure is completely equivalent to the unitary transform, but is often simpler to implement.

One can chain these operations together—one-by-one changing the stabilizer generators. In the next section we show how to construct a sequence of measurements that map between any two given stabilizer codes. If the final code is the same as the initial code, then we thereby apply a gate (given by the product of the U's in equation (1)). This feature is used in a number of algorithms, such as topological [1, 2], and teleportation [12] based computing schemes.

The operator U in equation (1) maps the Pauli group onto itself, and is therefore described as a Clifford operator. Clifford operators are insufficient for universal quantum computation, and a quantum circuit only involving Clifford operators can be efficiently simulated on a classical computer [23]. Relaxing the constraint that the generators belong to the Pauli group opens up the ability to generate arbitrary gates.

Although the arguments have largely appeared elsewhere, in appendix A we give the proofs that U has all of these properties. Note, if one has a non-measurement way to apply U, such gates could also be used as part of the rewiring.

Given two stabilizer codes $S,{S}^{{\prime} }$, we wish to construct a sequence of stabilizer codes ${S}_{0},{S}_{1},\,\cdots ,\,{S}_{N}$, such that S₀ = S, ${S}_{N}={S}^{{\prime} }$, and S_j differs from S_j−1 by only one anticommuting generator. By the arguments in section 2.2 one then can map between S and ${S}^{{\prime} }$ by performing N measurements.

To facilitate constructing this sequence of stabilizer codes, we first make use of the fact that the generators are not unique, and find a set of generators of S and ${S}^{{\prime} }$ such that each of the generators fall into one of three blocks, denoted G_A, G_B, G_C and ${G}_{A}^{{\prime} },{G}_{B}^{{\prime} },{G}_{C}^{{\prime} }$. The first blocks are identical: ${G}_{A}={G}_{A}^{{\prime} }$. The second blocks, G_B and ${G}_{B}^{{\prime} }$ contain the same number of elements, and have the property that the generators in G_B commute with members of ${S}^{{\prime} }$, but are not in ${S}^{{\prime} }$. Conversely, those in ${G}_{B}^{{\prime} }$ commute with the members of S, but are not in S. Thus the elements of G_B are logical operators for the code defined by ${S}^{{\prime} }$, and vice versa. The elements in the third block are in one-to-one correspondence, and for each g_j $\in$ G_C, there exists a single element ${g}_{j}^{{\prime} }\in {G}_{C}^{{\prime} }$, such that g_j and ${g}_{j}^{{\prime} }$ anticommute. The element g_j however, commutes with all other elements of ${G}^{{\prime} }$ (and likewise for ${g}_{j}^{{\prime} }$). We claim that one can always find generators satisfying these conditions, and in section 2.4 we provide a constructive algorithm for finding these generators.

For each element g_j $\in$ G_B our construction also gives a complementary operator ${g}_{j}^{(c)}$ with the property that ${g}_{j}^{(c)}$ anticommutes with g_j, but commutes with all other elements of G. Furthermore ${g}_{j}^{(c)}$ commutes will all elements of ${G}^{{\prime} }$. Similarly, for each ${g}_{j}^{{\prime} }\in {G}_{B}^{{\prime} }$ we find a complementary operator ${g}_{j}^{{\prime} (c)}$ with analogous properties.

Given this construction, we can then generate the sequence of stabilizer codes ${S}_{0},{S}_{1},{S}_{2},\,\cdots \,{S}_{N}$. If the number of generators in blocks G_A, G_B, G_C are a, b, c, then we require N = 2b + c steps. It will require one step to replace an element of G_C with one of ${G}_{C}^{{\prime} }$, and two steps to replace an element of G_B with one of ${G}_{B}^{{\prime} }$. The required operation for replacing elements of G_C is simple: one just measures the elements of ${G}_{C}^{{\prime} }$. In order to replace g_j $\in$ G_B with ${g}_{j}^{{\prime} }\in {G}_{B}^{{\prime} }$, one first measures the product ${g}_{j}^{(c)}{g}_{j}^{{\prime} (c)}$, then measures ${g}_{j}^{{\prime} }$. Each of these steps is of the form detailed in section 2.2.

Note if G_B is empty, then the two codes S and S' are different gauge fixings of a single subsystem code. In that case, our algorithm reduces to a standard gauge fixing approach. See section 2.5.1.

In appendix C we give some simple examples to illustrate the mechanics of this procedure. Section 3 further explores the utility of these mappings.

In this section we explicitly construct generators of the form described in section 2.3. Given an arbitrary set of generators, G and $G^{\prime}$ of S and ${S}^{{\prime} }$, we first construct a connectivity matrix M, whose (i, j)'th element is 1 if the i'th member of G anticommutes with the j'th member of ${G}^{{\prime} }$. Otherwise that element is zero. For codes with n physical qubits and k logical qubits, M will be a $(n-k)\times (n-k)$ matrix. As already emphasized, the generators are not unique, and the same set of stabilizers are formed if one replaces any one generator by its product with another. Such a replacement in G corresponds to adding the jth row of M to the ith row mod(2). A similar replacement in ${G}^{{\prime} }$ corresponds to adding columns mod(2). By using the same techniques used for row reduction, one can thereby find a set of generators for which M is diagonal (with zeros and ones along the diagonal). The generators g_i and ${g}_{i}^{{\prime} }$ with M_ii = 1 correspond to block C, as defined in section 2.2.

Consider any ${g}_{j}\notin {G}_{C}$. Because of the structure of M, it commutes with all of the generators of the stabilizer group of ${S}^{{\prime} }$. Thus it is either a member of ${S}^{{\prime} }$ or logical operator of ${S}^{{\prime} }$. If it belongs to ${S}^{{\prime} }$, then it equals a product of the members of ${G}^{{\prime} }$—and one can always construct a set of generators for ${S}^{{\prime} }$ such that ${g}_{j}\in {G}^{{\prime} }$, giving us blocks G_A and ${G}_{A}^{{\prime} }$. This rearrangement of ${G}^{{\prime} }$ does not require replacing any of the elements of block C. Finally, all of the remaining generators are logical operators for the other code, and hence are in blocks G_B and ${G}_{B}^{{\prime} }$.

We further transform the generators, based upon the operators in blocks G_B and ${G}_{B}^{{\prime} }$. Each g_j $\in$ G_B is a logical operator for ${S}^{{\prime} }$, and hence there is a complementary logical operator ${g}_{j}^{(c)}$, that anticommutes with g_j. By construction, ${g}_{j}^{(c)}$ commutes with all elements of ${G}^{{\prime} }$ (and hence the elements of G_A). The complementary operators can always be chosen to commute with each other: if $\{{g}_{j}^{(c)},{g}_{k}^{(c)}\}=0$ for some g_k $\in$ G_B, one simply takes ${g}_{j}^{(c)}\to {g}_{j}^{(c)}{g}_{k}$. After this manipulation, one can further transform the generators so that ${g}_{j}^{(c)}$ commutes with all if ${g}_{k}\in {G}_{B}$ or G_C, for $k\ne j$: if ${g}_{k}\in {G}_{C}$ anticommutes with ${g}_{j}^{(c)}$, we take g_k → g_k g_j. This transformation does not change any of the other commutation relations. Note, as illustrated in section 3, one can map between codes with different numbers of qubits by simply appending auxiliary qubits to the shorter code with trivial local stabilizers.

In commonly-studied noise models, noise acts independently on physical qubits. Consequently, one measure of the robustness of the code is its distance—the lowest weight operator that performs a logical X- or Z-operation. Here weight is the number of qubits which are acted on by the operator. A code of distance d can correct errors of weight t or less, where $d=2t+1$.

Our basic algorithm can produce intermediate codes whose distance is smaller than that of S and ${S}^{{\prime} }$. Appendix D gives an explicit example. In sections 2.5.1 and 2.5.2 we quantify this issue by deriving lower bounds on the distances of the intervening codes generated by our algorithm when mapping between S and ${S}^{{\prime} }$. As recently shown by Huang et al [24], these lower bounds are worst case scenarios, and after adding appropriate ancilla qubits, there always exists a path in which the intermediate codes have distance no smaller than S or ${S}^{{\prime} }$. Moreover, Huang et al find the remarkable result that a random path yields high distance codes with high probability (and this probability can be made arbitrarily large by adding more ancillas).

2.5.1. Subsystem codes

2.5.2. Generic case

Intuitively, a measurement of the form of those in section 2.2, is fault-tolerant if errors that occur during the measurement do not degrade the error-protective properties of the code. For a code of distance 3 or higher (i.e. one in which at least a single qubit error can be corrected), this intuitive requirement can be satisfied by the property that no single error during the measurement can propagate to more than one qubit on the data [23]. The cat-state method, as introduced by Shor [30] and nicely discussed by Aliferis et al [31], provides one approach to meeting this requirement. The measurement is described in detail in appendix B.

In practical applications, the physical apparatus may introduce constraints on the operators measured. For example, one may only be able to carry out single qubit measurements, or measurements on sets of qubits that are connected by hard-coded wires. In the presence of such constraints, it is no longer possible to map between any two arbitrary stabilizer codes. The mapping may also be asymmetric: the constraints may be satisfied in mapping from A to B, but not in mapping from B to A. This latter setting is the domain of 'one-way' quantum computing [12].

One defines the constraints through the set W of all measurable operators. Given stabilizers codes S and ${S}^{{\prime} }$ generated by G and ${G}^{{\prime} }$, a necessary, but not sufficient, condition for the existence of a rewiring path is that ${G}^{{\prime} }$ is a subset of the group generated by $W\cup G$. For small systems, constrained paths can be found via an exhaustive search.

Note in many cases, measuring high-weight stabilizers is problematic. If one constrains the weights of the generators to be measured along the path from one code to another, such a path is not guaranteed to be generated by the algorithm.

The [[7, 1, 1]] Steane code is a 7-qubit code that supports transversal Clifford gates, and the 15-qubit [[15, 1, 3]] quantum Reed–Muller code supports several transversal non-Clifford gates which complement those of the Steane code. Thus [9–11] suggested sequentially mapping between these codes to produce a universal set of transversal gates. The generators for these codes are given in table 1, where we have appended extra bits to the Steane code.

Table 1.  Generators for Steane code (${g}_{0}-{g}_{5}$) and Reed–Muller codes (${g}_{0}^{{\prime} }-{g}_{13}^{{\prime} }$). Additional qubits with arbitrarily chosen stabilizer generators (${g}_{6}-{g}_{13}$) are appended to the Steane code for the conversion.

	Steane	Reed–Muller
j	gj	${g}_{j}^{{\prime} }$
0	${X}_{1}{X}_{3}{X}_{5}{X}_{7}$	${X}_{1}{X}_{3}{X}_{5}{X}_{7}{X}_{9}{X}_{11}{X}_{13}{X}_{15}$
1	${X}_{2}{X}_{3}{X}_{6}{X}_{7}$	${X}_{2}{X}_{3}{X}_{6}{X}_{7}{X}_{10}{X}_{11}{X}_{14}{X}_{15}$
2	${X}_{4}{X}_{5}{X}_{6}{X}_{7}$	${X}_{4}{X}_{5}{X}_{6}{X}_{7}{X}_{12}{X}_{13}{X}_{14}{X}_{15}$
3	${Z}_{1}{Z}_{3}{Z}_{5}{Z}_{7}$	${X}_{8}{X}_{9}{X}_{10}{X}_{11}{X}_{12}{X}_{13}{X}_{14}{X}_{15}$
4	${Z}_{2}{Z}_{3}{Z}_{6}{Z}_{7}$	${Z}_{1}{Z}_{3}{Z}_{5}{Z}_{7}{Z}_{9}{Z}_{11}{Z}_{13}{Z}_{15}$
5	${Z}_{4}{Z}_{5}{Z}_{6}{Z}_{7}$	${Z}_{2}{Z}_{3}{Z}_{6}{Z}_{7}{Z}_{10}{Z}_{11}{Z}_{14}{Z}_{15}$
6	Z8	${Z}_{4}{Z}_{5}{Z}_{6}{Z}_{7}{Z}_{12}{Z}_{13}{Z}_{14}{Z}_{15}$
7	Z9	${Z}_{8}{Z}_{9}{Z}_{10}{Z}_{11}{Z}_{12}{Z}_{13}{Z}_{14}{Z}_{15}$
8	Z10	${Z}_{1}{Z}_{3}{Z}_{9}{Z}_{11}$
9	Z11	${Z}_{2}{Z}_{3}{Z}_{10}{Z}_{11}$
10	Z12	${Z}_{3}{Z}_{7}{Z}_{11}{Z}_{15}$
11	Z13	${Z}_{1}{Z}_{3}{Z}_{5}{Z}_{7}$
12	Z14	${Z}_{2}{Z}_{3}{Z}_{6}{Z}_{7}$
13	Z15	${Z}_{4}{Z}_{5}{Z}_{6}{Z}_{7}$

Without any reference to the structure of the codes, our algorithm gives a mapping between them (see appendix E for details). For example, we find that 7 operators need to be measured to map from the Steane to the Reed–Muller code: ${g}_{0}^{{\prime} },{g}_{1}^{{\prime} },{g}_{2}^{{\prime} },{g}_{3}^{{\prime} },{g}_{8}^{{\prime} },{g}_{9}^{{\prime} },{g}_{10}^{{\prime} }$. Remarkably, these are all stabilizer generators of the Reed–Muller code, and hence no additional hardware is required, beyond what one already needs for implementing error correction. These operators can be measured in any order desired, or even simultaneously. Similarly one can map back to the Steane code by only measuring stabilizers: g₀, g₁, g₂, g₆, g₈, g₉, g₁₀. The resulting round-trip acts as the identity operator. The distance of the code never falls below 3 so, as discussed in section 2.6, the process is fault-tolerant.

Due to its importance, the literature contains several other approaches to map between the Steane and Reed–Muller codes. Hwang et al produced a circuit based on the particular structure of these codes and the fact that they can both be transformed into a common canonical form [10]. Anderson et al made the insightful observation that these two codes could be considered to be identical subsystem codes—with additional stabilizers added to fix the gauge [9]. They were able to use this structure to generate a map between the codes. Bombin also made similar observations [32]. Quan et al later extended this idea [11]. Our approach is in the same category as these gauge fixing methods, but has the added benefit that it automatically finds the minimal set of operators which need to be measured. It is purely algorithmic and does not require any insight.

As a related example, Huang and Newman used our algorithm to create a mapping between the 5-qubit code and the Steane code [24].

Topological codes are stabilizer codes where the spins are arranged on a lattice, the stabilizer generators are local (meaning they only involve spins which are near one-another), but the logical operators are non-local. These codes are particularly robust against local noise sources. They are also of great intellectual interest, as they have connections to gauge theories, spin liquids, and topological order. These codes are typically translationally invariant, but it can be advantageous to introduce 'extrinsic defects,' which locally disrupt the wiring. One can implement gates by deforming the code so that these defects move around one-another [33]. Here we apply our algorithm to the problem of moving these defects—reproducing known protocols for moving 'e' and 'm' type defects in surface codes, and finding new protocols for converting between these defects, and moving 'twist defects'. The latter is valuable beyond quantum information processing, as moving twist defects around one-another is equivalent to braiding Majorana fermions, which would allow the direct observation of excitations with non-Abelian statistics.

We will explicitly consider the toric/surface code. There are several conventions for defining this code. We follow [34], and place the qubits on the vertices of a checkerboard lattice with alternate plaquettes colored yellow and red (figure 1). For each yellow plaquette there is a stabilizer corresponding to the product of Z's on the four qubits at the vertices. For each red plaquette there is another stabilizer corresponding to the product of X's. The number of logical qubits stored by the code depends on the boundary conditions and the topology of the surface tiled by the qubits.

Zoom In Zoom Out Reset image size

The simplest defect involves 'removing' one of the stabilizers—meaning that one removes that generator from G, reducing the constraints on the codespace. In the presence of appropriate boundaries, this extrinsic defect yields one additional logical qubit. This defect is referred to as an Z or X defect (or equivalently e and m) depending if the removed stabilizer is a product of Z's or X's. Bombin [1, 2] uses the phrase 'code deformation' to describes the operations required to move these defects, and the algorithm is explained in detail by Fowler [33]. Our general code rewiring algorithm can be used to find these operations.

Consider for instance the setup in figure 1 where one wishes to move a Z defect (shown as a white square in the leftmost panel) to a diagonally adjacent site (rightmost panel). The two codes differ by only one generator: ${g}_{0}={Z}_{1}{Z}_{2}{Z}_{3}{Z}_{4}$, ${g}_{0}^{{\prime} }={Z}_{4}{Z}_{5}{Z}_{6}{Z}_{7}$, where Z₄ acts on the shared qubit. These are logical operators for the other code (i.e. lie in the B-blocks). The complementary logical operators involves a product of X operators extending from the each of the defects to the boundary. The product of these logical operators is simply X₄. Thus, following the prescription in section 2.2, one rewires the code by first measuring X₄ then measuring ${g}_{0}^{{\prime} }$. This protocol coincides with the one in [33].

As a second example, consider figure 2 where one wishes to convert a Z defect into an X defect on a neighboring plaquette. Again the codes differ in only one generator, and the generators are logical operators for the other code. The complementary operators this time are a string of X's and a string of Z's extending to a boundary. Their product is a string of Y's. Thus rewiring this code requires measuring a non-local quantity. In many topological quantum computer architectures this is impractical, as one wishes to avoid measuring non-local operators. In such a case, one could first move the defect near a boundary, where the string becomes short, at the cost of reducing the distance of the code.

Zoom In Zoom Out Reset image size

Finally we consider a 'twist' defect, illustrated in figure 3. Two of the square plaquettes are replaced by pentagons, and the plaquettes between them become rhombuses. As illustrated in the figure, the stabilizer associated with a pentagon involves measuring a product of three X operators, a Y and a Z or the product of three Z operators, a Y and a X. The stabilizer associated with a rhombus involves the product of two Z's and two X's. Twist defects are important for several reasons. For example, an X defect can be converted into a Z defect by moving it through the rhombus cells—a procedure that only requires local measurements. Given appropriate boundary conditions, adding a twist defect yields one additional logical qubit.

Zoom In Zoom Out Reset image size

We wish to consider how to deform the code in order to move one of the pentagons. For example, in figure 3 we illustrate a move in which the defect is made shorter. In this case, the code changes by two generators: on the left, ${g}_{0}={Z}_{1}{Z}_{2}{X}_{4}{X}_{5}$ and ${g}_{1}={X}_{2}{X}_{3}{Z}_{5}{Y}_{6}{X}_{7}$. On the right, ${g}_{0}^{{\prime} }={Z}_{1}{Z}_{2}{X}_{4}{Y}_{5}{Z}_{6}$ and ${g}_{1}^{{\prime} }={X}_{2}{X}_{3}{X}_{6}{X}_{7}$. Following the algorithm in section 2, we find a new set of generators $G=\{{g}_{0},{g}_{1}{g}_{0}\},{G}^{{\prime} }=\{{g}_{0}^{{\prime} },{g}_{1}^{{\prime} }{g}_{0}^{{\prime} }\}$, where ${g}_{0}{g}_{1}={g}_{0}^{{\prime} }{g}_{1}^{{\prime} }$, and g₀ anticommutes with ${g}_{0}^{{\prime} }$. Thus to convert between the codes one need only measure ${g}_{0}^{{\prime} }$.

These manipulations allow for operations which can be interpreted as braiding quasiparticles with unusual quantum statistics. As discussed by Kitaev [22], the codespace can be identified with the ground-space manifold of a Hamiltonian which is the sum of the stabilizer generators. Turning off one of the generators, say Z₀, enlarges the space. States that are eigenstates of Z₀ with eigenvalue −1 are identified with excited states of the Hamiltonian and are said to contain a quasiparticle at that location. Moving a Z defect around a X defect produces a control-not gate [33], which in this context can be interpreted as a phase that is contingent on the presence of the quasiparticles. Hence, there is a phase generated by moving one quasiparticle around another, which is the defining property of an anyon. The twist defects are even more interesting, as in this mapping the pentagons play the role of particles with non-Abelian statistics (described either as Ising anyons or Majorana fermions) [34].