Low-overhead fault-tolerant quantum computing using long-range connectivity

Lawrence Z. Cohen; Isaac H. Kim; Stephen D. Bartlett; Benjamin J. Brown

Source-linked AI summary

Low-overhead fault-tolerant quantum computing using long-range connectivity

Lawrence Z. Cohen, Isaac H. Kim, Stephen D. Bartlett, Benjamin J. Brown

arXiv:2110.10794v2Oct 20, 2021quant-ph

TL;DR

Fault-tolerant quantum computing faces large physical-qubit overheads, motivating architectures that encode more logical information efficiently. The paper introduces long-range, LDPC-based logical Pauli measurements that preserve code protection and low overhead. It estimates order-of-magnitude savings over same-distance surface codes around one hundred logical qubits, potentially bringing such computations to a few thousand physical qubits.

Problem
Fault-tolerant quantum computing requires large numbers of physical qubits, while the practical cost of universal logical gates for quantum LDPC codes remains poorly understood.
Method
The paper generalizes lattice surgery through code deformation and multi-logical Pauli measurements for fault-tolerant gates on quantum LDPC codes.
Results
The scheme preserves code distance and supports the full Clifford gate set, with magic-state distillation and state injection extending it to universal quantum computing.
Takeaways & Limitations
Long-range connectivity with quantum LDPC codes can provide favorable overheads compared with surface-code schemes at practical device scales.

Abstract

from arXiv · show

Vast numbers of qubits will be needed for large-scale quantum computing due to the overheads associated with error correction. We present a scheme for low-overhead fault-tolerant quantum computation based on quantum low-density parity-check (LDPC) codes, where long-range interactions enable many logical qubits to be encoded with a modest number of physical qubits. In our approach, logic gates operate via logical Pauli measurements that preserve both the protection of the LDPC codes as well as the low overheads in terms of the required number of additional qubits. Compared with surface codes with the same code distance, we estimate order-of-magnitude improvements in the overheads for processing around one hundred logical qubits using this approach. Given the high thresholds demonstrated by LDPC codes, our estimates suggest that fault-tolerant quantum computation at this scale may be achievable with a few thousand physical qubits at comparable error rates to what is needed for current approaches.

I. INTRODUCTION

The paper targets the high qubit overhead of fault-tolerant quantum computing by combining long-range connectivity with quantum LDPC codes and fault-tolerant logical Pauli measurements. It estimates substantial overhead reductions relative to surface codes at near-term scales, while identifying implementation and compilation constraints.

Motivation: Fault-tolerant quantum computing may require millions of physical qubits for practical quantum chemistry, cryptanalysis, and polynomial-speedup applications.These estimates arise from the overhead of encoding and processing protected logical qubits with local-check error-correcting architectures.
Motivation: Long-range entangling operations have recently progressed across superconducting, semiconductor, trapped-ion, photonic, and networked quantum systems.This progress motivates architectures that relax strictly local two-dimensional connectivity.
Approach: The proposed architecture uses quantum LDPC codes to encode substantial logical information with fewer physical qubits than local approaches.The paper focuses on overhead savings at near-term device scales rather than asymptotic behavior.
Overhead estimates: A 50-logical-qubit computation may require only a few thousand physical qubits at code distance d = 14 ∼16, compared with at least ten-thousand qubits for a comparable surface-code architecture.This estimate assumes sufficiently reliable long-range coupling to operate below the scheme’s fault-tolerance threshold.
Approach: Fault-tolerant logic gates are implemented through logical Pauli measurements using a generalized lattice-surgery or code-deformation construction.The method supports Clifford operations and can be supplemented with magic-state distillation and state injection for universal computation.
Constraints: Higher stabilizer weights and measurement circuits can increase failure rates under circuit-level noise, despite constant small check weights limiting error spread.The paper notes that its estimates should account for the performance effects of these implementation details.
Constraints: The required parallelism and compilation cost remain algorithm-dependent, especially when Pauli strings exceed the available parallelism.The impact may be small for predominantly low-weight Pauli strings but is unclear for methods such as qubitization.

II. RESULTS

The paper introduces a code-deformation procedure that measures logical Pauli operators in quantum LDPC codes while preserving code distance and low-overhead structure. The construction supports Clifford operations through single-qubit and parity measurements, but its basic lemma is restricted when smaller-supported logical operators exist.

Main construction: The construction implements fault-tolerant logical gates in quantum LDPC codes through multi-logical Pauli measurements and code deformation.It extends techniques for reducing stabilizer weight to measure all logical Pauli operators and implement the full logical Clifford group.
Logical operations: Single-qubit Pauli and arbitrary-basis parity measurements support a measurement-based realization of the full Clifford gate set.Magic-state distillation and state injection can supplement these operations for universal quantum computing.
Protection: The construction preserves the code distance during deformation, retaining the code’s error-correcting capabilities.The merged code is later split back into the original code space after the logical measurement.
Code structure: LDPC codes use stabilizer generators with bounded weight and bounded qubit participation, represented by Tanner graphs linking physical qubits to stabilizer checks.The construction works with CSS codes and uses Tanner-graph substructures associated with the support of a logical operator.
Measurement procedure: A logical operator is measured by adding an extended system whose low-weight stabilizers multiply to the target operator, then inferring its outcome from stabilizer measurements.The merged Tanner graph combines the original graph with primal and dual graph layers connected by additional edges.
Scope and limitation: The basic construction requires that no distinct logical operator be supported on a strict subset of the target operator’s qubits.Otherwise, measuring a two-logical-qubit operator can unintentionally measure the individual logical operators instead.

2. Logical non-CSS measurement

The construction extends logical Pauli measurements to non-CSS operators, enabling measurements such as logical Y and X1Z2 through fused ancilla systems and mixed stabilizer generators.

Non-CSS logical measurements are required to implement the full logical Clifford group using logical Pauli measurements.
Logical Y is measured by combining ancilla systems for logical X and Z, then replacing overlapping generators with mixed generators.The product of X, Z, and mixed stabilizers yields the logical Y measurement result.
For logical X1X2, connected ancilla systems produce stabilizer products whose measurement outcomes give the joint logical result without separately measuring X1 or X2.The original stabilizers can then be measured again to return to the code space.
The construction applies whether the supports of X1 and Z2 intersect, with the fusion procedure adapted to the intersection structure.
The same construction measures logical X1Z2 by merging X and Z ancilla boundaries with mixed stabilizer generators.The product of the left X, right Z, and highlighted mixed generators gives the logical X1Z2 operator.

3. Simultaneous measurement of commuting logical operators

The construction supports simultaneous measurement of commuting logical operators by treating cases differently according to support overlap and Pauli type.

Disjoint commuting logical operators can be measured independently at the same time.
Commuting operators with overlapping supports can still be measured independently when both are entirely X-type or entirely Z-type.
For overlapping commuting operators of different Pauli types, generator products are modified and additional weight-two stabilizers fix the degrees of freedom introduced by merging.

C. Fault tolerance

The deformation preserves the LDPC structure while keeping stabilizer and qubit participation bounded by the original code parameters plus a constant.

The LDPC nature of the code remains intact throughout deformation from C to Cmerged.
w′, q′ ≤ max(w + 3, q + 3) after measuring a logical operator, where w and q bound stabilizer weight and qubit participation.
Bounded stabilizer complexity limits measurement complexity and the spread of errors during deformation.

1. Distance of Cmerged

The merged code preserves the original distance when the ancilla has sufficient layers, while introducing gauge degrees of freedom that do not reduce the distance of the logical operators of interest.

The distance analysis treats extra degrees of freedom as gauge qubits and checks that their operators do not lower the relevant logical distance.
Choosing r = d guarantees that code distance does not drop below d during deformation, whereas r = 1 can significantly reduce distance in the surface-code example.
A single ancilla layer can create a low-weight logical between boundaries, while d layers preserve the distance in the illustrated merge.The paper notes that some codes may require fewer than d layers.
The ancilla construction adds gauge qubits associated with cycles in the dual graph, with equivalent cycles across layers representing the same gauge qubit.
Any logical or gauge operator that anticommutes with a Z gauge operator has weight at least r.
The construction’s gauge operators can be organized as strings spanning the ancilla layers and terminating in the original code.
For an ancilla with at least 2d − 1 layers, Cmerged treated as a subsystem code has distance at least d.

D. Low-overhead fault-tolerant quantum computation

Fault-tolerant Pauli measurements enable logical Clifford gates, initialization, and logical-basis measurement while retaining the LDPC-based construction. The accompanying gauge-operator structure constrains X gauge operators to span all d ancilla layers.

Fault-tolerant logical Pauli measurements enable logical Clifford gates, initialization, and measurement in the logical Pauli basis.
The construction analyzes space and time overheads, with parallelism serving as a key quantity for determining them.
An X gauge operator must have weight at least d because it must intersect red gauge operators across all d dual ancilla layers.

1. Ancilla system size

The ancilla size for measuring a logical operator is controlled by its weight, the code connectivity parameter q, and the number of layers used. With r = d, the size is proportional to w_Ld.

For a logical operator of weight w_L, the ancilla graph contains at most qw_L/2 check nodes.
When r = d, the ancilla system is proportional to w_Ld.
For the considered cyclic-code constructions, a canonical logical-operator set can have w_L = d for every operator in the set.

2. Parallelism

Parallelism trades space overhead against time overhead: larger ancilla resources permit larger multi-logical measurements, while constant-rate constraints limit how many logical qubits can be measured together. Hypergraph product codes provide additional structure that can reduce ancilla costs for grouped measurements, but measuring all logical operators still requires O(n^3/2) ancillas.

2. Parallelism: The weight of logical parity measurements creates a trade-off between space and time overheads, and some codes improve these overheads over general LDPC codes.
2. Parallelism: Parity measurements can combine multiple logical operators by separately constructing and then connecting their ancilla systems.
2. Parallelism: Measuring all X logical operators in a code with Θ(n) logical qubits requires Ω(nd) ancillas, so constant-rate operation limits the number measured in one parity measurement.
2. Parallelism: Increasing space overhead with more ancilla systems can reduce time overhead by allowing very large multi-logical measurements.
2. Parallelism: Parallelism is chosen according to available space and time overhead rather than being inherent to the code.
2. Parallelism: Hypergraph product codes can arrange canonical logical operators along rows or columns, enabling one ancilla system to measure multiple logical qubits.
2. Parallelism: O(n) ancillas can measure logical operators of weight O(√n) in the structured hypergraph-product arrangement, versus O(n^3/2) for a naive scheme.
2. Parallelism: Measuring all logical operators on the hypergraph product code requires O(n^3/2) ancillas, reducing the scheme’s rate and distance to O(n^2/3) and O(n^1/3).

3. Magic states

Universal fault-tolerant computation requires magic-state distillation in addition to Pauli measurements. The scheme uses a separate magic-state factory and injects distilled states into the LDPC data block through ancilla systems.

3. Magic states: Universal fault-tolerant computation requires magic-state distillation in addition to fault-tolerant Pauli measurements.
3. Magic states: Non-Clifford gates such as T or CCZ gates can be implemented using injected magic states and Clifford gates.
3. Magic states: The architecture stores data on one LDPC code block, uses a separate surface-code magic-state factory, and injects distilled states through ancilla systems.
3. Magic states: For 10^10 T gates with 1% tolerance and noisy |T⟩ states of error 10^-3, the required distillation output error rate is 10^-12.

4. Decoders

The paper describes efficient decoding algorithms for quantum LDPC codes, including adaptations of classical bit-flip decoding to quantum settings.

Small-set flip adapts the classical bit-flip decoder to quantum LDPC codes.It was designed to address the specific structure of quantum codes.

III. DISCUSSION

The discussion identifies practical overhead bottlenecks and possible reductions, while emphasizing that connectivity constraints remain important for physically implementing LDPC-based fault tolerance.

LDPC codes can achieve fault-tolerant quantum computing with overheads favourable to surface-code schemes at reasonable scales.The scheme uses generalized lattice surgery together with magic-state distillation to implement universal quantum computing.
Magic-state distillation is one major overhead bottleneck and may require several factories to produce states at a sufficiently high rate.The discussion proposes adapting low-overhead surface-code distillation ideas to LDPC codes.
A hypergraph product code used for magic-state distillation can be nonlocal in only one dimension.This restriction may simplify implementation in some quantum systems.
Restricting nonlocality may limit attainable code distances, although such a trade-off may be necessary for physical implementation.The discussion connects code distance with connectivity and identifies limited nonlocality as an important design constraint.
The ancilla systems used for logical measurements are the other main overhead contribution.The construction requires ancilla systems with height at least d to maintain code distance, motivating proposals for constant-layer ancillas.

IV. MATERIALS AND METHODS

The construction measures logical operators using an ancilla system while preserving code distance, with equivalent logical operators propagated through successive ancilla layers.

Theorem 1 guarantees merged-code distance ≥d when the ancilla system has at least 2d −1 layers.The result applies when measuring a logical operator of a quantum CSS LDPC code and treating the merged construction as a subsystem code.
The proof assumes an X logical operator and reduces the general logical-parity case to the methods developed for this simple case.It also assumes the logical operator contains no X-type stabilizer as a subset on the first layer.
Z logical operators retain weight at least d because original X stabilizers remain unchanged outside the ancilla system.Ancilla stabilizers and gauge operators do not reduce the logical operator's weight below d.
The three curves in Fig. 8 represent equivalent X logical operators on the original code and successive dual ancilla layers.Independence of stabilizer subsets within a dual layer keeps the transformed operator supported on that layer.
Applying X stabilizers in successive dual ancilla layers moves logical-operator support through corresponding primal layers while preserving nontrivial support.The construction can clean support from one layer into the next until the top boundary is reached.
Successive cleaning steps replace support on one ancilla layer with equivalent support on the next while maintaining logical-operator weight.This layer-by-layer argument establishes the distance-preservation mechanism for the deformation.