Fault-Tolerant Quantum Computation with Constant Overhead

Daniel Gottesman

Source-linked AI summary

Fault-Tolerant Quantum Computation with Constant Overhead

Daniel Gottesman

arXiv:1310.2984v3Oct 10, 2013quant-ph

TL;DR

Large fault-tolerant quantum circuits face high qubit overhead because conventional protocols protect logical qubits separately and require substantial ancilla resources. This paper uses quantum LDPC codes and controlled ancilla handling to construct fault-tolerant protocols in a common model. It shows that, asymptotically, arbitrarily large reliable computations can use constant overhead equal to the underlying code family's inverse rate, under strong assumptions and with unresolved code-family and ancilla limitations.

Problem
Conventional fault-tolerant protocols have high qubit overhead because error correction is often treated separately for each logical qubit and uses many ancillas.
Method
The paper constructs fault-tolerant protocols using quantum LDPC code families, appropriately sized code blocks, and controlled ancilla-state flow.
Results
Arbitrarily long reliable quantum computations are possible below threshold with asymptotic overhead equal to the inverse rate 1/R of the underlying quantum error-correcting code family.
Takeaways & Limitations
Fault-tolerant quantum computation can in principle require few extra qubits, contrasting with conventional approaches, when the protocol's assumptions hold.
Takeaways & Limitations
The result depends on no geometric constraints, fast classical computation, and the asymptotic limit; known code families also lack either satisfactory decoding or sufficient error suppression.

Abstract

from arXiv · show

What is the minimum number of extra qubits needed to perform a large fault-tolerant quantum circuit? Working in a common model of fault-tolerance, I show that in the asymptotic limit of large circuits, the ratio of physical qubits to logical qubits can be a constant. The construction makes use of quantum low-density parity check codes, and the asymptotic overhead of the protocol is equal to that of the family of quantum error-correcting codes underlying the fault-tolerant protocol.

1 Introduction

Fault-tolerant quantum computation traditionally incurs substantial qubit overhead because error correction is often organized separately for each logical qubit and requires large ancilla resources. The paper argues that quantum LDPC codes can instead support arbitrarily large computations with constant asymptotic overhead tied to the code rate, while known code families remain imperfect.

Existing overhead: O(m polylog(mT)) physical qubits replace a logical circuit using m qubits and T gates in the standard threshold theorem.Practical constant factors can range from hundreds or thousands to billions.
Existing overhead: Separate error correction for each logical qubit, together with ancilla qubits for correction and gates, is identified as the main source of high overhead.Surface-code approaches can share blocks but still devote many physical qubits to protecting each logical qubit.
Approach: Large codes that encode and correct many logical qubits together offer a route to more efficient fault-tolerant error correction, but have received limited prior study.Earlier work established protocols for multi-qubit stabilizer-code blocks and showed substantial overhead reductions for moderate-size computations.
Main contribution: The paper shows that suitable quantum error-correcting code families can yield arbitrarily large computations with constant error rate and constant overhead asymptotically equal to 1/R.LDPC codes provide small ancillas, while block sizing and controlled ancilla flow keep overhead bounded; R can approach 1 for suitable families.
Open limitations: Known code families are not completely satisfactory because some lack efficient decoding and others provide insufficient error suppression for computation-independent thresholds.The theorem remains applicable to future code families satisfying its conditions or to known families with improved decoders.
Open limitations: The result is primarily asymptotic, so sub-leading additive overheads may be important for small computations.The author presents the construction as motivation for further work on reducing overhead in small systems.

2 Basic Model of Fault Tolerance

The paper analyzes fault tolerance in a basic circuit-location model using stabilizer and LDPC codes, fault-tolerant gadgets, stochastic noise, and several operational assumptions. Its efficiency claim relies especially on free classical computation and the absence of geometric constraints for required long-range interactions.

Code model: A quantum error-correcting code encodes k logical qubits into n physical qubits as a 2^k-dimensional subspace, while this paper studies blocks containing many logical qubits.The code framework is restricted to stabilizer codes.
Error correction: A stabilizer syndrome identifies Pauli errors through the generators' ±1 eigenvalues, and a distance-d code corrects floor((d−1)/2) errors.Errors are distinguishable by commutation or can be treated identically when they differ by a stabilizer.
Code model: LDPC codes are stabilizer codes whose generators have low weight and act nontrivially on each physical qubit only a bounded number of times.The formal definition uses generator weight bound r and qubit participation bound c.
Circuit model: Fault-tolerant gadgets implement circuit locations on encoded qubits, with transversal gates preventing interactions between two qubits in the same code block.The basic model represents computation as locations that may be faulty.
Noise and operations: The model assumes stochastic noise, no leakage from the computational subspace, and parallel operations on a constant fraction of the qubits.Measurements are available during computation and take one time step.
Geometric assumptions: The required efficient LDPC codes may involve stabilizer generators acting on qubits far apart in finite-dimensional Euclidean space, requiring long-range gates.Codes with fully local syndrome measurements do not appear capable of constant overhead, though a few nonlocal generators may suffice.
Resource assumptions: Free classical computation is a key protocol assumption, allowing quantum fault-tolerance overhead to be outsourced to cheaper classical bits and computation.The paper aims to exploit this asymmetry between the cost of classical and quantum resources.

3 Main Result

The theorem gives fault-tolerant simulations with asymptotic overhead equal to the underlying quantum error-correcting code, provided the code family satisfies LDPC, sizing, and robust correction conditions. Below threshold, arbitrarily long reliable computations are possible, subject to circuit-size and minimum-size bounds.

Code-family conditions: The code family consists of constant-degree LDPC quantum error-correcting codes with asymptotic rate R.The theorem also requires suitable code sizes and robust correction under faults in error correction and syndrome measurement.
Main theorem: Under local stochastic noise below threshold, a circuit using k qubits and f(k) locations can be simulated with at most ηk/R physical qubits.This holds for sufficiently large k and for f(n)=o(g(n^α)), with 0 < αβ < 1 and η > 1.
Resource requirements: The simulation uses polynomially many physical locations when syndrome-repetition complexity T(n_i) is polynomial in n_i.A polynomial-time decoder also makes the required classical computation polynomial in size.
Main result: Below threshold, arbitrarily long reliable computations achieve asymptotic overhead equal to that of the underlying quantum error-correcting code.Unlike the usual threshold theorem, the construction has reduced overhead but requires a minimum circuit size k0.
Scope and limitations: For code families with g(n)=exp(poly(n)), the theorem applies to arbitrary polynomial-size circuits; families with g(n)=poly(n) impose a scaling limit.The threshold depends on code rate and on how closely the protocol approaches optimal overhead.

4 Efficient LDPC Codes

The section extends LDPC-code fault-tolerance analysis to adversarial stochastic noise and derives thresholds for noisy syndrome extraction. It then evaluates code families, finding that known constructions satisfy the theorem’s conditions but remain practically unsatisfactory.

Adversarial-noise decoding: Quantum LDPC codes with bounded-degree stabilizer graphs support cluster-counting bounds needed to generalize independent-noise results to adversarial stochastic noise.The proof bounds collections of connected clusters in bounded-degree graphs and applies this to the code’s stabilizer adjacency graph.
Adversarial-noise decoding: Theorem 3 gives a threshold p0 below which the logical error rate scales as ni(p/p0)di/2 and approaches zero as ni, di increase.The decoding algorithm selects a lowest-weight error consistent with the measured syndrome; the proof uses separated error clusters.
Noisy syndrome extraction: Initialization-spanning clusters must contain at least s/4 actual errors, producing a more stringent requirement p′′ < pf in the threshold analysis.The argument counts both initialization errors and errors during the correction cycle for clusters reaching the final time.
Known code families: Hypergraph product codes can have rate R arbitrarily close to 1, but increasing the rate lowers the thresholds p0, p1, and p2.This trade-off may suit systems with high-cost, very high-fidelity qubits.
Known code families: Known code families are not completely satisfactory: hyperbolic codes offer polynomial-time decoding but computation-time-dependent thresholds, while high-distance families lack efficient decoders.The section calls for better decoding algorithms or new families with efficient decoding and exponential error suppression.

5 Error Correction

The section compares fault-tolerant error-correction methods and develops Shor error correction for LDPC codes, whose bounded generator weights keep ancilla requirements controlled.

Shor error correction: Shor error correction measures each stabilizer syndrome bit with a tested cat state and transversal interactions with the encoded data.The cat state has one qubit per generator weight, and the measured syndrome is repeated for reliability.
Shor error correction: High-weight stabilizer generators make cat states fragile because a single phase error can corrupt a syndrome result, motivating LDPC codes.For large cat states, phase-error probability approaches one, so Shor correction becomes impractical.
Resource requirements: An [[n, k, d]] code with (r, c)-LDPC structure uses (n−k)r′ extra qubits for one Shor syndrome measurement, with depth O(r′c).Here r′ includes the cat-state and testing qubits; repeated measurements reuse these qubits.
Resource requirements: Non-overlapping stabilizer generators can be measured in parallel, while partitioning code blocks reduces relative extra-qubit overhead by a factor of s.Each block waits s times longer between syndrome measurements, increasing its effective storage-error rate by s.
Alternative correction: A single-ancilla alternative lowers preparation demands but permits one fault to propagate to multiple data qubits, unlike Shor’s transversal construction.The alternative is described as non-fault-tolerant in the usual sense.

6 Gates, Preparation, and Measurement

The section addresses universal gates and ancilla preparation for block codes, using concatenated fault tolerance and block partitioning to keep gate-related overhead sublinear.

Logical gates: Transversal gates support some logical operations but cannot form a universal gate set, so additional fault-tolerant gate techniques are required.Knill’s method supplies universal operations through encoded ancilla states and gate teleportation.
Logical gates: Knill’s procedure performs logical gates through Bell measurements and classical processing, using ancilla states encoded in the data code.For k logical qubits per block, the ancilla applies the desired operation to one selected qubit while identities act on the others.
Ancilla cost: An [[n, k, d]] code requires 2n or 4n extra ancilla qubits for Knill gate operations, and reliably building these blocks likely adds overhead.Non-Clifford operations require magic states, which are not stabilizer states.
Ancilla preparation: Concatenated fault-tolerant simulation can create arbitrary ancilla states, but its polylogarithmic overhead yields O(n polylog(n/ǫ0)) total qubits for the needed states.The required encoding circuits are polynomial, specifically quadratic, in the ancilla size.
Block partitioning: Splitting logical qubits across blocks of size [[n′, k′]] makes single-gate ancilla overhead O(n′ polylog(n′/ǫ0)), sublinear in n when n′ < n/polylog(n/ǫ0).Only one or a small number of gates can be performed at a time under this allocation.
Ancilla preparation: For LDPC codes, ancilla preparation can use constant quantum depth, O(log n′) classical depth, and fewer than 2n′ encoded qubits.The construction encodes, measures stabilizers, and applies a classically determined Pauli correction.

7 Combining the Components

The section combines block selection, syndrome correction, gate gadgets, and threshold analysis to bound logical errors while approaching constant qubit overhead for large computations.

Code selection: The construction divides k logical qubits among M=⌈k/ki⌉ blocks from a code family, choosing ni large enough for reliability but small enough to control overhead.The selected code index balances code size against the polylogarithmic overhead of concatenated preparation.
Noise reduction: Faults in the basic circuit model are mapped to data-qubit and syndrome-bit errors in the simplified model used for threshold analysis.The mapping accounts for faults occurring before, during, or after syndrome measurements and for correlated syndrome effects.
Noise reduction: Shor correction bounds syndrome-bit faults from ancilla preparation, controlled-Pauli operations, rotations, measurements, and data errors that can affect multiple syndrome bits.A data-qubit fault can produce up to ⌈c/2⌉ wrong syndrome bits, while direct syndrome errors are treated separately.
Threshold analysis: The protocol defines a threshold pT such that all required inequalities hold whenever the physical error rate p is below pT.The overall proof connects the simplified fault-tolerance model to the basic location-level model.
Threshold analysis: Choosing ni > k^α for sufficiently large k bounds the logical error rate per logical location by ǫ/f(k), while the construction remains within the desired code-size range.The choice uses f(k)=o(g(k^α)) for some α<1.
Overhead: The total extra-qubit count combines syndrome-correction resources and gate-location resources, with correction performed on one of every s blocks at a time.As ki/ni approaches the code-family rate R, the overhead parameter ω can be made arbitrarily small.

8 Depth of the Fault-Tolerant Circuits

The protocol achieves constant space overhead but incurs time overhead from repeated syndrome measurements and ancilla preparation. The paper leaves simultaneous constant space and time overhead unresolved.

Constant space overhead is achieved, but the protocol does not also achieve low time overhead.The depth increase has two main sources: repeated syndrome measurements and ancilla preparation.
Retaining syndrome information for blocks without gates can reduce each error-correction cycle to a single syndrome measurement.Accumulating information over the previous T(n_i) correction steps can provide reliable correction.
Knill error correction is less susceptible to syndrome-bit errors than Shor error correction, reducing the need for repeated syndrome measurements.Knill’s method can combine gate execution and error correction.
For circuits with at most k^γ simultaneous gates, the extra gate qubits are O(k^γ n_i polylog(n_i/ε_0)); when γ + α′ < 1, their asymptotic overhead is negligible.This condition keeps the number of qubits used for gates sub-linear at any given time.
Choosing small blocks permits time overhead k^(1−γ) with γ arbitrarily close to 1, but weaker error suppression then requires larger computations before the protocol helps.For the theorem’s code families, any α > 0 can cover polynomial-length computations, while small n_i gives failure probability 1/g(n_i).
Complete parallelism, γ = 1, appears impossible because ancilla state preparation has polylogarithmic overhead for all code blocks.Achieving it would require codes supporting more direct universal fault-tolerant gates or more efficient ancilla preparation.
In the paper’s model, time overhead can instead be made constant using standard fault-tolerance methods, with Knill gates appearing especially time-efficient.The model assumes free classical computation and no geometric restrictions on gates.

9 Conclusion

The paper establishes that fault-tolerant quantum computation can use few extra qubits in principle, but the result is asymptotic and depends on strong modeling assumptions and suitable code families. Important practical and computational questions remain open.

Few extra qubits suffice in principle, but the result relies on no geometric constraints, fast classical computation, and the asymptotic limit.The proof’s direct threshold estimate is pessimistic, and the paper notes that simulations suggest better thresholds may be possible.
The protocol’s main practical drawback is the absence of known quantum LDPC code families combining LDPC structure, exponential error suppression, and efficient decoding.This is identified as an important open question for the approach.
Current code-family limitations make numerical evaluation difficult: exponential-decoding cases are computationally expensive, while efficiently decoded hyperbolic codes suppress errors weakly.Consequently, studying actual performance requires either enormous computation or very large codes.
Better code families, improved ancilla construction, or approaches compatible with geometric locality could further reduce the protocol’s limitations.The conclusion argues that large extra-qubit overhead is not inherent to quantum fault tolerance.