Efficient color code decoders in $d\geq 2$ dimensions from toric code decoders

Aleksander Kubica; Nicolas Delfosse

Source-linked AI summary

Efficient color code decoders in $d\geq 2$ dimensions from toric code decoders

Aleksander Kubica, Nicolas Delfosse

arXiv:1905.07393v3May 17, 2019quant-ph

TL;DR

Color-code decoding is considered more challenging than toric-code decoding because its excitations can arise in pairs or triples. The paper introduces the Restriction Decoder, combining toric-code decoding with local lifting, and reports a 2D threshold on par with leading efficient toric-code decoders.

Problem
Color-code decoding must account for excitations created in same-color pairs or three-color triples, and has been considered more challenging than toric-code decoding.
Source: §1.2 · pp. 3–4
Method
The Restriction Decoder combines decoding on restricted lattices with local lifting to produce a color-code recovery operation.
Source: §1.3 · pp. 5–6
Results
10.2% is the estimated 2D color-code threshold on the square-octagon lattice, on a par with leading efficient toric-code decoder thresholds of 9.9–10.3% on the square lattice.
Source: §6 · p. 32
Takeaways & Limitations
The decoder succeeds if and only if the corresponding toric-code decoding succeeds, so its performance is determined by the chosen toric-code decoder and restricted lattices.
Source: §6 · p. 32
The reported numerical estimates assume perfect syndrome extraction; measurement errors require accounting for data from multiple rounds for point-like excitations.
Source: §6 · p. 32

Abstract

from arXiv · show

We introduce an efficient decoder of the color code in $d\geq 2$ dimensions, the Restriction Decoder, which uses any $d$-dimensional toric code decoder combined with a local lifting procedure to find a recovery operation. We prove that the Restriction Decoder successfully corrects errors in the color code if and only if the corresponding toric code decoding succeeds. We also numerically estimate the Restriction Decoder threshold for the color code in two and three dimensions against the bit-flip and phase-flip noise with perfect syndrome extraction. We report that the 2D color code threshold $p_{\textrm{2D}} \approx 10.2\%$ on the square-octagon lattice is on a par with the toric code threshold on the square lattice.

1 High-threshold decoder for the 2D color code

The section introduces the 2D color code and its decoding challenge, then presents the Restriction Decoder and estimates its threshold on the square-octagon lattice. The decoder reduces decoding to restricted-lattice edge chains followed by local lifting.

1.1 A brief overview of the 2D color code

The 2D color code places qubits on triangular faces of a 3-colorable lattice and associates X- and Z-type stabilizers with its vertices.Its logical Pauli operators can be implemented by string-like operators forming non-contractible loops.Source: §1.1 · pp. 2–3

1.2 The problem of color code decoding

Color-code decoding must handle excitations created in pairs of the same color or triples of three different colors, making it more challenging than toric-code decoding.A single-qubit Pauli Z error creates three differently colored excitations, while a two-qubit error creates a same-color pair.Source: §1.2 · pp. 3–4

1.3 The Restriction Decoder for the 2D color code

The Restriction Decoder finds edge chains matching the R-G and R-B restricted syndromes, then locally lifts those chains to construct a color-code correction.The local lift selects neighboring faces whose boundary matches the chains around each R vertex.Source: §1.3 · p. 5
Unlike the decoder in Ref., the Restriction Decoder uses two restricted lattices and local lifting, yielding fully local decoders in d ≥3 dimensions.It also always returns a valid color-code correction.Source: §1.3 · p. 6

1.4 Numerical estimates of the color code threshold

10.2% is the estimated phase-flip threshold for the 2D color code on the square-octagon lattice, matching the MWPM threshold for the toric code on the square lattice.The estimate uses periodic-boundary lattices and the crossing of decoding-failure curves for different linear sizes.Source: Figure 2 · p. 6, §1.4 · p. 7

2 Going beyond two dimensions

This overview establishes chain-complex and lattice language for toric and color codes, then frames toric-code decoding as a minimum-weight filling problem or, in some dimensions, a Sweep Decoder. It also defines the higher-dimensional color code and its syndrome and logical-operator structure.

2.1 CSS stabilizer codes and chain complexes

A CSS chain complex represents stabilizers, qubits, and syndromes as vector spaces connected by boundary maps, with ∂X ◦ ∂Z = 0.For a Z-error ϵ, the X-syndrome is ∂Xϵ; decoding succeeds when the error and correction differ by a stabilizer.Source: §2.1 · pp. 7–8

2.2 Lattices

A homogeneous simplicial lattice has simplex cells whose intersections are shared faces; stars collect incident simplices, while links collect nonintersecting simplices sharing a higher-dimensional simplex.The join of disjoint simplices is the smallest simplex containing both.Source: §2.2 · p. 8

2.3 Boundary operators

Boundary maps define chains, cycles, and boundaries; generalized boundary operators are introduced for color-code analysis, where their compositions need not generally vanish.For standard boundary maps, every boundary is a cycle.Source: §2.3 · p. 9

2.4 The toric code in d ≥2 dimensions

The d-dimensional toric code places qubits on k-cells and defines X- and Z-stabilizers from neighboring (k−1)- and (k+1)-cells.Its logical Z operators correspond to nontrivial k-cycles, while X-type syndromes are (k−1)-boundaries.Source: §2.4 · pp. 9–10

2.5 Toric code decoding

Toric-code decoding seeks a k-chain matching the observed syndrome, with success requiring the error and correction to differ by a boundary.Under uniform phase-flip noise, choosing the most likely error reduces to the k-Minimum-Weight Filling problem; efficient general solutions are not known for most k.Source: §2.5 · p. 10
The Sweep Decoder uses a cellular automaton for toric codes with k ≠ 1, and is described as fully local, parallelizable, and generically high-threshold, including with measurement errors.The authors use it to develop cellular-automaton color-code decoders in d ≥3 dimensions.Source: §2.5 · p. 11

2.6 The color code in d ≥2 dimensions

A d-dimensional color code is defined on a vertex-(d + 1)-colorable simplicial lattice, with qubits on d-simplices and stabilizers associated with lower-dimensional simplices.Its logical Z operators are k-dimensional objects, and X-type syndromes are collections of (k − 1)-dimensional excitations.Source: §2.6 · p. 11

3 Colexes and restricted lattices

This section develops colexes and four lemmas about locally restricting chains, filling boundaries, choosing cycle colors, and representing boundaries through links. It then constructs restricted lattices and proves that their kth homology agrees with that of the original colex.

3.1 A local structure of colexes

A d-colex is built from colorable d-balls joined along boundaries, and colorable balls are d-disks whose boundaries are lower-dimensional colexes.The construction provides the lattice structure used for higher-dimensional color codes.Source: §3 · p. 12, §3.1 · p. 12, Figure 4 · p. 12

3.2 Four technical lemmas

The Local Restriction Lemma partitions a chain into vertex-local pieces while preserving the boundary locally around each vertex.For vertices outside the chain boundary, the local restriction is the join of the vertex with the restricted boundary.Source: §3.2 · pp. 13–14, Figure 5 · p. 13
The Colorable Filling Lemma guarantees a filling of a boundary using only a specified color set that contains the boundary’s colors and has more than n + 1 colors.The proof constructs such a filling through restrictions to colorable-ball boundaries.Source: §3.2 · p. 15
The Colorable Cycles Lemma gives a homologous cycle with any chosen set of n + 1 colors, while the Colorable Link Lemma represents a suitably colored boundary as a sum of links.For the link lemma, the boundary has n + 1 colors and the resulting chain uses the complementary colors.Source: §3.2 · p. 16

3.3 Restricted lattices

The restricted lattice LC uses cells from simplices in a chosen color set and adds (k + 1)-cells identified with links of simplices in the complementary colors.The construction preserves the k-cycles and k-boundaries relevant to the toric-code logical subspace.Source: §3.3 · pp. 17–18
Theorem 1 states that the kth homology groups of LC and the original colex L are isomorphic.The proof decomposes cycles using the Colorable Cycles Lemma and relates the resulting boundaries to cells of LC.Source: §3.3 · p. 18

4 Decoding the color code in d ≥2 dimensions

The Restriction Decoder reduces d-dimensional color-code decoding to toric-code decoding, using a chain-complex morphism and local lifting. Its correctness and threshold estimates are tied to decoding on the corresponding restricted lattices.

4.1 Morphism between color and toric code chain complexes

The restriction map is a morphism between the color-code and toric-code chain complexes, mapping the former onto a toric code on a restricted lattice.The morphism generalizes the d = 2 result cited in Ref..Source: §4.1 · p. 19, §4 · p. 19

4.2 Logical operators of the color code

A (γ, C)-membrane supports a color-code Z logical operator, which is non-trivial when γ represents a non-trivial homology class.The membrane logical operators form a basis, with the number of logical qubits given by the kth Betti number times the number of color subsets.Source: §4.2 · p. 22

4.3 Restriction Decoder for the color code

The decoder runs toric-code decoding on restricted lattices, combines those corrections, and locally lifts them to a color-code correction.Its complexity is determined by the toric decoder; the lifting can be constant-time when vertex d-stars are uniformly bounded, and the combined decoder is fully local when the toric decoder is fully local.Source: §4.2 · p. 23, §4.3 · p. 24
The output is a valid color-code correction, and it has no logical error if and only if every corresponding restricted-lattice toric decoder succeeds.The construction can use any toric-code decoder.Source: §4.3 · pp. 23, 25

4.4 Estimating the color code threshold from the toric code threshold

The color-code threshold can be estimated from toric-code thresholds on restricted lattices, with the worst-performing toric decoder limiting the estimate.Under bit-flip or phase-flip noise, the effective restricted-lattice noise has the same type and introduces no within-lattice error correlations, though its strength may vary by qubit.Source: §4.4 · p. 26

5 More examples of decoding in 2D and 3D

The section presents practical Restriction Decoder variants for 2D and 3D color codes, including almost-linear-time decoding, decoding without restricted lattices, and a cellular-automaton implementation. It also estimates 3D thresholds from toric-code thresholds and reports a direct 0D-threshold check.

5.1 Almost-linear time decoding of 0D point-like excitations in the color code

Using the UF decoder for 0D excitations gives almost-linear worst-case runtime O(Nα(N)); on the 2D square-octagon color code, the phase-flip threshold with perfect syndrome measurements is 9.8%.The 2-square toric-code UF threshold is 17.7%, which the authors use to estimate the color-code threshold.Source: §5.1 · pp. 26–27

5.2 Decoding the 2D color code without restricted lattices

The simplified 2D decoder uses toric-code decoders on the original lattice for restricted syndromes, then locally lifts their outputs to construct a color-code correction without restricted lattices.The lifting also handles vertices whose colors are outside the corresponding restricted-syndrome pair; the illustrated error and correction together form a stabilizer.Source: §5.2 · p. 27, Figure 10 · p. 28

5.3 Cellular automaton decoder of the 3D color code

For 3D Z-error decoding, the simplified decoder applies Sweep Decoding to three restricted syndromes and locally lifts the outputs; the procedure can be implemented as a fully local cellular automaton.It operates on the original lattice rather than three restricted lattices.Source: §5.3 · p. 29

5.4 Numerical estimates of the 3D color code threshold from the 3D toric code threshold

For 3D point-like excitations, the paper estimates the bcc color-code threshold from toric-code thresholds on cubic and diamond-cubic lattices; for loop-like excitations, it uses the Sweep Decoder threshold on the 3^4 bcc lattice.The loop-like case reports a 22.75% toric-code Sweep Decoder threshold, while the excerpt does not give the resulting color-code threshold.Source: §5.4 · pp. 29, 31
0.77% is the directly implemented Restriction Decoder threshold for 0D point-like excitations on the 3D bcc color code, versus 0.46% for a clustering decoder estimated on a different lattice.The direct estimate agrees with the toric-threshold-based estimate.Source: §5.4 · pp. 29, 31

6 Discussion

The Restriction Decoder links color-code correction to toric-code decoding, and its 2D threshold is on a par with leading toric-code thresholds. The reported estimates assume perfect syndrome extraction, while colorability and measurement errors mark directions for further work.

6 Discussion

The Restriction Decoder corrects color-code errors if and only if the corresponding toric-code decoding succeeds, so its performance depends on the selected restricted-lattice toric decoders.For d ≥ 3, using the Sweep Decoder as the toric-code decoder permits a cellular-automaton implementation.Source: §6 · p. 32
10.2% is the estimated 2D color-code threshold, on a par with 9.9–10.3% for leading efficient toric-code decoders and 10.9% for optimal 2D color-code decoding.The estimate assumes perfect syndrome extraction.Source: §6 · p. 32
For 3D point-like excitations on the bcc lattice, the estimated threshold is 13.1%, compared with an optimal decoding threshold of 27.6%.The paper also estimates thresholds for 1D loop-like excitations, but the supplied passages give no value for them.Source: §6 · p. 32
The authors suggest that exploiting lattice colorability in the Sweep Rule could yield native cellular-automaton color-code decoders with thresholds above their estimates.They identify colorability as both a source of decoding complexity and a structure that may support other decoders.Source: §6 · p. 32
The discussion assumes perfect syndrome extraction; point-like excitations with measurement errors require multiple syndrome rounds to determine a correction.For loop-like or higher-dimensional excitations, the authors expect a Restriction Decoder using the Greedy Sweep Decoder and local, possibly faulty, syndrome information.Source: §6 · p. 32