Source-linked AI summary
Constant overhead quantum fault-tolerance with quantum expander codes
Omar Fawzi, Antoine Grospellier, Anthony Leverrier
TL;DR
The paper addresses whether quantum fault tolerance can avoid the polylogarithmic space overhead of standard threshold constructions. It combines Gottesman’s framework with quantum expander codes and analyzes a decoder robust to noisy syndrome measurements, obtaining constant overhead together with single-shot and logarithmic-depth decoding.
Problem
Standard fault-tolerant quantum computation protects against noisy hardware but typically requires space overhead that grows polylogarithmically with the original computation size.
Method
The paper combines Gottesman’s constant-overhead framework with constant-rate quantum expander codes and analyzes the small-set-flip decoder under noisy syndrome measurements.
Results
Quantum expander codes achieve constant-overhead fault tolerance, with ηk physical qubits for k logical qubits, while the decoder is robust to noisy syndromes, single-shot, and parallelizable to O(log n) depth.
Takeaways & Limitations
The construction provides a route to fault-tolerant quantum computation whose space overhead can approach 1 as the physical error rate becomes sufficiently small.
Takeaways & Limitations
The analysis assumes suitable large-expansion constant-degree bipartite graphs, error-free classical computation, and a decoding-step error rate independent of computation size.
Abstract
from arXiv · showhide
We prove that quantum expander codes can be combined with quantum fault-tolerance techniques to achieve constant overhead: the ratio between the total number of physical qubits required for a quantum computation with faulty hardware and the number of logical qubits involved in the ideal computation is asymptotically constant, and can even be taken arbitrarily close to 1 in the limit of small physical error rate. This improves on the polylogarithmic overhead promised by the standard threshold theorem. To achieve this, we exploit a framework introduced by Gottesman together with a family of constant rate quantum codes, quantum expander codes. Our main technical contribution is to analyze an efficient decoding algorithm for these codes and prove that it remains robust in the presence of noisy syndrome measurements, a property which is crucial for fault-tolerant circuits. We also establish two additional features of the decoding algorithm that make it attractive for quantum computation: it can be parallelized to run in logarithmic depth, and is single-shot, meaning that it only requires a single round of noisy syndrome measurement.
1 Introduction
Quantum fault tolerance traditionally incurs polylogarithmic space overhead, while this work shows that quantum expander codes can achieve constant overhead with robust, single-shot, logarithmic-depth decoding.
- 1 Introduction: Constant-rate quantum expander codes enable fault-tolerant quantum computation with constant space overhead, potentially arbitrarily close to 1 at sufficiently small physical error rates.This approach addresses the polylogarithmic overhead associated with concatenated-code fault tolerance.
- 1 Introduction: Theorem 1 provides ηk physical qubits for a k-qubit computation, with depth O(f(k)) and noisy-circuit output within total variation distance ε of the ideal output.The guarantee holds for sufficiently large k and physical error rate below pT(η).
- 1 Introduction: The construction assumes constant error during decoding, sufficiently expanding constant-degree bipartite graphs, and error-free classical computation.The paper notes unresolved graph-construction and threshold limitations, as well as a restriction to sufficiently large codes.
- Main result and proof techniques: The small-set-flip decoder remains effective under noisy syndrome measurements, correcting errors while leaving a controlled residual error with high probability.The residual error E ⊕ Ẽ is equivalent to a local-stochastic error, except with failure probability e^-Ω(√n).
- Main result and proof techniques: The decoding algorithm parallelizes to O(log n) depth, limiting storage errors accumulated during classical decoding.The analysis uses syndrome locality, error clusters, and witness sets to establish robust correction under stochastic noise.
- Main result and proof techniques: The decoder is single-shot, requiring one noisy syndrome measurement rather than polynomially many repetitions.This avoids repeated syndrome measurements used in typical constructions.
2 Preliminaries
The section develops quantum expander codes and their small-set-flip decoder, then applies the decoder in a fault-tolerant construction with constant overhead. The decoder tolerates noisy syndromes, is parallelizable, and supports the stated fault-tolerance guarantees.
- Decoding: The small-set-flip algorithm cycles through stabilizer generators and applies syndrome-reducing error patterns, running in linear time and correcting errors below a graph-dependent linear-weight bound.
- Decoding: The analysis establishes that noisy-syndrome decoding remains effective and that the algorithm can be parallelized to logarithmic time.
- Noisy-syndrome decoding: The noisy-syndrome variant changes the input, stopping condition, and candidate flip set, producing a controlled local-stochastic residual error when δ < 1/16.
- Fault-tolerant construction: The fault-tolerant simulation uses encoded blocks and alternating simulation and error-correction cycles, with noisy circuits requiring ηk physical qubits, depth O(f(k)), and O(kf(k)) locations.
- Fault-tolerant construction: The construction bounds failure probability by δ under sufficiently small local-stochastic noise and gives resource bounds involving m log^c1(|D|/δ), while adding O(log log f(k)) quantum depth and O(log k) classical time.
3 Analysis of Algorithm 2
The analysis extends small-set-flip decoding to noisy syndrome measurements and establishes conditions under which the residual error remains controlled. It also develops supporting structural arguments for reduced errors, critical generators, local witnesses, and high-probability success.
- Noiseless decoding: The noiseless case previously showed that small-set-flip outputs an error equivalent to the input with probability at least 1 − e^-Ω(√n) under D = ∅.This result is generalized by Theorem 13 to nonempty syndrome errors.
- Noisy-syndrome decoding: Theorem 13 shows that under sufficiently small physical and syndrome noise, the residual error is equivalent to a local stochastic error except with probability e^-Ω(√n).The theorem requires δ < 1/16, β < β1, and positive thresholds p0 and p1 for the physical and syndrome noise parameters.
- Small adversarial errors: Expansion arguments identify critical generators and valid flips that decrease syndrome weight for sufficiently small reduced errors.These arguments underpin Proposition 14, Lemma 15, and Corollary 16, which relate residual error size to noisy-syndrome support.
- Random errors of linear size: Percolation bounds connected error clusters, while syndrome-graph locality lets the decoder correct each cluster independently.The execution support and witness constructions extend these cluster arguments to random linear-weight errors and establish high-probability local-stochastic residuals.
4 Parallel version for Algorithm 2
The parallelized decoder partitions X-type generators into a constant number of non-interacting color classes, enabling parallel flips and logarithmic-depth execution while preserving the noisy-syndrome decoding guarantee.
- Parallelization: The X-type generators are partitioned into fewer than χ sets whose syndrome supports do not intersect, allowing each set to be decoded in parallel.A coloring of an auxiliary generator graph supplies the required constant-size partition.
- Algorithm: The algorithm processes a syndrome containing both qubit errors and syndrome-measurement errors, outputting a qubit-error estimate ˆE.Each colored round updates the estimate and syndrome by applying selected flips.
- Correctness proof: The parallel proof establishes locality, rapid syndrome reduction, witness construction, and an equivalent reduced residual error under bounded execution support.These lemmas transfer the sequential analysis to the parallel decoder.
- Parallelization: With f = f0(|σ|) steps, the parallel algorithm has logarithmic complexity in the input size.The fixed-step schedule replaces the sequential algorithm’s execution until no syndrome-reducing flip remains.
- Parameter trade-off: The parameter c trades fewer decoding steps for a worse residual-noise parameter, whereas values near c2 + 1 improve residual noise but increase the number of steps.Thus parallel-decoder depth and residual-error quality cannot be optimized independently through c.