Disjointness of Stabilizer Codes and Limitations on Fault-Tolerant Logical Gates

Stabilizer codes are among the most successful quantum error-correcting codes, yet they have important limitations on their ability to fault tolerantly compute. Here, we introduce a new quantity, the disjointness of the stabilizer code, which, roughly speaking, is the number of mostly nonoverlapping representations of any given nontrivial logical Pauli operator. The notion of disjointness proves useful in limiting transversal gates on any error-detecting stabilizer code to a finite level of the Clifford hierarchy. For code families, we can similarly restrict logical operators implemented by constant-depth circuits. For instance, we show that it is impossible, with a constant-depth but possibly geometrically nonlocal circuit, to implement a logical non-Clifford gate on the standard two-dimensional surface code.

Popular Summary

Quantum computers are vulnerable to many sources of noise, necessitating the use of error-correcting codes. Once data are encoded, we need to find fault-tolerant ways to operate on that encoded data without introducing uncorrectable errors. For example, one simple fault-tolerant operation, called a transversal operation, acts on each qubit in the code individually, allowing no opportunity for errors to spread from qubit to qubit. Here, we study quantum stabilizer codes—a popular approach to protecting data—and prove what operations cannot be transversal (or nearly transversal) on these codes.

The technical tool we introduce is a new quantity describing a quantum code called the disjointness. The disjointness (roughly) counts the number of ways one can access data in the code in parallel. The disjointness can be explicitly bounded for certain codes, giving limitations on transversal operations as well as more general operations that couple only a few qubits in the code. For instance, we show that for a popular code family—surface codes—such logical operations must be Clifford gates, which are easy to simulate classically.

Our results provide insights, in the form of necessary conditions, for designing codes with interesting transversal operations.

Figure 1

(a) The 2D surface code has $X$-vertex and $Z$-plaquette stabilizer generators and many nonoverlapping representatives of logical Pauli $\overline{X}$ (green) and $\overline{Z}$ (blue) operators. (b) For a given representative of $\overline{Z}$ (blue) and any constant-depth circuit $U$ with possibly geometrically nonlocal gates (depicted in yellow), one can always find a representative of $\overline{X}$ (green), such that $U\overline{Z}{U}^{†}$ and $\overline{X}$ overlap only on a constant number of qubits.

Figure 2

Two different partitions of the [[105,1]] qubit stabilizer code, which is a concatenation of the 7-qubit and 15-qubit codes. Each row of the $7\times 15$ array is an instance of the 15-qubit code that encodes one of the qubits of the 7-qubit code. Depending on the partition of the qubits, the code can have either a transversal logical (a) $T=\mathrm{diag}(1,\exp 2\pi i/8)$ or (b) Hadamard gate. Here, a transversal unitary with respect to a given partition is a tensor product of unitaries, each of which is supported only on qubits within one subset of the partition (red or green box).

Figure 3

Making a ${\mathrm{C}}^{4}X$ gate with controls $c_1$, $c_2$, $c_3$, $c_4$ and target $t$ from five Toffoli gates and two ancillas.