A comparative code study for quantum fault-tolerance

1 Introduction

• The study compares previously considered and new codes by their thresholds, logical error rates, and overheads using the AGP ex-Rec method.The authors propose assessing these codes as bottom-level components of a fault-tolerant architecture.Source: §1 · p. 2
• The analysis assumes non-local gates, although locality constraints are expected to affect thresholds, especially for larger codes [2] [3].The cited work suggests the locality cost may be modest for small codes but typically worse for larger ones.Source: §1 · p. 2
• The study uses unbiased depolarizing noise, assigning equal probabilities to single-qubit X, Y, and Z errors and equal probabilities to 15 two-qubit errors.The authors choose this simpler model because a comparative study across general noise models is computationally infeasible.Source: §1 · p. 2
• Earlier threshold estimates used differing methods, so the authors favor one rigorously motivated framework for comparing codes.The study extends prior comparative Monte Carlo work by including more codes and analyzing fault-tolerant logical CNOT gates.Source: §1 · p. 3

1.1 The Code Architecture

• The proposed architecture pairs a high-threshold, reasonably low-overhead bottom code with a top code that reduces logical error further.The paper illustrates mapping a base error rate of O(10^-4) to O(10^-7), with a top code targeting O(10^-15).Source: §1.1 · p. 3

2 Preliminaries

• The threshold estimate depends on t, the number of errors correctable, and N, the count of failing sets of t+1 locations in an encoded gate.The section favors CSS codes partly because transversal CNOT minimizes the encoded CNOT’s size.Source: §2 · p. 4

2.1 Approximate Threshold Scaling

• With Amal growing faster than n and t linear in n, the threshold first rises with block size, then falls as Amal’s growth dominates.When Amal scales linearly with n and t=δn, the threshold instead increases and approaches a finite large-n value.Source: §2.1 · p. 4

2.2 Choice of Codes

• The study includes CSS code families and selected members, plus the [[5,1,3]] non-CSS code; quantum polynomial codes are considered as binary stabilizer codes.The selection includes quantum Reed-Muller, Hamming, BCH, surface, and Bacon-Shor codes, as well as concatenated codes.Source: §2 · p. 4, §2.2 · pp. 5–6
• BCH codes larger than [[47,1,11]] were impractical to simulate, and their large overhead limits their applicability as bottom codes.The paper notes that these larger codes may benefit considerably from their high t/n, but a bottom code should achieve low logical error at moderate overhead.Source: §2.2 · p. 6

2.3 Universality

• When transversal gates are limited to CNOT and Pauli operations, injection and distillation can supply |+i⟩ ancillas for S and Q, which together generate the single-qubit Clifford group.The described distillation uses seven unencoded |-i⟩ ancillas with Steane error correction to produce one |+i⟩ ancilla; encoded use begins by injecting a noisy ancilla.Source: §2.3 · pp. 6–7, Figure 3 · p. 7

3 Error Correction Circuits

• A 1-Rec combines an encoded gate with error correction, while its ex-Rec also includes preceding input error correction.For transversal gates, the encoded gate applies the physical gate across the qubit blocks.Source: §3 · p. 7, Figure 4 · p. 7
• Steane-EC couples verified encoded ancillas to data, measures them in the X or Z basis, and uses the syndrome to select corrections.Ancillas undergo R verification rounds; detected errors cause rejection, and L preparation attempts set an overhead parameter.Source: §3 · pp. 7–8, Figure 5 · p. 8

3.1 Specific Code Considerations

• The study prioritizes code error-correcting properties over Steane-network simplifications, whose relative advantage is unclear, and omits several possible optimizations.Omitted optimizations include different encoders for logical ancillas and removing detection steps for codes from perfect classical codes.Source: §3.1 · pp. 8–9
• Surface-code Shor-EC repeats syndrome measurements ℓ times on an ℓ × ℓ lattice, while Bacon-Shor encoding uses the method described in [19].The bare-ancilla Shor construction is fault-tolerant for surface codes on lattices of size 5 × 5 or larger when measurements are repeated enough times.Source: §3.1 · p. 9
• Reichardt’s [[49,1,9]] construction rejects a 49-qubit ancilla when any block-level detection finds an error and limits preparation attempts to L.The stated construction detects any single or pair of faults, so a third-order event is needed to evade its checks.Source: §3.1 · p. 9
• Polynomial codes decode measurement outcomes over GF(2^m), while the [[15,1,3]] Reed-Muller code has transversal T, which is not used in threshold analysis.The polynomial construction treats each qudit as m qubits and uses binary CSS operations.Source: §3.1 · pp. 9–10
• For [[5,1,3]], the study uses Knill-EC and constructs CNOT, S, and Cyc from T3 because the code lacks two-qubit transversal gates.The simulations assume perfect logical Bell pairs; CNOT and S are logical only after the full encoded T3 circuit.Source: §3.1 · p. 9, Figure 7 · p. 10

4 The Aliferis-Gottesman-Preskill (AGP) Method

• AGP tests whether a rectangle followed by an ideal decoder matches the ideal decoder followed by its simulated gate, classifying fault sets as benign or malignant.For t-strictly fault-tolerant constructions, any t or fewer locations in the ex-Rec are benign; weak fault tolerance permits some lower-weight malignant sets.Source: §4 · p. 10
• The ex-Rec accounts for faults in the leading 1-EC that can combine with later faults, avoiding the need to count incoming errors separately under the stated conditions.The argument assumes deterministic coupling of ancillas to data and complete stabilizer error correction, conditions the paper says its circuits satisfy.Source: §4 · pp. 11–12

4.1 Monte-Carlo Implementation of Method

• Monte Carlo simulation estimates ex-Rec failure under depolarizing faults, counting unavailable verified ancillas in internal 1-ECs as failures, with an exception for Reichardt’s [[49,1,9]] method.The study estimates thresholds from fitted failure-rate curves; it substitutes a perfect ancilla for failed preparations in Reichardt’s leading 1-EC to avoid possible double-counting.Source: §4.1 · pp. 12–13
• The study analyzes CNOT ex-Recs because they are the largest Clifford ex-Recs, while non-Clifford gates are assumed to use injection and distillation.The text says this implementation will not affect the threshold; Pauli gates are stored in a classical Pauli frame.Source: §4.1 · p. 12
• Malignant-set sampling is difficult for large-distance codes: the paper says it remains possible for Golay but not for codes of higher distance.The number of possible fault sets of size t + 1 grows with the total number of locations in the ex-Rec.Source: §4.1 · p. 13

4.2 Software and Computer Use

• The C++ simulation and circuit-synthesis programs use MPI and share functions and procedures, while runtime checks validate input and intermediate results.The project is open source, and the authors cite these shared procedures as increasing confidence in simulation output.Source: §4.2 · p. 13

5.1 Perfect Ancillas

• With flawless ancillas, the studied codes do not exceed a 1% threshold using Steane-EC; surface codes using Shor-EC are not expected to exceed about 3%.In this study, the flawless-ancilla assumption applies only to this section; the thresholds are largely determined by the code’s effective distance.Source: §5.1 · p. 14

5.2 Pseudo-Thresholds

• Pseudo-thresholds generally increase with L; at finite L, small R can outperform larger R, while the [[49, 1, 9]] code is expected to approach 1 × 10^-2 with many more attempts.For the same L, larger R can cause more ancillas to fail and increase the chance that an extended rectangle fails.Source: §5.2 · pp. 15–16
• (2.25 ± 0.03)×10^-3 is the maximum overall pseudo-threshold, attained by the Golay code with L = 30 and R = 1.The peak Bacon-Shor result is (1.224±0.005)×10^-3 for [[49, 1, 7]], while the peak surface-code result with Steane-EC is (1.008 ± 0.008)×10^-3 for [[41, 1, 5]].Source: §5.2 · p. 15, Figure 10 · p. 16

5.3 Influence of Storage Errors

• Zeroing memory-location errors raises the peak pseudo-threshold to (3.33±0.02)×10^-3, while storage errors otherwise have little influence.Bacon-Shor codes are least affected because their encoding circuits are simple; the [[5, 1, 3]] code is most affected because storage errors can enter at many locations.Source: §5.3 · p. 16

5.4 Logical Error Rate versus Overhead

• The study estimates overhead by counting physical CNOTs per rectangle, which approximately captures rectangle size as depth times width.The authors note that other measures include total qubits and circuit depth.Source: §5.4 · p. 16
• For fewer than O(10^4) CNOTs per rectangle, the Golay code has the lowest logical error rate, further reduced by increasing verification rounds to R = 2.Simplified verification could reduce Golay and Bacon-Shor overhead by at least a factor of 2; Eq. (1) estimates actual failure rates reasonably well.Source: §5.4 · pp. 16–17
• At p0 = 10^-4, pseudo-threshold changes need not track logical-error changes; when p0 is not near threshold, a target error rate may require fewer ancilla attempts.Some plotted error rates were extrapolated and should be treated as rough indications; the authors report error estimates an order of magnitude larger than those extrapolated values.Source: §5.4 · p. 17
• By overhead, [[9,1,3]] outperforms C4/C6, whereas C4/C6 beats [[7,1,3]]; surface-code error rates are relatively high, but their circuits are already 2D-local.The next two Bacon-Shor codes fall between C4/C6 levels 2 and 3 in the comparison.Source: §5.4 · p. 18

6 Discussion

• The Golay code reaches the study’s best threshold, about 2 × 10^-3, and Bacon-Shor codes are competitive with Knill’s C4/C6 scheme at a base error rate of 10^-4.The logical-error-rate-versus-overhead curve is an important figure of merit for this comparison.Source: §6 · p. 18
• Figures 13 and 14 plot level-1 CNOT ex-Rec failure probability against CNOTs per rectangle; Figure 13 compares the best-performing codes with C4/C6, while Figure 14 selects a monotone, per-size-best subset.Both figures evaluate error rates at p0 = 10^-4.Source: Figure 13 · p. 19, Figure 14 · p. 20
• Finite Steane-EC resources R and L can lower thresholds; for general quantum BCH codes, resource limits and encoding complexity can push thresholds down beyond a peak block size.For code families with low-weight stabilizers, Shor-EC may instead yield thresholds that grow with block size.Source: §6 · pp. 18–19
• The analyzed surface-code memory ex-Rec has an asymptotic threshold of about 3.5 × 10^-3, while Figure 15 expects error rates to fall exponentially as ℓ increases at fixed p0 = 10^-4.The reported asymptotic threshold is about half the value stated in; finite-block CNOT ex-Recs have an overhead–logical-error trade-off.Source: §6 · p. 19, Figure 15 · p. 21
• Choosing a top code requires its performance to determine when to switch from the bottom code and the total overhead; linear-in-n error-correction circuits are desirable because thresholds may otherwise decline with n.The discussion also expects a [[n, k, d]] block code to have a threshold comparable to a [[n, 1, d]] code.Source: §6 · p. 19
• The proposed architecture requires only a transversal CNOT from the bottom code, while a transversal top-code T gate can keep twice-encoded T errors similar to other Clifford-gate errors.The discussion notes possible constructions for implementing all gates needed for universality with approximately the same low error rate.Source: §6 · pp. 19–20

A Various Aspects of Steane-EC

• CSS stabilizers come from parity-check rows of C2 and C1, whose operators preserve the encoded states and whose logical X and Z operations correspond to the respective code spaces.The construction uses two classical linear error-correcting codes with the CSS containment relation.Source: A Various Aspects of Steane-EC · p. 21
• CSS codes are exactly the stabilizer codes with transversal CNOT; dual-containing CSS codes have transversal H, and doubly-even generators also give transversal S.The discussion notes that these codes have no transversal gates outside the Clifford group in this case.Source: A Various Aspects of Steane-EC · pp. 21–22
• Putting a generator matrix into standard form G = (I|A) yields an encoder with one CNOT per 1 in A, depth set by the largest row weight, and at most n + wn locations with memory noise.Bacon-Shor encoded ancillas can use O(n) two-qubit gates, while general unitary stabilizer circuits have O(n^2) gates and O(log n) depth.Source: A Various Aspects of Steane-EC · p. 22
• Verifying an encoded ancilla uses three additional ancillas, three transversal CNOTs, and three transversal measurements, with the stated cost depending on whether memory noise is included.The bounds are R(3Aenc + 6n) without memory noise and R(3Aenc + 6n) + n with memory noise; both assume equal communication costs.Source: A Various Aspects of Steane-EC · p. 22
• For Steane error correction, the CNOT extended rectangle has at most 8Aenc + 8Aver + 17n fault locations; setting R = t gives O(wnt), or O(n^3) in the worst case.The location count assumes equal communication costs between qubits.Source: A Various Aspects of Steane-EC · p. 22

A.1 Latin Rectangle Method for Optimizing Encoding Circuits

• Each 1 in the standard-form matrix A specifies a CNOT, and assigning those gates to time steps is equivalent to completing a Latin rectangle.The method starts from a generator matrix put in standard form by Gaussian elimination.Source: §A.1 · pp. 22–23
• For Steane’s [[7,1,3]] code, the encoder uses 9 CNOTs and can be scheduled in depth 3, the minimum depth for that matrix.The described procedure also restores the qubit permutation introduced during Gaussian elimination.Source: §A.1 · pp. 22–23
• The CNOT schedule is a bipartite edge coloring, and w colors are both sufficient and minimal, where w is the maximum row weight of A minus one.Vertices represent control and target qubits, while edges represent CNOTs; each color denotes a time step.Source: §A.1 · p. 23
• The authors tested several Latin-rectangle encoders with and without memory locations by simulation using CHP.The test is reported for several encoders produced by their software tool.Source: §A.1 · p. 23

B Syndrome Decoding

• The study uses six decoder types, including table lookup, cyclic-code lookup, Bacon-Shor majority voting, surface-code matching, concatenated-code message passing, and algebraic decoding for the [[47,1,11]] code.Table 2 lists the decoders used for the codes in the study.Source: B Syndrome Decoding · pp. 23–24, Table 2 · p. 24
• For cyclic codes, the Meggitt decoder stores syndrome-to-correction tables and can find a recovery using at most n table lookups.For nonbinary polynomial codes, the table also stores error type.Source: B Syndrome Decoding · p. 24
• The [[47,1,11]] decoder computes missing syndromes, finds roots of an error-location polynomial, and triggers a syndrome-dependent fallback if it cannot locate enough errors.The fallback maps the state into the code space, possibly incorrectly at the logical level.Source: B Syndrome Decoding · p. 24
• Bacon-Shor decoding applies one syndrome decoder to X errors and rotated Z errors, reducing the syndrome to a repetition-code parity check on column parities.The same decoder suffices for both error types because of the code’s stated symmetry.Source: B Syndrome Decoding · pp. 24–25
• Surface-code decoding maps defects to minimum-weight matching; Steane-EC gives a 2D problem and Shor-EC a 3D problem, with recovery applying phase flips along matched pairs.X and Z errors are treated as separate matching problems, with boundary defects included in the construction.Source: B Syndrome Decoding · p. 25
• The concatenated [[49,1,9]] decoder uses level-1 flags and a level-2 syndrome to correct errors of weight 4 or less; decoder tests found correction of all errors up to t for the tested codes.The large Bacon-Shor and surface-code algorithms were not exhaustively tested; the larger-family versions used algorithms tested on smaller codes.Source: B Syndrome Decoding · pp. 25–26

• For [[5, 1, 3]], the table notes identify NB and NC as parameters and specify the number of CNOT gates in a T3 rectangle.Source: C Data Tables · p. 27
• Tables 3–5 present the complete tabulation of code-survey data across three parts.Source: Table 3 · p. 28, Table 4 · p. 29, Table 5
• Bracketed values are extrapolated from a linear least-squares fit to the logarithm of p1(p0); for [[49, 1, 9]], a parameter counts preparation attempts for a 7-qubit encoded ancilla used in error detection.Source: C Data Tables · pp. 28–29
• Table 6 reports surface-code data using Shor-EC and a transversal CNOT, with ℓ syndromes for an ℓ×ℓ code EC.Source: Table 6 · p. 30
• Table 7 gives level-1 pseudo-thresholds for rectangles using Steane-EC with perfect ancillas, for n < 200.Source: Table 7 · p. 31