Tangling Schedules Eases Hardware Connectivity Requirements for Quantum Error Correction

Error corrected quantum computers have the potential to change the way we solve computational problems. Quantum error correction involves repeated rounds of carefully scheduled gates to measure the stabilizers of a code. A set of scheduling rules is typically imposed on the order of gates to ensure that the circuit can be rearranged into an equivalent circuit that can be easily seen to measure the stabilizers. In this work, we ask what would happen if we break these rules and instead use circuit schedules that we describe as tangled. We find that tangling schedules generates long-range entanglement not accessible using nearest-neighbor two-qubit gates. Our tangled-schedule method provides a new tool for building quantum error-correction circuits and we explore applications to design new architectures for fault-tolerant quantum computers. Notably, we show that, for the widely used Pauli-based model of computation (achieved by lattice surgery), this access to longer-range entanglement can reduce the device connectivity requirements, without compromising on circuit depth.

Popular Summary

Error correction will be vital to enable large-scale quantum computations. Through it, multiple physical qubits are used to encode a single logical qubit, thereby introducing redundancy, which provides protection against errors. The surface code is a promising error-correction scheme, in part because of the limited requirements it places on the quantum hardware compared to other schemes. However, existing proposals to interact logical qubits still require the physical qubits to be connected to one another in a way that is difficult for solid-state quantum hardware. In this work, we present the “tangled schedules” method, which addresses this challenge and removes the need for infeasibly high connectivity, moving the field one step closer to useful quantum computing.

Quantum error correction typically works by repeatedly measuring a set of operators via a circuit specifically designed for that purpose. The order in which the two-qubit gates are applied in this circuit, called the scheduling, needs to satisfy a set of rules. We show how breaking one of these scheduling rules can generate entanglement not directly available on the hardware, which we can therefore use to measure long-range or high-weight operators. Our tangling schedules method operates by simply reordering some of the two-qubit gates and making some further simple changes to the circuit to measure a product of operators. Crucially, tangling schedules does not require a substantial increase in the circuit depth.

We present two applications of the tangling schedules method to perform logical computations with the surface code. Potential interesting future work would be to investigate how the tangling schedules technique could be exploited for other quantum error-correction schemes.

Figure 1

Hardware layouts with square-grid connectivity that accommodate (a) the rotated and (b) the unrotated planar codes, at least for the purpose of quantum memory.

Figure 2

Two auxiliary circuits for measuring the stabilizer $P_1{P}_2\cdots P_j$ using an auxiliary qubit prepared in the $|+⟩$ state. The circuits differ only in their schedules and, assuming that no other circuits are executed simultaneously, the two are equivalent. The measurements are in the $X$ basis.

Figure 3

Examples of schedules for pairs of stabilizers that satisfy condition (b). Panel (a) displays the scheduling that measures stabilizers $g_1=XXXXII$ and $g_2=IIZZZZ$ and panel (b) the scheduling that measures stabilizers $g_1=XXXXI$ and $g_2=IZXZX$. The coloring of qubits and plaquettes in this figure is used throughout the paper. Stabilizer $X$- and $Z$-Pauli terms are colored red and blue, respectively. A continuous colored area indicates a single stabilizer, with the black circles on the edge representing data qubits and the green circle within the shape the auxiliary qubit used for measurement of the stabilizer. Each number between a pair of data and auxiliary qubits indicates the layer in which the corresponding entangling gate between the two qubits is applied during syndrome extraction. In both examples, there are two joint qubits where the Pauli terms differ; specifically, for $g_1$, these are the $X$ and, for $g_2$, they are the $Z$. We therefore either need to apply the two cx gates for $g_1$ before we apply the cz gates for $g_2$, or the other way around. Otherwise, we would not measure the two desired stabilizers.

Figure 4

Examples of schedules that violate condition (b) and hence the combined circuits do not measure $g_1$ and $g_2$. However, we can exploit this to measure the higher-weight product, $h=g_1{g}_2$. Panel (a) displays the tangled scheduling that measures the stabilizer $h=g_1{g}_2=-XXYYZZ$ and panel (b) the tangled scheduling that measures the stabilizer $h=g_1{g}_2=-XYIYX$. For an explanation of the different parts of the diagrams, see Fig. 3; however, here, each continuous colored area indicates a single component operator.

Figure 5

Circuit identities used to analyze tangled schedules. (a) Interchanging rule for noncommuting entangling cx and cz gates. Similar rules hold for cx, cy and cy, cz gate pairs, provided they share the target qubit. (b) The circuit pruning identity for removing an entangled auxiliary qubit. In the text, we label the top qubit 1 and the next-to-top qubit 2. The blue boxes indicate Clifford corrections. Note that only the Pauli terms depend on the measurement outcome $m$, so that the (non-Pauli) Clifford term can be applied nonadaptively and the Pauli correction can also be handled nonadaptively by Pauli frame tracking. An application of this identity is Fig. 6.

Figure 6

Circuit for measuring $g_1{g}_2=-XXYYZZ$ with the outcome given by $m_1\oplus m_2$. Left: a circuit requiring low connectivity to measure the product $g_1{g}_2$ by violating the (b) condition. This uses the schedule in Fig. 4. Right: an equivalent circuit that shows direct entanglement of auxiliary qubits. In both cases, there is a Clifford correction to achieve the desired postmeasurement state. After two rounds of the protocol, the Clifford correction becomes a Pauli correction, as shown in Fig. 7.

Figure 7

Circuit for two rounds of measuring $g_1{g}_2=-XXYYZZ$ with the outcomes given by $m_1\oplus m_2$ and $n_1\oplus n_2$. The Clifford correction from the one-round circuit in Fig. 6 has become a Pauli correction $g_1^{1+m_1+n_1}$ that does not need to be physically implemented (removing the need for fast feedback) and can instead be accounted for by Pauli frame tracking.

Figure 8

Measuring an elongated $XXXX$ stabilizer (a) using our method that requires only a degree-4 connectivity device and (b) using the method of Ref. [16] that requires a degree-6 connectivity device. With our method, we initialize the two (accessory) qubits in the middle in the $Y$ basis (in purple), then measure the product $XXXXII\cdot IIZZXX=-XXYYXX$ of the two plaquettes by using schedules that do not satisfy condition (b). The classically flipped outcome of this measurement is then the outcome corresponding to the elongated rectangle. Here and in the rest of the paper, the green color on the plaquettes indicates a $Y$-Pauli term in the operator we measure.

Figure 9

Measuring a twist-defect $XXYXX$ stabilizer (a) using our method that requires only a degree-4 connectivity device and (b) using the method of Ref. [16] that requires a degree-6 connectivity device. With our method, we initialize one (accessory) qubit in the middle in the $Y$ basis (in purple), then measure the product $XXXXII\cdot IIZZXX=-XXYYXX$ of the two plaquettes by using schedules that do not satisfy condition (b). The classically flipped outcome of this measurement is then the outcome corresponding to the twist defect.

Figure 10

Default and tangled versions of two rotated planar code patches. The effective $X$ and $Z$ distances are (a),(b) 3 and 7 and (c),(d) 5 and 3, respectively. In (b) and (d), the green lines between auxiliary qubits indicate a tangled schedule between the two corresponding component plaquettes. Furthermore, the accessory qubits are shown in purple.

Figure 11

Comparing the default and tangled patches’ quantum memory performance. (a) The narrow case where the effective $X$ distance, $w$, is fixed to be 3 and the physical error rate is $p={10}^{-3}$. This means that the width is fixed to be 3 for default and 4 for tangled planar codes, while the height varies as shown on the horizontal axis. (b) The wide case when the effective $Z$ distance, $h$, is fixed to be 3, the effective $X$ distance, $w$, varies as shown on the horizontal axis, and the physical error rate is $p={10}^{-3}$. This means that the height is fixed to be 3 for both default and tangled planar codes, while the width is $w$ for the default and $2w-2$ for the tangled case. (c) The squarer-shaped case when the joint effective distance, $h=w$, varies as shown on the horizontal axis. This means that the default patch is of size $h\times h$, while the tangled patch is of size $(2h-2)\times h$.

Figure 12

Default and tangled rotated planar code patches without logical corners. We chose two default rotated planar patches for the stability experiment [(a) $2\times 2$, (c) $4\times 6$] and three tangled rotated planar patches [(b) $2\times 2$, (d) $4\times 6$, (e) $6\times 4$]. The $X$-type stabilizers are overdetermined and hence their measurement outcomes sum to 0 (mod 2).

Figure 13

Comparing the default and tangled stability experiments for the patches of Fig. 12. The time overhead $R={\gamma }^{\mathrm{tng}}/{\gamma }^{\mathrm{def}}$ is plotted against the physical error rate.

Figure 14

Default (a) and tangled (b) versions of a $5\times 5$ unrotated planar code. Their scheduling is also shown.

Figure 15

An example showing the merge-stage patch of a general lattice surgery operation involving several logical qubits as unrotated planar code patches. The original patches are outlined in black and labeled with their Pauli terms in the measurement. Here and in subsequent plots, the purple dots and lines label those outcomes that multiply to give the logical Pauli product we measure. Note that, at certain places, we could shrink the merge-stage patch (e.g., at the bottom left, we do not need the rectangle-shaped extension) if we do not wish to involve further patches in our logical measurement. However, we left these extensions here to show how other patches from adjacent tiles could be merged in easily too. Also, we could omit some of the merging through the boundaries of tile units, e.g., in the present case we could simply join at three boundaries instead of four. The $(d-1)\times (d-1)$ sized yellow square is an area we need to cross in order to have a logical failure string that connects the yellow square’s top and bottom vertices, thus connecting two boundaries of the merge-stage patch.

Figure 16

(a) The area including the yellow square from Fig. 15. The elongated stabilizers always spread the errors from their auxiliary qubits from the north-west to the south-east direction. For the regular $Z$ stabilizers we consider two cases. (b) If regular $Z$ stabilizers also spread errors from their auxiliary qubits in the north-west to the south-east direction (i.e., as the elongated ones), we can compose the shown graph where each edge corresponds to a single fault location during syndrome extraction, and, as a result, flips the outcome of the stabilizers that correspond to the vertices of that edge. Vertices $A$ and $B$ are boundary nodes. A logical error is a path in the graph that connects $A$ and $B$. This shows that the effective distance of the merge-stage patch in Fig. 15 is $d-1$. (c) If regular $Z$ stabilizers spread errors in the south-west to the north-east direction (i.e., perpendicular to the direction of spreading of the elongated stabilizers), e.g., as is the case in Fig. 14, then this graph can be composed. Again, it is straightforward to see that the effective distance is $d-1$.

Figure 17

(a) A QPU with its background lattice colored gray and white, and two aligned patches laid on top of this lattice. (b) Hence, $XX$ lattice surgery is possible without the need for any long-range stabilizers. The purple auxiliary qubits are those whose joint parity outcomes give the logical $XX$-measurement outcome. (c) However, $XZ$ lattice surgery needs some long-range stabilizers, as we need to change the checkerboard pattern to fit the pattern of those stabilizers that multiply into the logical $XZ$. The purple auxiliary qubits’ joint parity outcomes give the logical $XZ$-measurement outcome.

Figure 18

(a) The scheduling of the tangled patches in Fig. 10 extends naturally below the elongated rectangles. (b) Three types of detectors that we assign during syndrome extraction with elongated stabilizers and twist defects. Here $D1-D2$ compares the elongated outcomes from two consecutive rounds, where $D2$ needs to include accessory qubit outcomes, as those qubits were reset after they were measured. Detector $D3$ compares the $Y$-accessory qubit outcome to the two adjacent Pauli corrections.

Figure 19

A possible error $Y$ happening midcircuit: (left) the original location of the $Y$ error; (middle) propagating to an equivalent Pauli error; (right) the effect of the error on readout. Since the sum $m_1\oplus m_2$ is unchanged by the transformations $m_1\to m_1\oplus 1$ and $m_2\to m_2\oplus 1$, this detector goes untriggered. However, the Pauli correction after two rounds is inferred from $m_1\oplus n_1$ and will have the incorrect result. This leads to a Pauli error $g_1$. In the case of the surface code, this leads to two data qubit errors possibly aligned with a logical operator, a so-called bad hook error. Such a bad hook would also occur if we had directly entangled the auxiliary qubits and so is an intrinsic property of syndrome extraction with low-connectivity hardware. However, this can be compensated by the fact that the distance can be locally increased when we do lattice surgery using the same number of qubits (Sec. 6). Note also that the two detectors associated with the accessory qubits (prepared in state $|i⟩$) will be triggered after the second round.

Figure 20

Single midcircuit errors that together lead to a logical $X$ failure. The depicted patch’s schedule and qubits are not shown here, but are the same as in Fig. 10. Each subfigure (a)–(e) shows a different midcircuit error occurring after the execution of a cz gate, with the specific errors given by the purple-encircled Pauli strings. The purple asterisks show which detectors are triggered by the corresponding midcircuit error. More precisely, if they are placed in the middle of an elongated rectangle then they are like $D1$–$D2$ from Fig. 18; otherwise, they are associated with accessory qubits (like $D3$). An exhaustive search shows that fewer than five fault locations do not lead to a logical $X$ failure.

Figure 21

Four tile units in the bulk of the QPU, each surrounded by green dashed lines. The green dotted lines indicate areas where we can place elongated rectangles and twist defects. The purple dashed lines show areas where we may join the merge-stage patches of lattice surgery between tile units. We can continue tiling like this, meaning we shift the patches one row up for the next tile unit to the right.

Figure 22

Lattice surgery examples. (a) Measuring a logical $XXXX$. In general, to measure a logical Pauli product whose term on a patch is $X$, we place plaquettes everywhere except on the gray-white area around that patch in subfigure (a). (b) Measuring a logical $ZZZZ$. In general, to measure a logical Pauli product whose term on a patch is $Z$, we place plaquettes everywhere except on the gray-white area around that patch in subfigure (b). If the Pauli term is $Y$, we use all plaquettes around the patch, while if it is $I$, we avoid both gray-white areas. For an explanation of all aspects of the figure, see the caption of Fig. 15.

Figure 23

The tiling of our QPU in the bulk with rotated planar code patches.

Figure 24

Performing the same $XYZY$ measurement as in Ref. [17, Fig. 11], but on the degree-4 hardware shown in Fig. 1 using rotated planar patches. (a) The first, purely $X$-type, lattice surgery operation involving the three patches on which we intend to measure either $X$ or $Y$, and the auxiliary patch. Local stabilizers are sufficient here. (b) The second lattice surgery operation involving the three patches on which we intend to measure either $Y$ or $Z$, and the auxiliary patch. This is a mixed $ZZZX$-type lattice surgery, and hence we need elongated rectangles. Because of the distance-halving effect, we need to have a wider area to connect the auxiliary patch to the rest of the patches.

Figure 25

An alternative way to measure the $XYZY$ operator of Fig. 24 with twist-based lattice surgery with rotated planar patches. While twist-based lattice surgery is not always possible in this way without losing significant distance, in several cases it is possible.

Figure 26

Pruning a single leaf from a tree of tangled schedules. As a result of pruning, on the right, we see a Clifford correction on data qubits and additional one-qubit gates on auxiliary qubit 2 (gates in blue boxes).