Universal fault-tolerant quantum computing with stabilizer codes

The quantum logic gates used in the design of a quantum computer should be both universal, meaning arbitrary quantum computations can be performed, and fault-tolerant, meaning the gates keep errors from cascading out of control. A number of no-go theorems constrain the ways in which a set of fault-tolerant logic gates can be universal. These theorems are very restrictive, and conventional wisdom holds that a universal fault-tolerant logic gate set cannot be implemented natively, requiring us to use costly distillation procedures for quantum computation. Here, we present a general framework for universal fault-tolerant logic with stabilizer codes, together with a no-go theorem that reveals the very broad conditions constraining such gate sets. Our theorem applies to a wide range of stabilizer code families, including concatenated codes and conventional topological stabilizer codes such as the surface code. The broad applicability of our no-go theorem provides a new perspective on how the constraints on universal fault-tolerant gate sets can be overcome. In particular, we show how nonunitary implementations of logic gates provide a general approach to circumvent the no-go theorem, and we present a rich landscape of constructions for logic gate sets that are both universal and fault-tolerant. That is, rather than restricting what is possible, our no-go theorem provides a signpost to guide us to new, efficient architectures for fault-tolerant quantum computing.

Figure 1

Teleportation gadget for intrinsically fault-tolerant implementation of single-qubit logical operator $\overline{U}$. In the case where $\overline{U}=\overline{I}$ it implements error correction by teleportation. For general $\overline{U}$, this error correction ensures that $\overline{U}$ is implemented fault-tolerantly.

Figure 2

Simplified teleportation gadgets implementing $\overline{U}$ on CSS codes that are intrinsically fault-tolerant with respect to (a) $X$ errors and (b) $Z$ errors. [The first gate in (a) represents ${\overline{\text{cnot}}}_{2,1}$ conjugated by $\overline{U}$ on the control qubit.]

Figure 3

Magic state injection circuit obtained by letting $\overline{U}=\overline{T}$ in Fig. 2.

Figure 4

Coherent state injection circuit obtained by letting $\overline{U}=\overline{H}$ in Fig. 2.

Figure 5

Example of a logical operator implemented by braiding defects. The defect configuration is four holes, such that the closest holes are separated by a distance $l$. Braiding one hole around another grows the support of a string-like logical operator of length $l$ (blue) but it remains string-like and of length $\mathrm{\Theta }\left(l\right)$, so its spread under the braid is constant.

Figure 6

Illustrations of infinite disjointness of examples of conventional topological stabilizer codes. (a) Toric code: logical operator representatives correspond to topologically nontrivial loops around the torus. Specifically, ${\overline{X}}_1$ and ${\overline{Z}}_2$ are vertically oriented loops, ${\overline{X}}_2$ and ${\overline{Z}}_1$ are horizontally oriented loops and products such as ${\overline{Y}}_1$ and ${\overline{Y}}_2$ are diagonally oriented loops (which go around both holes). Disjoint representatives of each logical operator correspond to parallel loops around the torus (e.g., translating the red loop gives a disjoint, topologically equivalent grey loop). The disjointness of the code is thus lower-bounded by the circumference around the torus, which is grows with $l$. (b) Color code: logical operator representatives correspond to topological excitations that traverse to all three boundaries. Labelling the height of the triangle, $l$, we can construct $l$ representatives (of the kind shown in red and grey) such that each qubit is in the support of at most two of the representatives). The disjointness is thus bounded by $l/2,$ which goes to infinity (c) 3D surface code: $\overline{Y}$ logical operator representatives correspond to the paths of point-like charge between top and bottom faces and a line-like flux stretching from front to back passing from left face to right. We can construct $l$ representatives (of the kind shown) so that each qubit is only in the support of at most two of the representatives. Since the $\overline{X}$ and $\overline{Z}$ operators are simply planes and columns and so have $l$ disjoint representatives, this implies that the disjointness of the code is at least $\frac{l}{2}$.

Figure 7

Sequence of surface codes through which dimensional conversion deforms to transform between the standard three-dimensional ($l\times l\times l$) surface code (far left) and two-dimensional ($l\times l$) surface code (far right).

Figure 8

Representation of action on logical operators of removing a layer during dimensional conversion between 2D and 3D surface codes. A boundary is viewed as a 2D surface code (split) and then a locality-preserving logical circuit that is a product of nearest-neighbor cnot operators is applied between it and the face of the 3D code adjacent to it to disentangle it from the 3D code. The final result is that the original logical operators are mapped to the corresponding logical operators on the new code with the layer removed. (The removed layer is discarded, so its state is not important.) A layer can be added by the inverse process.