Surface Code Compilation via Edge-Disjoint Paths

We provide an efficient algorithm to compile quantum circuits for fault-tolerant execution. We target surface codes, which form a two-dimensional grid of logical qubits with nearest-neighbor logical operations. Embedding an input circuit’s qubits in surface codes can result in long-range two-qubit operations across the grid. We show how to prepare many long-range Bell pairs on qubits connected by edge-disjoint paths of ancillae in constant depth that can be used to perform these long-range operations. This forms one core part of our edge-disjoint path compilation (EDPC) algorithm, by easily performing many parallel long-range Clifford operations in constant depth. It also allows us to establish a connection between surface code compilation and several well-studied edge-disjoint path problems. Similar techniques allow us to perform non-Clifford single-qubit rotations far from magic state distillation factories. In this case, we can easily find the maximum set of paths by a max-flow reduction, which forms the other major part of EDPC. EDPC has the best asymptotic worst-case performance guarantees on the circuit depth for compiling parallel operations when compared to related compilation methods based on swap gates and network coding. EDPC also shows a quadratic depth improvement over sequential Pauli-based compilation for parallel rotations requiring magic resources. We implement EDPC and find significantly improved performance for circuits built from parallel controlled-not (cnot) gates, and for circuits that implement the multicontrolled $X$ gate ${\mathrm{C}}^k\mathrm{NOT}$.

Popular Summary

Computers are built from imperfect hardware that experiences rare faults that can corrupt computations if unaddressed. For quantum computers, with hardware that must store fragile quantum superposition states, faults can be many orders of magnitude more common. Luckily, there are techniques to gain sufficient fault-tolerance to perform useful quantum computations. The surface code forms the basis for a promising strategy to protect the information on a quantum computer, but it imposes constraints on the operations that can be performed. We consider how to abide by these constraints and efficiently compile an abstract circuit description of an algorithm into elementary operations on an architecture built from the surface code. This compilation algorithm reduces the resources required to implement algorithms, thus leading to more efficient quantum computing. Using elementary surface code operations, we show a constant-depth procedure for preparing long-range Bell states at the ends of edge-disjoint paths of ancillas. Our proposed edge-disjoint compilation (EDPC) algorithm uses this procedure to perform long-range Clifford operations, such as CNOT gates, and we show that the depth of implementing CNOT operations is optimal for large parallel CNOT circuits. We assume non-Clifford single qubit rotations can be performed at the boundary of the architecture, e.g., by consuming magic states produced by distillation. EDPC then implements these rotations in the bulk by reducing to long-range CNOT operations with the boundary by a simple circuit identity. We implement EDPC and show significantly improved performance in compiling parallel CNOT circuits and multi-controlled X gates.

Figure 1

Logical qubits (light and dark gray patches) encoded in the surface code form a 2D grid. The elementary operations can be applied on any lattice translations of those shown. Their times in units of surface code logical time steps are as follows. $\mathit{0}$ logical time steps: single-qubit preparation in the $X$ basis (i) and the $Z$ basis (ii). Destructive single-qubit measurement, which moves the patch outside of the code space, in the $X$ basis (iii) and the $Z$ basis (iv) take $0$ steps. $\mathit{1}$ logical time step: two-qubit measurement of $XX$ (v) and $ZZ$ (vi). A move of a logical qubit from one patch to an unused patch (vii). Two-qubit preparation (viii) and destructive measurement (ix) in the Bell basis. $\mathit{3}$ logical time steps: a Hadamard gate, which uses three ancilla patches (x). See Appendix pp1 for further details.

Figure 2

Application of a cnot$(q_0,q_1)$ gate on qubits at distance $k+1$ using surface code operations in two ways. (a) Using a swap-based approach requires $\mathrm{\Omega }(n)$ depth using operations from Fig. 1, while (b) generating and consuming a Bell pair [12] can be implemented in constant depth. The classical function $f$ computes Pauli corrections on the output qubits.

Figure 3

A cnot gate can be implemented in depth $2$ using $ZZ$ and $XX$ joint measurements with a $|+⟩$ ancilla state, followed by classically controlled Pauli corrections. The swap gate can be implemented using four move operations and two ancillae in depth $2$.

Figure 4

A nonlocal cnot can be implemented using swap gates that take depth $2\lceil (k-1)/2\rceil$ using a zigzag of ancilla patches along the path $P$ of length $k$. The figure shows the case when $k$ is odd and the depth of the swap circuit is $2(k-1)$. The patches on the path can store other logical information, which will simply be moved during the swap gates. The patches adjacent to the path are ancillae that are used to implement the swap gates.

Figure 5

A long-range cnot can be implemented in depth $2$ by first preparing a Bell pair. (a) Joining Bell pairs with Bell measurements. This can be iterated to form a long-range Bell pair along any path of ancillae in depth $2$. (b) A Bell pair can be used to apply a cnot. (c),(d) The first and second steps of a depth-2 circuit that implements a cnot between a pair of patches at the end of a path of ancilla patches by preparing and consuming a Bell pair.

Figure 6

The EDP subroutine implements a set of parallel cnot gates connected by an operator EDP set. We assume a qubit ratio of 1 to 3 of data (black) to ancilla (gray and white). (a) The input to the EDP subroutine is a set of cnots and an associated EDP set. (b) We fragment the EDP set into two VDP sets consisting of segments of the original paths, and implement the compiled circuit over two depth-2 stages, one for each of these sets. (c) During the first stage we prepare a Bell pair between the ends of the segments in the first VDP set. (d) During the second stage we perform joint Bell measurements between the ends of segments in the second VDP set, producing long-range Bell pairs on ancillae adjacent to the control and target of each cnot. Then, long-range cnots can easily be applied by using the long-range Bell pairs (Sec. 2d). See Figs. 8 and 9 for further details of the long-range operations used here.

Figure 7

The graphs used in this paper. (a) The grid graph where each surface code patch corresponds to a vertex and is connected to its neighbors. (b) The operator graph for a set of terminal pairs $\mathcal{T}$ that correspond with a parallel cnot circuit. EDP sets for $\mathcal{T}$ on this graph are also operator EDP sets.

Figure 8

(a) For segments marked in white, we use long-range Bell pair preparation in depth $2$. (b) For segments marked in black, we then use long-range Bell pair measurement in depth $2$. (c) The Bell measurements in stage 2 stitch together the Bell pairs made in phase 1, resulting in a Bell pair in the qubits at the ends of the full path.

Figure 9

Detailed implementation of the steps in Fig. 6. For each segment that is scheduled in phase 1, we use (b) and (c); and for each subpath that is scheduled in phase 2, we use (d) and (e). In (d) variables $x_0$ and $z_0$ are equal to the total parity of all long-range Bell measurements applied during stage 1 on the cnot path. Each of these operations takes depth $2$. Panels (d) and (e) share variables $a$ and $b$.

Figure 10

We assume the capability of performing $S$ and $T$ gates at the boundary qubits (red) where it is easy for us to supply the requisite $S$ and $T$ magic states. We can then execute $S$ or $T$ gates in the $Z$ or $X$ basis for our circuit by using long-range cnot gates and the circuits in (b). For example, to execute $S$ or $T$ on qubits $G3$, $E7$, and $HTH$ on $G7$, we apply long-range cnot gates between pairs $(G3,G1)$, $(E7,A7)$, $(A5,G7)$, and then execute $S$ or $T$ on $G1$, $A7$, HTH on $A5$. We can continue applying other Clifford gates to qubits $G3$, $E7$, and $G7$ right after performing the long-range cnot gate, without waiting for the $Z$ correction, since we can propagate the correction through Clifford operations.

Figure 11

On a rotated $L_1\times L_2$ grid (here, $4\times 5$), we can implement an odd-even pattern of swap gates on data qubits (gray) using ancillae (white). Row-wise and columnwise swap gates used in swap routing on a grid [21] can be modified as shown above so that the ancillae used for swap gates do not overlap. Therefore, any arbitrary permutation on a rotated grid can be implemented in space-time $4(L_1+1)+2(L_2+1)$.

Figure 12

Space-time cost of a randomly sampled set of disjoint cnot gates with standard error of the mean (shaded region) compiled to the surface code using EDPC and swap compilation. We generate ten random circuits for each number of qubits ($n$) consisting of a set of disjoint cnot gates of varying density; the number of randomly selected qubits involved in a cnot gate is given by $n_{\mathrm{CNOT}}$. At all densities we see improved performance and scaling using EDPC.

Figure 13

We compare the space-time cost of compiling a $T$-gate optimized circuit decomposition for a half ${\mathrm{C}}^k\mathrm{NOT}$ gate to the surface code using EDPC and swap compilation. We see in the log-log plot (b) that dependence of the space-time cost on $n$ gives a higher scaling dependence in the case of swap compilation than EDPC. This results a lower space-time cost for EDPC starting from 64 qubits.

Figure 14

(a) A $d=5$ surface code patch implemented in a grid of data physical qubits (black disks), and ancilla physical qubits (white disks). Error correction is implemented with single-qubit operations and cnot gates between pairs of qubits connected by a dashed edge. The $Z$- and $X$-type stabilizers are associated with alternating red and blue faces. (b) A decoding graph that is defined by associating an edge with each qubit and a vertex for each stabilizer. If stabilizers are measured perfectly, $Z$ errors on data qubits (marked in red) can be corrected by finding a minimum weight matching (green edges) of vertices associated with unsatisfied $X$ stabilizers (yellow disks).

Figure 15

(a) A logical $Z_L\otimes Z_L$ measurement is performed by lattice surgery in the following steps. (i) Stop measuring the weight-two stabilizers along the horizontal boundary between the patches. (ii) Reliably measure the bulk faces for a single vertically extended patch. Note that $Z_L\otimes Z_L$ can be inferred from the product of the outcomes of the newly measured red faces. This temporarily merges the patches to form a single extended surface code patch. (iii) Reliably measure once more the weight-two faces along the horizontal boundary between the patches. This separates the pair of patches. (b) Two types of patches tile the plane, with $Z_L\otimes Z_L$ measurements possible between vertically neighboring patches, and $X_L\otimes X_L$ measurements possible between horizontally neighboring patches.

Figure 16

The move operation can be implemented in depth 1 by local and neighboring Pauli measurements. A horizontal move operation can be implemented by preparing a single-qubit patch in $|0⟩$, applying joint $XX$ measurement, and then measuring the original patch in the $Z$ basis (up to Pauli corrections). The vertical move operation follows from applying a Hadamard gate to the source qubit $|\varphi ⟩$ and a Hadamard gate on the output. Simplifying the circuit gives the right-hand side in the figure, with a $ZZ$ measurement that is available vertically.

Figure 17

Implementation of a Hadamard operation in depth 3 with three ancilla patches. (a) A transverse Hadamard operation is applied in depth 0 to each physical data qubit, which switches the arrangement of $X$ and $Z$ stabilizer generators compared to the standard configuration. (b) The patch is extended in depth 1 so that a segment of the standard boundary type is introduced on the right. (c) The patch is shrunk into a standard surface code patch of the form of the top-left corner of the region [see Fig. 15] in depth 1, but with its location shifted by a (code distance) $d$-independent amount. This allows us to shift the patch into the top-left corner in 0 depth (not shown). Then we move the logical qubit to the bottom-left corner in depth 1.

Figure 18

We can implement Bell preparation and measurement in terms of single- and two-qubit Pauli measurements in depth 1 as given in Fig. 18 [13]. (a) A Bell pair can be prepared from a (horizontal) joint $XX$ measurement of $|00⟩$ or a (vertical) joint $ZZ$ measurement of $|++⟩$, up to Pauli corrections. (b) A destructive Bell measurement can be implemented by a joint $XX$ measurement followed by individual $Z$ basis measurements, or by a joint $ZZ$ measurement followed by individual $X$ basis measurements.

Figure 19

Various implementations of a cnot gate with intermediate ancilla qubits and Bell operations. In particular, we are able to apply the control and the target either before (green) or after (teal) Bell preparation and measurement steps, while keeping the depth at 2.

Figure 20

(a) Any $k$-qubit gate diagonal in the computational basis can be remotely executed on $k$ dedicated ancillae by first using cnot gates. We use this technique to apply remote $Z(\theta )$ rotations [Fig. 10] with magic states at the boundary. (b) Similarly, gates diagonal in the Hadamard basis also have a remote implementation. Since the Pauli corrections can be commuted through Clifford circuits, Clifford circuits can be executed immediately after executing the cnot operations with no need to wait on the remote operations.

Figure 21

EDP subroutine: to apply cnots to the data qubits at the endpoints of a set of edge-disjoint paths $\mathcal{P}$, where the interior of each path is supported on ancilla qubits. The depth is at most 4.

Figure 22

Bounded $\mathcal{T}$-operator set algorithm: an approximation algorithm for minimizing the $\mathcal{T}$-operator set size that combines the theoretical guarantees from Theorem 3 with pragmatic performance using the greedy algorithm of Theorem 5.

Figure 23

Remote rotation subroutine: executes parallel single-qubit rotations that require magic states at the boundary by a Max Flow reduction. Using the EDP subroutine (Algorithm 21), we can perform remote rotations (Fig. 10) on each set of qubits connected to the boundary by $\mathcal{P}$ in depth 4.

Figure 24

EDPC: a surface code compilation algorithm for any circuit $\mathcal{C}=g_1\cdots g_{\ell }$. An operation $g_i$ is available if it has not been executed and all operations $g_j$ with overlapping support, for $j<i$, are executed.

Figure 25

swap compilation: we construct an algorithm based on the greedy depth mapper algorithm from Ref. [14]. Let us implicitly define $\mathtt{\text{route}}(\pi )$, for mapping $\pi$, which finds a swap circuit for implementing partial permutations [14]. We can compute the required partial permutation from the current mapping of qubits, and the given future mapping $\pi$.

Figure 26

EDPC implementation: the EDPC algorithm (Algorithm 24) differs from our implementation in that it greedily tries to execute cnot gates earlier.