Universal Fault-Tolerant Quantum Computation with Only Transversal Gates and Error Correction

Transversal implementations of encoded unitary gates are highly desirable for fault-tolerant quantum computation. Though transversal gates alone cannot be computationally universal, they can be combined with specially distilled resource states in order to achieve universality. We show that “triorthogonal” stabilizer codes, introduced for state distillation by Bravyi and Haah [Phys. Rev. A 86, 052329 (2012)], admit transversal implementation of the controlled-controlled-$Z$ gate. We then construct a universal set of fault-tolerant gates without state distillation by using only transversal controlled-controlled-$Z$, transversal Hadamard, and fault-tolerant error correction. We also adapt the distillation procedure of Bravyi and Haah to Toffoli gates, improving on existing Toffoli distillation schemes.

Figure 1

The Toffoli gate is equivalent to a CCZ gate in which the target qubit is conjugated by Hadamard gates.

Figure 2

An implementation of the logical Hadamard operation in a triorthogonal code. Transversal Hadamard gates are applied to the data block. In order to restore the data to the codespace, and also correct any $X$ errors, an encoded $|+⟩$ state is prepared, coupled to the data with transversal CNOT gates and measured. $X$ corrections are applied as necessary.

Figure 3

A CCZ gate can be implemented by consuming a single Toffoli state [26]. The input qubits are teleported into the Toffoli state (enclosed by the dashed line) with Clifford corrections conditioned on the measurement outcomes.

Figure 4

A Toffoli state distillation circuit using a triorthogonal code encoding $k$ qubits. Three separate blocks are encoded into the state $|+{⟩}^{\otimes k}$ and then transversal CCZ gates are applied. Conditioned on detecting no errors, each block is decoded and Hadamard gates are applied to each of the target qubits, yielding $k$ Toffoli states.

Figure 5

The average number of physical $T$ gates required for three different Toffoli state distillation protocols. For the previous protocols of Refs. 9, 10, 14, input $T$ gates are first distilled to the appropriate fidelity according to Table I of Ref. 24. The solid black line shows the cost of our protocol for [[$3k+8$, $k$, 2]] triorthogonal codes where an even integer $2\le k\le 100$ has been optimally selected at each target error rate. Input CCZ gates to the triorthogonal protocol are produced using Ref. 10. Physical $T$ gates are assumed to have error at most ${10}^{-2}$. Detailed calculations are provided as Supplementary Material [27].