Graphical algorithms and threshold error rates for the 2d colour code

1 Introduction

• Topological codes suit architectures with local interactions: unlike concatenated codes, they are designed around locality constraints, and the 2d surface code has a threshold approaching 1%.The cited 2d-lattice thresholds for the Steane and Bacon-Shor codes are 1.85 × 10−5 [9] and 2.02 × 10−5 [10], respectively.Source: §1 · p. 1
• Surface-code state distillation uses repeated circuits to improve approximate resource states and may require several orders of magnitude more qubits than the rest of the computer.The example |Y⟩ distillation circuit takes seven approximate states as input to produce a better approximation.Source: §1 · p. 2
• The colour code of [3] may incorporate desirable surface-code features while implementing S gates transversally, although T gates still require state distillation.The paper identifies the colour-code threshold as a missing determination.Source: §1 · p. 2
• 6.25% is the analytic lower bound for the 2d colour-code threshold with error-free syndrome extraction; simulations suggest it may reach 13.3%, while faulty extraction circuits reduce it to approximately 0.1%.The paper also presents an approximate hypergraph-matching correction method.Source: §1 · p. 2
• The paper reviews the colour code and error correction, then presents simulations with non-ideal extraction and two ideal-extraction threshold estimates: simulation and combinatorics.The section sequence is described in the paper’s roadmap.Source: §1 · p. 2

2 Error correction on the 2d colour code

• The code uses red, green, and blue plaquettes with X- and Z-stabilisers, and errors are inferred from eigenvalue changes in adjacent stabilisers.An X error toggles adjacent Z-stabilisers; Z errors are detected through X-stabilisers.Source: §2 · pp. 2–3
• Error chains produce terminals; 2-chains have two same-colour terminals, while 3-chains have one terminal of each colour.Chains with more than three terminals can be decomposed into lower-order chains with overlapping terminals.Source: §2 · p. 3, Figure 2 · p. 4
• The decoder maps terminals to hypergraph nodes and possible 2- and 3-chains to edges and hyperedges, then seeks a perfect matching that reproduces the syndrome.General hypergraph matching lacks known efficient algorithms; graph matching has polynomial-time algorithms such as Edmonds’ blossom algorithm [17–19].Source: §2 · pp. 3–4
• Minimum-chain-length weights approximate maximum-likelihood matching, but omit the multiplicity of error chains that can produce the same terminals.The approximation finds a syndrome-producing matching with the fewest errors under ideal syndrome extraction; accounting for alternative chains could potentially increase the threshold.Source: §2 · p. 4, Figure 3 · p. 5
• Finite-lattice boundaries hide terminals, while many-terminal chains can be misread as longer error events unless overlapping terminals are handled.Dummy node pairs can address overlaps without arbitrary-rank hyperedges, but real implementations must identify overlaps without access to the number of toggles at each plaquette.Source: §2 · pp. 4–6

3 Logical qubits and logical gates

• Logical qubits are encoded on triangular lattices, and logical X and Z operations are odd-length chains masked by the boundaries.The minimum length of such chains defines the code distance.Source: §3 · pp. 6–7, Figure 6 · p. 7
• The colour code supports transversal Hadamard, S, and controlled-not gates on the specified lattices or across two sheets.Applying Hadamard to every qubit exchanges X- and Z-chains; transversal S acts on the logical states for odd-distance codes.Source: §3 · p. 7
• Defects can form logical qubits from one defect of each colour, retaining surface-code features while permitting transversal S gates.Defects are contiguous regions where particular stabiliser generators are no longer measured.Source: §3 · p. 7, Figure 7 · p. 8

4 Hypergraph mimicry and pair assignment

• The procedure never matches the hypergraph directly; it solves an approximate graph problem and maps its solution back to a candidate correction.The candidate need not have the minimum weight-sum hypergraph matching.Source: §4 · p. 8
• Replacing green–blue edges with paths through four added nodes represents pairs in a mimic graph while preventing terminals from participating in two error chains.The pair node p represents the green and blue nodes together, and p′ serves as its boundary; red-to-pair edges represent rank-3 hyperedges.Source: §4 · p. 9, Figure 10 · p. 9, Figure 11 · p. 10
• Mimic-graph matchings can be malformed because the matching algorithm does not enforce the triplet patterns needed for a valid correction.The method can often repair malformed patterns with a weight-0 alternating cycle; rematching with red and green collapsed avoids searching for such cycles.Source: §4 · p. 10, Figure 12 · p. 11, Figure 13 · p. 11
• The algorithm tries several pair assignments, collapses each into a trial graph, and selects the lowest-weight trial solution.The method also considers mimic-graph constructions with different colour permutations and uses the corresponding matching weights to select assignment choices.Source: §4 · pp. 10, 12
• The mimic matching weight-sum is at most the minimum-weight hypergraph matching weight-sum, while trial matching weight-sums are at least that minimum.When the trial and mimic weight-sums are equal, the trial matching is itself a minimum-weight hypergraph matching.Source: §4 · p. 12
• Using up to 6 × 25 initial trials gives a 95% probability of recovering the minimum-weight hypergraph matching with certainty for a single time step with d+1 errors on large lattices.Using 6 × 50 trials did not significantly increase that probability; remaining uncertain corrections typically had weight-sums only one greater than the mimic matching.Source: §4 · p. 12

5 Simulation results

• The simulations measure average syndrome-extraction cycles before logical failure, tracing X-errors on triangular-lattice colour codes.Each timestep includes memory errors and syndrome extraction; the stated preparation, measurement, and two-qubit gate error probabilities are p, p, and p/15 per non-trivial Pauli product, respectively.Source: §5 · p. 12
• Approximately 0.1% is the indicated asymptotic threshold error rate for the colour-code quantum memory with faulty syndrome extraction.The simulations could not reach higher-distance codes to observe convergence.Source: Figure 14 · p. 13, §5 · p. 14
• Collecting syndrome information over time creates a 3d structure that permits error chains to span time, with time-spanning segments weighted like equal-length spatial segments.The simulations also collect one final ideal syndrome before error correction and checking for logical failure.Source: §5 · p. 13
• Correlated syndrome-extraction errors and approximate correction leave distance-3 performance no better than an uncorrected qubit and let distances 5, 7, and 9 correct the same number of errors.The authors assert that higher distances will eventually correct more errors under this method.Source: §5 · p. 13
• Successive-distance curve intersections move substantially and leftwards, so they do not provide a lower bound on the threshold.The authors suggest lattice boundaries may partly explain the movement.Source: §5 · p. 13

6.1 Direct simulation

• With correct syndrome information under ideal syndrome extraction, each timeslice is corrected independently, so the logical error rate per timestep is obtained by summing over all possible dangerous syndrome combinations.Here, p0 is the physical error rate, Q(d) is the number of data qubits, and A_d(k) is the number of dangerous syndromes resulting from k errors in the distance-d code. Under true minimum-weight hypergraph matching and ideal syndrome extraction, two errors are the minimum required for a distance-d code to fail.Source: §6.1 · p. 14
• 13.3% is the estimated threshold under ideal syndrome extraction, based on direct simulation and the intersection of successive distance-code curves.The simulation samples failure ratios for error configurations and uses the matching algorithm to estimate the prefactors; Fig. 15 gives the threshold estimate.Source: §6.1 · p. 14, Figure 15 · p. 15

6.2 Dangerous syndrome coverage

• The paper conjectures that dangerous F+k syndromes arise from F errors on one continuous length-(d+2λ) chain plus k further errors, rather than simply adding errors to any dangerous F-error syndrome.The proposed bound counts continuous chains by starting from an error on the Q qubits and shifting up to three terminals.Source: §6.2 · pp. 15–16
• Ad(F) grows exponentially with code distance, and enumerating length-d logical operators and unique F-error combinations confirms the predicted asymptotic behavior.For higher orders, the reported gradients agree with the combinatoric error rate, although approximate matching also lets longer logical operators contribute to Ad(F+1) and Ad(F).Source: §6.2 · p. 16, Figure 16 · p. 17
• The growth-rate argument is not rigorous: it remains unproven that a constant λ exists for all distances on this geometry.The simulations appear to follow the predicted growth rates, but the lower-bound argument depends on the initial conjecture.Source: §6.2 · p. 17

• The approximate rank-3 hypergraph matcher constructs upper- and lower-bounded graphs; when their bounds meet, the approximation introduces no errors.The method can serve as an initial pass before less efficient methods attempt to improve performance.Source: §7 · p. 17
• The general correction procedure is a minimum-weight hypergraph perfect matching problem, with the approximate method potentially applicable to other 3-colour codes.Source: §7 · p. 17
• Under ideal syndrome extraction, p_th ≥ 6.25% analytically and may reach 13.3%; faulty extraction lowers the simulated threshold to approximately 0.1%.Source: §7 · pp. 17, 19, Figure 19 · p. 19
• A specialized matching algorithm for colour codes with boundaries may raise the threshold lower bounds and improve the scheme's prospects.Source: §7 · p. 19