Fault-tolerant quantum circuits with much lower overhead

Quantum computing is an emerging technology that promises to solve some problems exponentially faster than classical computers can. Quantum computation involves elementary operations known as quantum gates, which establish connections between quantum bits, or qubits, the quantum analogues of the bits in classical computers. 

Today’s qubits are still too noisy to faithfully execute the long quantum algorithms needed to solve practically important problems. Quantum error correction can compensate for noise, but it has high overhead. With existing quantum error correction schemes, a single logical qubit — the qubit that actually performs a quantum computation — might require thousands of additional physical qubits to handle the error correction.

In a paper we published in the Nature journal npj Quantum Information, we describe a new, low-overhead, fault-tolerant implementation of an important quantum gate called a T gate.

We show that our scheme reduces the overhead costs of implementing T gates by at least an order of magnitude, both in terms of the number of qubits and the number of required operations. Further, our scheme respects many of the hardware constraints characteristic of the most promising quantum computing architectures.

Any quantum algorithm can be decomposed into a series of gates drawn from a universal gate set. For instance, with only three elementary quantum gates — Hadamard (H), controlled-NOT (CNOT), and T gates — we can synthesize any quantum operation and thus execute any quantum algorithm. 

Quantum gates can be divided into two groups: the Clifford group gates and the non-Clifford gates. Gates in the Clifford group can be efficiently simulated by a classical computer; non-Clifford gates cannot be. Of the three basic gates we described above, only the T gate is a non-Clifford gate. Expressed in terms of our basic gate set, all useful quantum algorithms require many T gates. 

As with qubits, there’s a distinction between a logical gate — which requires many additional qubits for error correction — and a physical gate — a direct, noisy implementation of a gate operation.

For many quantum computing architectures, the error correction for the logical T gate is responsible for most of the resource overhead. So reducing that overhead is an important outstanding problem in the field.

Magic states

In previous work, the most effective method for implementing logical T gates was to use magic-state distillation, an approach pioneered by Alexei Kitaev and Sergey Bravyi at Caltech. A magic state is a quantum state that can be used to produce non-Clifford gates (such as the T gate) using only Clifford operations; magic-state distillation corrects errors in a prepared magic state to produce a high-fidelity magic state.

At the logical level, Clifford operations are typically much easier to implement than non-Clifford operations, which is what makes magic states so special. Still, the Clifford operations themselves do require error correction, which adds overhead. And they may need to be repeated multiple times to achieve the desired high-fidelity magic states, which increases the overhead still further. We refer to schemes that implement the Clifford gates at the logical level as a top-down approach. 

In our work, instead of using magic-state distillation to prepare magic states with high fidelity, we propose a fault-tolerant method for directly preparing magic states. 

Redundant ancilla encoding

Quantum error correction requires performing measurements on some of the qubits that compose a logical circuit; the qubits that perform those measurements are known as ancilla qubits. Our scheme, which we call redundant ancilla encoding, uses the same ancilla qubits in different ways for different phases of a quantum operation. In one part of our scheme, we use a group of ancilla qubits to detect errors; but in another part, those ancilla qubits transform into flag qubits, which can detect events where small errors grow to large uncorrectable errors. 

Using fewer ancilla qubits allows us to implement a fault-tolerant protocol for preparing magic states with very few resources. It also allows all of our operations to be implemented between nearest-neighbor qubits, an important constraint in many quantum computing architectures. 

We further showed that, due to the fault tolerance of our circuits, magic states with the desired fidelities can be prepared using only physical-level Clifford operations, not the logical-level implementations required in prior work. Our scheme is thus a bottom-up approach, given that all operations can be implemented at the physical level. This is one of the main reasons we see improvement by at least an order of magnitude in our implementation of the T gate.

Although large-scale and fully fault-tolerant quantum computers are not within the range of current technologies, various quantum computing architectures are inching towards the demonstration of a prototype fault-tolerant quantum error correction scheme. By removing the need to use very high-fidelity encoded Clifford operations and allowing the use of lower-fidelity physical-level operations — while respecting hardware constraints — our bottom-up magic-state-preparation scheme makes fault-tolerant implementation of a non-Clifford gate more easily realizable in the near future.