PaperlayerView exact revision on arXiv

Source-linked AI summary

Flag fault-tolerant error correction with arbitrary distance codes

Christopher Chamberland, Michael E. Beverland

arXiv:1708.02246v3quant-ph

TL;DR

The paper addresses the need for broadly applicable, low-overhead fault-tolerant error correction beyond existing code-specific flag methods. It introduces flag t-FTEC for arbitrary-distance stabilizer codes meeting specified conditions, using flag ancillas to identify dangerous errors during stabilizer measurement. Numerically, a 22-qubit flag 2-FTEC implementation for the [[19, 1, 5]] color code achieves lower logical failure rates than comparable schemes, while the authors identify code-family and circuit-construction boundaries for future work.

  • Problem

    Existing flag error-correction results targeted particular distance-three and error-detecting codes, while scalable quantum computing needs general schemes applicable across broader code families.

  • Method

    The paper introduces flag t-FTEC for distance d = 2t + 1 stabilizer codes satisfying specified conditions, using flag ancillas to signal errors whose weight exceeds the number of circuit faults.

  • Results

    With 22 qubits, flag 2-FTEC on the [[19, 1, 5]] color code achieves lower logical failure rates than comparable rotated distance-3 surface-code and Steane-EC schemes.

  • Takeaways & Limitations

    Flag error correction may support near-term qubit-limited experiments and low-overhead fault-tolerant protocols for quantum LDPC codes.

  • Takeaways & Limitations

    The sufficient condition developed for the code families does not apply to the Hamming code because of even-weight Z-type logical operators supported within some stabilizer generators.

Abstract

from arXiv · show

In this paper we introduce a general fault-tolerant quantum error correction protocol using flag circuits for measuring stabilizers of arbitrary distance codes. In addition to extending flag error correction beyond distance-three codes for the first time, our protocol also applies to a broader class of distance-three codes than was previously known. Flag circuits use extra ancilla qubits to signal when errors resulting from $v$ faults in the circuit have weight greater than $v$. The flag error correction protocol is applicable to stabilizer codes of arbitrary distance which satisfy a set of conditions and uses fewer qubits than other schemes such as Shor, Steane and Knill error correction. We give examples of infinite code families which satisfy these conditions and analyze the behaviour of distance-three and -five examples numerically. Requiring fewer resources than Shor error correction, flag error correction could potentially be used in low-overhead fault-tolerant error correction protocols using low density parity check quantum codes of large code length.

1 Introduction and formalism

Scalable quantum computing likely requires active stabilizer-based error correction, motivating general fault-tolerant schemes that support diverse codes with lower resource demands. The paper formalizes fault tolerance, develops flag error correction, and studies its applicability and potential uses.

  • 1 Introduction and formalism: Active error correction is likely necessary because proposed self-correcting quantum memories do not yet provide a practical route to reliable large computations.Topological approaches with physically imposed symmetries are also not expected to reduce error rates sufficiently for large computations.
  • 1 Introduction and formalism: Shor, Steane, and Knill error correction trade off broad code applicability, thresholds, transversal operations, syndrome-measurement resources, and qubit overhead.Shor applies to any stabilizer code but typically repeats syndrome measurements and uses verified cat states; Steane is restricted to CSS codes, while Knill often uses more qubits.
  • 1 Introduction and formalism: General fault-tolerant error correction schemes remain important for alternatives such as concatenated codes and high-rate, efficiently decodable quantum LDPC codes.The paper motivates developing schemes applicable to a wide range of codes, including settings where low-overhead fault-tolerant protocols are needed.
  • 1 Introduction and formalism: Flag error correction extends earlier code-specific flag methods to arbitrary-distance stabilizer codes satisfying specified code and circuit requirements.The approach uses extra ancillas to detect potentially problematic high-weight errors during stabilizer measurement, does not require verified state preparation, and has used fewer ancillas for codes considered to date.
  • 1 Introduction and formalism: The paper’s protocol is evaluated for error-correction performance rather than fault-tolerant logical gates, with future work deferred for gate implementation.Potential applications include early qubit-limited experiments and low-overhead fault-tolerant protocols for quantum LDPC codes.
  • 1.1 Fault-tolerant error correction: The analysis assumes a simple depolarizing circuit-noise model in which resting qubits and other circuit operations can fail with distinct probabilities.The paper defines Pauli weight, stabilizer syndromes, logical equivalence, and the operational fault-tolerance criteria used in its analysis.
  • 1.1 Fault-tolerant error correction: Fault tolerance requires both preservation of correctability under combined input errors and faults and prevention of unbounded error growth across correction rounds.The first condition prevents correctable errors from spreading, while the second bounds output errors after s faults even with arbitrary input errors.

2. With probability

The paper specifies circuit-level noise and estimates logical failure rates through Monte Carlo simulation. It also defines pseudo-thresholds for comparing fault-tolerant error-correction protocols.

  • 2. With probability: With probability 2p/3, a single-qubit measurement has its outcome flipped.The model separately assigns failure probabilities to resting qubits and other circuit operations.
  • 2. With probability: With probability p̃, each resting qubit receives an independently and uniformly sampled Pauli error from {X, Y, Z}.The analysis varies the resting-qubit error rate relative to the error rate for gates, preparations, and measurements.
  • 2. With probability: The considered two-qubit gates are CNOT, XNOT, and CZ, with XNOT and CZ defined through Hadamard conjugation of CNOT.These operations are part of the circuit-level noise analysis.
  • 2. With probability: Logical failure rates are estimated with N-run Monte Carlo simulations that propagate sampled location errors through fault-tolerant circuits and verify decoded outputs.A logical X or logical Z error during a run counts as a logical failure, and error bars are provided.
  • 2. With probability: The pseudo-threshold is defined as the physical error probability p at which the encoded protocol’s logical failure rate matches the relevant unencoded failure rate.The paper evaluates FTEC protocols without considering fault-tolerant logical gates.

2 Flag error correction for small distance codes

The paper develops flag error correction for distance-three codes by adding flag ancillas that expose otherwise dangerous high-weight data errors. For the Steane code, flagged errors have distinguishable syndromes, enabling fault-tolerant correction through repeated syndrome measurements.

  • Flag circuits: A single fault in an unflagged stabilizer-measurement circuit can create a multi-qubit data error and make a distance-three code fail.Such a fault can cause failure with fewer than (d − 1)/2 total faults for a distance-d code.
  • Flag circuits: Flag circuits use extra ancillas to signal when few faults produce data errors whose weight exceeds the number of faults.A t-flag circuit flags any error from up to t faults satisfying min(wt(E), wt(EP)) > v.
  • Flag 1-FTEC condition: The Flag 1-FTEC condition requires flagged single-fault errors for each stabilizer to have distinct syndromes or be logically equivalent.This condition lets subsequent syndrome measurements identify the relevant flag error despite the fault.
  • Flag 1-FTEC protocol: The Flag 1-FTEC protocol repeats flagged syndrome measurements and applies a correction after repeated consistent syndromes, differing syndromes, or a flag-triggered diagnosis.If a circuit flags, non-flag circuits provide a syndrome used to select a matching flag error when available.
  • Flag 1-FTEC protocol: The protocol may require up to three syndrome repetitions to guarantee that an undetected fault leaves at most a weight-one residual error.With no flags, an undetected fault cannot spread to a weight-two error; the second-round minimum-weight correction therefore preserves the fault-tolerance criterion.
  • Steane-code example: The Steane code satisfies the Flag 1-FTEC condition because its relevant Z-part flag errors have distinct syndromes, with the other stabilizers following by symmetry.For Zq1Zq2Zq3Zq4, the reduced set is {I, Zq1, Zq4, Zq3Zq4}.

3 Flag error correction protocol for arbitrary distance codes

The paper generalizes flag fault-tolerant error correction to arbitrary-distance stabilizer codes through circuit conditions that identify high-weight errors caused by faults. It gives a syndrome-measurement protocol, circuit constructions, and code-family examples satisfying the resulting criteria.

  • Protocol and conditions: A t-flag circuit flags errors whose weight, up to multiplication by the measured Pauli, exceeds the number of circuit faults.This extends flag circuits from distance-three settings to measurements supporting arbitrary-distance protocols.
  • Protocol and conditions: The flag t-FTEC condition requires correction sets to distinguish or logically equate all errors consistent with up to t faults.Under this condition, the protocol is fault-tolerant for t = floor((d−1)/2) faults.
  • Protocol and conditions: The protocol updates syndrome-difference and same-syndrome counters, then chooses corrections based on repeated syndromes, flags, and non-flag measurements.Its cases cover no flags, t flagged circuits, and fewer than t flagged circuits with counter-dependent corrections.
  • Resource comparison: The maximum syndrome-measurement rounds scale as 2(t^2 + 3t + 2), while the scheme avoids verified w-qubit cat states used by Shor error correction.The paper states that its protocol generally requires fewer syndrome repetitions than often-described Shor error correction.
  • Satisfying code families: The rotated surface-code family [[d^2, 1, d]] for odd d = 2t + 1 satisfies the flag t-FTEC condition with 4-flag circuits.The sufficient condition also covers self-dual CSS codes with stabilizers of weight at most six, including hexagonal color codes.
  • Satisfying code families: Self-dual CSS codes with stabilizer weight at most 2v satisfy a related flag t′-FTEC condition using (v−1)-flag circuits, where t′ = t/floor(v/2).This extends the sufficient-condition argument beyond the weight-6 case.
  • Satisfying code families: Quantum Reed-Muller codes [[n = 2^m − 1, k = 1, d = 3]] satisfy flag 1-FTEC using 1-flag circuits, while some Hamming codes do not satisfy the sufficient condition.The [[15, 7, 3]] Hamming code can fail the general condition for one circuit ordering, although permuting CNOT gates can restore it.
  • Circuit constructions: General 2-flag circuits measure arbitrary-weight stabilizers, requiring at most four flag qubits, with w/2−1 sufficient when w ≤ 8.Flag outcomes can further reduce correction sets and potentially broaden the family of codes satisfying the flag t-FTEC condition.

4 Circuit level noise analysis

The circuit-level analysis evaluates flag-FTEC protocols across distance-three and distance-five codes under several noise models, comparing logical failure rates, pseudo-thresholds, qubit costs, and circuit depth. Performance depends strongly on idle-qubit failure rates and the resource trade-off between lower qubit overhead and greater circuit depth.

  • Analysis scope: The analysis compares flag-FTEC, Steane-EC, and surface-code schemes using logical failure rates, pseudo-thresholds, qubit counts, and time steps.The study includes the [[5,1,3]], [[7,1,3]], and [[19,1,5]] codes under ˜p = p, ˜p = p/10, and ˜p = p/100.
  • Distance-five analysis: For the [[19,1,5]] color code, reducing idle-qubit failure probability from p to p/10 improves the pseudo-threshold by nearly a factor of six.This demonstrates the strong dependence of flag-FTEC performance on idle-qubit errors.
  • Resource trade-offs: Flag-FTEC uses fewer qubits but typically has increased circuit depth, making its pseudo-threshold sensitive to idle-qubit errors.For distance-three codes, flag 1-FTEC can use 7 qubits, while Steane-EC requires at least 35; when idle errors are much lower than gate, preparation, and measurement errors, flag-FTEC may suit early experiments.
  • Distance-five analysis: 22 qubits suffice for flag-EC on the [[19,1,5]] code, compared with 49 for the d = 5 surface code and at least 95 for Steane-EC.The corresponding pseudo-thresholds are (7.74 ± 0.16) × 10^-5, (2.63 ± 0.18) × 10^-4, and (5.60 ± 0.43) × 10^-5, respectively, for ˜p = p/100.
  • Distance-five analysis: For ˜p = p/100 and p ≲ 10^-4, flag-2-FTEC achieves lower logical failure rates than Steane-EC on the [[19,1,5]] code.The surface code has lower logical failure rates overall in the distance-five comparison but uses more qubits.
  • Cross-distance comparison: For ˜p = p/100 and p ≲ 1.5 × 10^-4, 22-qubit flag-FTEC outperforms Steane-EC using at least 35 qubits and the 17-qubit d = 3 rotated surface code.The higher distance of the [[19,1,5]] color code creates a parameter regime with lower logical failure rates than the considered distance-three schemes.

5 Conclusion

The conclusion presents flag t-FTEC as a general protocol for distance d = 2t + 1 stabilizer codes satisfying a flag condition, with examples spanning several code families. Numerical results indicate lower logical failure rates than comparable schemes in some low-qubit regimes, while circuit construction and decoding remain open challenges.

  • Protocol scope: Flag t-FTEC applies to stabilizer codes of distance d = 2t + 1 that satisfy the flag t-FTEC condition.Flag ancillas signal when v faults produce data errors of weight greater than v.
  • Code families: Quantum Reed-Muller, surface, and hexagonal lattice color codes satisfy the paper’s sufficient condition for flag t-FTEC.The paper also provides explicit circuits for distance-three and distance-five codes with stabilizer weights 4, 6, and 8.
  • Numerical evidence: With 22 qubits, flag 2-FTEC on the [[19,1,5]] color code can achieve lower logical failure rates than some schemes using similar qubit counts.The conclusion identifies comparisons with the rotated distance-three surface code and Steane-EC as numerical evidence for near-term applications.
  • Practical implications: The protocol tends to use fewer qubits than Steane, Knill, and Shor error correction, supporting possible use in qubit-limited fault-tolerant experiments.The conclusion frames this as a potential application rather than a universal performance advantage.
  • Open problems: Optimal arbitrary-weight flag circuits, additional qualifying code families, parallel stabilizer measurements, and efficient decoding remain open problems.The paper specifically seeks fewer flag qubits and CNOT gates, fewer false positives, compact multi-stabilizer circuits, and scalable decoding constructions.

A Proof that the flag t-FTEC protocol satisfies the fault-tolerance criteria of Definition 3

The proof establishes that satisfying the flag t-FTEC condition guarantees both fault-tolerance criteria by exhaustively analyzing syndrome repetition and flagging cases under at most t faults. Each case yields a correction that returns the data to the codespace or leaves only a bounded residual error.

  • Conclusion of proof: Claim 1 concludes that satisfying the flag t-FTEC condition guarantees both fault-tolerance criteria of Definition 3.The case analysis covers all possible errors arising from at most t faults.
  • Proof setup: The proof assumes at most t faults and defines benign faults as those that leave all syndrome measurements unchanged.Repeating syndrome measurements with t-flag circuits exhausts the possible cases under this fault bound.
  • No-flag cases: With no flags, repeating an identical syndrome t − n_diff + 1 times guarantees a fault-free round whose correction removes the data errors.The argument uses the bound on remaining faults after accounting for syndrome-changing faults.
  • Multiple flags: When t circuits flag, no other faults can occur, and the measured syndrome identifies logically equivalent errors whose product is corrected.The resulting correction returns the system to the codespace even for arbitrary-weight input errors.
  • Partial-flag cases: When fewer than t circuits flag, the protocol uses syndrome repetition to account for remaining faults and selects a correction from a logically equivalent error set.The residual difference from the input codeword is bounded by weight t − m − n_diff.

B Fault-tolerant state preparation and measurement using flag t-FTEC

Flag t-FTEC supports fault-tolerant state preparation and logical measurements with fewer qubits than Shor EC and without postselection. The procedures use extended stabilizers for encoded-state preparation and repeated fault-tolerant measurements with majority voting.

  • Overview: Fault-tolerant state preparation and measurement using flag t-FTEC require fewer qubits than Shor EC, and postselection is unnecessary.The construction follows a procedure similar to Shor EC while reducing qubit requirements.
  • State preparation: Preparing any n-qubit state followed by flag t-FTEC on extended stabilizers prepares the encoded |0⟩ state with at most t single-qubit errors.The extended stabilizers include the code stabilizers together with the logical Z operator.
  • Logical measurement: Fault-tolerant measurement of a logical Pauli operator performs flag t-FTEC, measures the operator with a t-flag circuit, and repeats the sequence 2t + 1 times.The final eigenvalue is chosen by majority vote.
  • Logical measurement: At least t + 1 of the repeated logical measurements are fault-free, so majority voting recovers the correct eigenvalue.Flags during error correction or operator measurement determine the possible error set used for subsequent correction.

C Candidate general w-flag circuit construction

The paper proposes a candidate general w-flag circuit for measuring Z^⊗w, using paired CNOT constructions and flag qubits to detect high-weight propagated errors. The construction has favorable generality but is not proven optimal and can exhibit problematic fault patterns in restricted variants.

  • Construction: The candidate construction measures Z^⊗w using paired CNOT_fm gates and CNOT_dm gates arranged into two flagging families.The first family is organized into sets s1, s2, and s3, while the full construction adds further CNOT_fm locations.
  • Analysis: The analysis restricts fault patterns to CNOT locations and uses propagation and affected-qubit terminology to track how faults spread through the circuit.Idle and measurement faults can be represented by at most as many CNOT faults for this analysis.
  • Flagging mechanism: Each CNOT_dm gate except the last two is followed by two partner CNOT_fm gates, so a single measurement-qubit Z error that reaches data is flagged.The partner placement spans different parts of the circuit to expose propagated errors.
  • Failure modes: The shorter first-family-only circuit can allow v faults to create more than v data errors without flagging, including patterns involving IZ or ZZ faults in s0.The identified mechanisms include faults near the ends of s0 and cancellation of propagated errors at later flag locations.
  • Failure modes: A poor ordering of CNOT_fm gates can let four faults produce a weight w/2 + 1 data error without a flag, motivating the specified ordering of s1, s2, and s3.The chosen ordering is intended to make propagated errors reach additional flag qubits unless further faults cancel them.
  • Resources and scope: The full candidate uses w − 1 flag qubits and 7w − 8 time steps, but optimal arbitrary-w constructions remain an open problem.For w = 6, another construction uses three flag qubits and 14 time steps instead of five and 34.

D Quantum Reed-Muller codes

The paper constructs the quantum Reed-Muller family QRM(m) with parameters [[2^m − 1, 1, 3]] and shows that it satisfies the sufficient flag 1-FTEC condition. Its stabilizers have structured supports derived from shortened Reed-Muller codes.

  • Code family: The quantum Reed-Muller family QRM(m) has parameters [[2^m − 1, k = 1, d = 3]].The construction follows recursively defined classical Reed-Muller generator matrices.
  • Fault tolerance: The QRM(m) family satisfies the sufficient flag 1-FTEC condition required by the protocol.This establishes QRM(m) as an infinite code family compatible with the paper’s flag-error-correction framework.
  • Construction: The X stabilizers are derived by deleting the first row and column of G_m, while the Z stabilizers come from the correspondingly shortened H_{m−2,m}.This produces the generator matrices used for the quantum code’s stabilizer structure.
  • Stabilizer structure: Every X-type stabilizer has a corresponding Z-type stabilizer, and each X generator has weight 2^m − 1.The remaining Z generators have weight 2^(m−2) and support contained within some weight-2^m−1 X-generator support.

E Implementation of Steane error correction

The paper implements and compares Steane error correction for CSS codes, emphasizing the ancilla verification needed for fault tolerance. For the [[19, 1, 5]] code, full Steane correction improves logical failure rates but uses substantially more qubits than flag 2-FTEC.

  • Protocol: Steane error correction extracts syndromes using encoded |0⟩ and |+⟩ ancillas prepared in the same CSS code as the data.Transversal CNOTs and complementary-basis measurements obtain X- and Z-type syndromes.
  • Fault tolerance: Unverified ancilla preparation is not fault tolerant because one preparation error can become a multi-qubit error and spread to the data.Verifier ancillas detect multi-weight errors, rejecting the prepared state when errors are found.
  • Fault tolerance: For general CSS codes, both X- and Z-error verification is required, whereas the simpler circuit is fault tolerant only for perfect distance-three CSS codes.The paper uses the more complete circuit when the code does not have the special properties of the [[7, 1, 3]] code.
  • [[19, 1, 5]] comparison: For the [[19, 1, 5]] code, the reduced Steane circuit has leading logical-failure behavior p_L = c_1p^2 + c_2p^3 + O(p^4), rather than the distance-five form c p^3 + O(p^4).The reduced circuit minimizes physical-qubit use but does not satisfy all fault-tolerance criteria for this non-perfect CSS code.
  • [[19, 1, 5]] comparison: 171 qubits for full Steane correction yield lower logical failure rates than the 95-qubit reduced circuit, while flag 2-FTEC uses only 22 qubits but has a pseudo-threshold one to two orders lower.The comparison is made under noise models with idle-qubit failure probabilities p and p/100.

F Implementation of Surface code error correction

The surface-code implementation maps noisy stabilizer measurements to decoding graphs and uses minimum-weight matching to infer corrections. Its performance depends sensitively on the chosen measurement circuits because circuit faults can create harmful propagated errors.

  • Code and measurements: The rotated surface code uses n = d^2 data qubits for distance d and measures X- and Z-type stabilizers with dedicated measurement ancillas.The paper illustrates the d = 3 layout and the corresponding stabilizer-measurement circuits.
  • Decoding graph: Perfect-measurement decoding represents Z stabilizers as graph nodes and data qubits as edges in the planar graph G2D.Boundary nodes and edges complete the graph representation used for minimum-weight correction.
  • Circuit-noise effects: The code’s performance is sensitive to measurement-circuit choice, and a poor circuit can allow one fault to cause a logical failure for d = 3.Thus the circuit design is part of the fault-tolerant implementation rather than a neutral measurement detail.
  • Circuit-noise effects: A single circuit fault can produce diagonal decoding edges because an error may be detected by one stabilizer before another.The figure also illustrates correlated errors arising during X-type measurement circuits.
  • Decoding graph: Circuit-noise decoding stacks d copies of G2D into G3D and adds inter-layer and diagonal edges so single measurement-circuit faults correspond to weight-one edges.The graph is then used to identify correction paths from changed stabilizer outcomes.
  • Decoding procedure: The decoder stores d rounds of noisy stabilizer outcomes followed by one perfect round, highlights changed-outcome nodes, and applies minimum-weight matching.Matched edges are vertically collapsed into G2D before the inferred Pauli correction is applied.

G Compact implementation of flag error correction

This section compares compact flag-error-correction implementations for the [[7, 1, 3]] code, varying ancilla count, circuit depth, and stabilizer-measurement scheduling. Using fewer ancillas can yield a higher pseudo-threshold and lower logical failure rates under the stated conditions.

  • Circuit construction: The [[7, 1, 3]] Steane-code circuit measures Z stabilizer generators using one flag qubit and three measurement qubits.A single fault causing an error of weight greater than one triggers the flag, and flagged errors have unique syndromes.
  • Performance comparison: Table 6 reports pseudo-thresholds and circuit depth for two- and four-ancilla flag-EC protocols under noise models with ˜p = p and ˜p = p/100.The corresponding comparison is summarized for the [[7, 1, 3]] code.
  • Performance comparison: Figure 23 compares logical failure rates for flag 1-FTEC protocols using two and four ancilla qubits on the [[7, 1, 3]] Steane code.The comparison complements the pseudo-threshold and circuit-depth results in Table 6.
  • Scheduling and resources: The four-ancilla protocol measures all Z stabilizer generators in one cycle, while X stabilizers are measured separately.The two-ancilla method requires at most two extra time steps for stabilizer measurement.
  • Performance comparison: The two-ancilla protocol achieves a higher pseudo-threshold than the four-ancilla protocol in the reported comparison.Using more ancillas introduces additional idle-qubit locations where errors can occur.

H Stabilizer generators of various codes.

The section lists stabilizer generators for several quantum error-correcting codes, including distance-three and distance-five examples. It also includes representatives of the codes’ logical operators.

  • Distance-three codes: The listed codes include the [[5, 1, 3]] code and the [[7, 1, 3]] Steane code.These are the distance-three examples identified in the table description.
  • Distance-five codes: The section includes the [[19, 1, 5]] and [[17, 1, 5]] color codes as distance-five examples.Both are identified as members of a family of color codes.
  • Logical operators: The stabilizer-generator table’s last row gives representatives of the logical operators for the listed codes.The table covers the 5-qubit, Steane, and two color-code examples.
Loading 1708.02246v3…