Constructing logical gates for low-density parity-check (LDPC) codes

We discuss Xanadu's state-of-the-art method for constructing logical gates fault-tolerantly to achieve universal quantum computation using general low-density parity-check (LDPC) codes.

By Benjamin Ide, Michael Vasmer, and Rafael Alexander

To build useful quantum computers, they must be designed to be resilient against errors. The possible rewards offered by fault-tolerant quantum computation have inspired a field of research known as quantum error correction (QEC), which strives to help alleviate noise and deal with the difficulty of reliably controlling fragile quantum systems. Within QEC, there has been ever-more-sophisticated theoretical progress in understanding how to suppress errors more quickly, with fewer resources, and to a greater degree.

In our recent work, we discuss the problems that must be overcome to implement fault-tolerant logical gates. A logical gate is the minimal algorithmic sub-unit of computation and a gate is fault-tolerant if it executes correctly even in the presence of errors. Fault-tolerant logical gates are therefore a prerequisite for achieving universal, useful quantum computation. We've created a framework that provides a systematic method for designing fault-tolerant gates, and using this framework, we've delivered a state-of-the-art technique with lower resource requirements than earlier approaches.

Quantum error correcting codes

How does quantum error correction work? We consider quantum information stored in some number of quantum bits (qubits), where each qubit is realized by a quantum mechanical system. Qubits are fragile, and left alone they will inevitably suffer from errors and corrupt the computation. Quantum error correction protects our qubits by encoding the information in a larger quantum system called a QEC code, within which repeated measurements of multi-qubit operators called stabilizers allows us to detect and correct errors.

What is the status quo? Run-of-the-mill quantum error correction often employs codes that belong to a family known as topological codes. A major downside to topological codes is that the encoding rate—the ratio of encoded logical qubits to physical qubits—approaches 0 as the level of protection is improved by increasing system size. Despite this, topological codes are popular because the physical qubits that constitute a stabilizer measurement are physically local, which is beneficial for many architectures with limited qubit connectivity. These shortcomings, as well as the relative ease of non-local qubit interactions in our architecture, have driven us towards a newer paradigm, requiring a deeper theoretical treatment: low-density parity-check (LDPC) codes.

Low-density parity-check (LDPC) codes

Here at Xanadu, our photonic architecture is very flexible and does not require locality, and as such, it is highly compatible with novel ideas from the study of LDPC codes. In particular, we have access to classes of QEC codes that maintain a good encoding rate as the system size is increased, thereby dramatically improving the overhead requirements and practicality of building a fault-tolerant quantum computer. Focusing our efforts on finding QEC codes that have a better rate is well worth it since a large portion of the resources in a useful quantum computer will be dedicated to QEC circuits.

One highly desirable feature of many QEC codes (including topological codes) is that each individual stabilizer measurement does not involve very many physical qubits, and further, that no physical qubit participates in very many stabilizer measurements. This is very beneficial because not only are quantum systems fragile in their own right, but the measurements themselves can also introduce noise! This noise gets worse if the measurements involve more qubits, so designing the quantum error correcting codes in such a way that limits qubit connectivity helps suppress errors. The defining feature of LDPC codes is precisely this: Stabilizers don’t involve many qubits, and no qubit participates in many stabilizer measurements.

Implementing logic gates while using LDPC codes

Quantum measurements also drive the process of implementing gates. Namely, we can implement logical gates via measurements of logical operators, which are multi-qubit measurements that commute with the stabilizer measurements that define the code, but are not themselves stabilizers. The immediate problem is that these measurements cannot be conducted directly while maintaining fault tolerance because there are too many qubits in the measurements, the very problem we were avoiding by using LDPC codes! An indirect approach is required.

There have been various previously proposed techniques that involve extending encoded states with additional (ancilla) qubits in such a way that necessary logical measurements can be conducted via fault-tolerant measurements, i.e., measuring operators that involve only a small number of qubits. However, since extra ancilla qubits are necessary, the reduction in resources gained by choosing LDPC codes with good encoding rates may again be lost by the choice of logical measurement technique. And indeed, before our work, all techniques were either specific to certain codes or required too many resources in general, which inspired our search for potential improvements.

Homological measurement framework

QEC codes that have the CSS property, meaning that each measured stabilizer is either a pure Pauli X operator or pure Pauli Z operator, can be described by two binary matrices whose rows describe the X and Z stabilizers, respectively. Interpreting these matrices as linear maps and placing them in a sequence called a chain complex gives us the natural setting in which to apply the mathematical concept of homology.

In mathematics, homology is studied to understand various algebraic, topological, and geometric objects. Here, we use it to study QEC codes. The logical content is given by one of the homology groups. Other properties given by the homology show the degree to which there are more stabilizer measurements than necessary.

Using this point of view to describe both the LDPC code and the ancilla system, we describe the merger of these systems as a homological algebraic construction. We call this framework Homological Measurement. This allows us to organize the mathematical objects elegantly and exploit results from homological algebra to understand the logical measurements to aid the search for the best technique.

This framework can describe the majority of previous logical measurement techniques. By examining the problem and the past solutions through this lens, it became apparent that improvements were available.

Edge expanded homological measurement

For each logical operator measurement we want to conduct, there is an associated graph that represents the structure of that logical operator within the LDPC code. This graph, in turn, defines a potential choice for the ancilla system. We use this ancilla system and a particular choice of chain map as a starting point.

The edge expansion of a graph is a particular measure of the graph’s connectivity. With high enough expansion, the measurement is guaranteed to be conducted fault-tolerantly. The key insight made available by looking at the problem through our framework is that we can simply add edges to the graph to increase the expansion, and it becomes straightforward to understand how these added edges affect the measurement.

Through this, we achieve a reduction in required ancilla qubits. Further, we have shown through simulations of Xanadu’s architecture for a fault-tolerant quantum computer that, even with the smaller system size this provides, errors are controlled just as well (and better in some cases!) than competing, higher resource requirement techniques. This work paves the way for delivering a large-scale fault-tolerant quantum computer potentially sooner than expected.

To find out more, read our recently published paper on Fault-tolerant logical measurements via homological measurement, authored by Benjamin Ide, Manoj G. Gowda, Priya J. Nadkarni, and Guillaume Dauphinais.