Union-Find Decoders For Homological Product Codes

Matthew B. Hastings; Nicolas Delfosse

REVIEW 3 major objections 4 minor 18 references

Union-Find Decoders For Homological Product Codes

T0 review · 3 major / 4 minor · reviewed 2026-08-27 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper shows that homological product codes can be decoded efficiently whenever one factor admits a union-find decoder and the other is small enough for brute-force lookup, and that for surface codes augmented by a small code the…

desk verdict Genuinely useful decoder construction, but the half-distance proof has a real gap that needs fixing before the main claim is trusted. read the letter →

arxiv 2009.14226 v2 pith:4FJNYWXC submitted 2020-09-29 quant-ph

Nicolas Delfosse , Matthew B. Hastings This is my paper · ORCID

classification quant-ph PACS 03.67.Pp

keywords homologicalproductcodesunion-finddecodersurfaceaugmentedquantumerrorcorrectionlow-densityparity-checkcodedistancefault-tolerantcomputation

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper establishes that homological product codes—quantum codes built by multiplying the chain complexes of two smaller CSS codes—can be decoded efficiently whenever one factor admits a union-find decoder and the other is small enough to decode by exhaustive lookup. Applied to the product of a surface code with a tiny code such as the [[4,2,2]] code, called an augmented surface code, the resulting decoder runs in almost-linear time and, with a modified growth rule, corrects any error of weight less than half the code's distance. The distance of these augmented codes is proven to be the product of the two factor distances, so the construction converts a fixed-distance surface code into a larger-distance code at reduced qubit overhead. Numerical simulations show that although the pseudo-threshold is lower than the plain surface code, the logical error rate in the low-noise regime is better, making the tradeoff attractive for fault-tolerant architectures.

What carries the argument

The central object is the homological product chain complex $A = B \otimes C$, whose cells are tensor products of cells of the large complex $B$ and the fixed complex $C$. The load-bearing mechanism is the cluster-validity test: a cluster $M \otimes \tilde{C}$ is valid exactly when the observed syndrome $v$ satisfies $\partial v = 0$ and each partial inner product $\tilde{v}_j = (v, x_j)$ is a boundary in $M$, where the $x_j$ are representatives of the logical $X$ operators of $\tilde{C}$. This reduces a decoding problem in the product code to repeated calls to the large code's union-find decoder and to small linear-algebra lookups, which is what makes the whole construction (near-)linear time when the large code is a surface code.

What would settle it

Enumerate all Z-error patterns of weight less than half the product distance for a small augmented surface code, e.g., the product of a distance-3 toric code with the [[4,2,2]] code, and run the paper's decoder (Algorithm 1 or the modified growth version) on each: any mis-correction of a sub-half-distance error would refute the half-distance claim. Alternatively, test the distance-equals-product theorem on a topological large code with boundaries; a counterexample would show the distance claim depends on boundary conditions.

Watch

Extended reading notes

Core claim

The central discovery is a general reduction: to decode the homological product of a large code B and a fixed-size code C, it suffices to combine a union-find decoder for B with a brute-force decoder for C. The paper proves the existence of a cluster-validity test and a cluster-decoding routine for product complexes, based on the Kunneth formula and on the assumption that C has no redundant stabilizers, so that a syndrome on a product subcomplex is a boundary exactly when it is closed and its partial inner products with the logical operators of C are boundaries in the large code. For the specific augmented surface code—surface code times [[4,2,2]]—the decoder is spelled out in detail: it cancels edge syndromes, grows and validates clusters via a validity vector, then uses peeling and a final local lookup to output a correction. The authors prove that for fixed-code distance 2 the simple decoder corrects all errors below half the distance, and that a subedge-growth modification extends this guarantee to arbitrary fixed-code distance, while a separate distance theorem shows the product distance equals the product of the distances for topological large codes such as toric codes.

Load-bearing premise

The small fixed code must have no redundant stabilizer generators and trivial zeroth and second homology, so that the cluster-validity test is exact and the code's logical-qubit count factors; if that condition fails, the decoder's validity criterion and the distance product formula can break.

Editorial extensions

If this is right

Any surface code can be promoted to a code with distance multiplied by that of a small fixed code, while keeping stabilizer weight bounded by a constant, and the resulting augmented surface code is decodable in almost-linear time.
The same construction applies to any large LDPC code that already has a union-find decoder; the product with an O(1)-size fixed code inherits an efficient decoder, as long as the fixed code has no redundant checks.
For error rates below the crossover point, augmented surface codes achieve a lower logical error rate than plain surface codes with the same or lower qubit overhead, because the increased minimum distance more than compensates for the lower threshold.
The half-distance guarantee gives a rigorous performance bound for the decoder that is independent of the specific noise model, matching the standard guarantee for the surface-code union-find decoder.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

If the distance-equals-product theorem extends to topological codes with boundaries, the construction would directly improve the parameters of planar surface-code patches, the building blocks of many fault-tolerance protocols; the paper explicitly leaves this boundary case open.
The validity test suggests a general recipe: any pair of decoders that can recognize when a syndrome is a boundary in a subcomplex could be composed along a homological product, so the result may transfer to decoders other than union-find, such as belief-propagation-based decoders, whenever they can certify boundary membership.
A practical extension would be to choose the subcomplex $\tilde{C}$ adaptively during growth (the paper notes this is possible for larger fixed codes); optimizing that choice could raise the pseudo-threshold while preserving the half-distance guarantee.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Request a human review

A listed scientist reviews the paper for a fee and the review publishes here regardless of verdict. See the reviewers or get listed.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Candid take on 2009.14226: the decoder construction is new and the distance equality part is solid, but the proof of the half-distance guarantee (Lemma 1) has a load-bearing step that is asserted rather than proved. I would not block peer review, but the authors need to repair that proof.

What's genuinely good: combining a union-find decoder on one factor with a brute-force decoder on a fixed-size factor is a clean idea, and the general validation test in Section 3 (Lemma 2) is a real contribution. The distance equality result for topological large codes (Section 4) appears correct and is independently useful. The numerical study is honest about the tradeoff: pseudo-thresholds are worse, but low-noise logical error rates improve at comparable overhead. The paper is clearly written and the assumptions are stated.

The soft spots: the proof of Lemma 1 relies on the claim that an invalid cluster must have an edge in H leaving it. That converts a syndrome-level validity test into a geometric statement about hidden edges, and no proof is given. For d>2, the modified algorithm is described only inside the proof and is not the algorithm used in the numerical section, so the 'slight modifications' claim is not backed by simulation or by a careful correspondence between the subedge model and the actual half-edge growth. The d>2 argument also depends on subedges that are not the qubits on an edge, and the c(e) closest subedges are not shown to relate to logical operator weight on that edge. The no-redundancy assumption is explicit and is satisfied by [[4,2,2]], so that is not the limiting step; Lemma 1 is. The numerics lack error bars and released data, which is minor but worth mentioning.

Who this is for: people working on decoders for product codes and on low-overhead surface-code variants. The construction will likely be useful even if the half-distance proof needs reworking. The distance result alone is worth citing.

Recommendation: send to peer review, but with a required major revision on the proof of Lemma 1. The paper deserves careful refereeing, not a desk rejection.

Referee Report

3 major / 4 minor

Summary. This paper proposes a general construction of union-find decoders for homological product codes, combining a union-find decoder for the 'large' factor code with a brute-force decoder for an O(1)-size 'fixed' factor code. The main application is to augmented surface codes, i.e. homological products of a surface code with a small code such as the [[4,2,2]] code. The authors prove in Section 4 that, under certain assumptions, the distance of the product equals the product of the distances, and they give a general syndrome-validation and decoding procedure in Section 3. The central theoretical claim is Lemma 1 (Section 2.4): the union-find decoder, with a modification for fixed codes of distance larger than 2, corrects all errors of weight less than half the distance of the augmented surface code. Numerical simulations of augmented toric codes indicate that these codes have lower pseudo-thresholds than plain toric codes but achieve lower logical error rates at low physical error rates for comparable qubit overhead.

Significance. If the half-distance claim is correct, the paper makes a meaningful algorithmic contribution: it gives an almost-linear-time decoder for a family of homological product codes with improved distance and reduced qubit overhead, and it extends the union-find paradigm beyond topological codes. The general validation and decoding routines in Section 3 are a useful framework, and the distance product theorem in Section 4 is a clean result with explicit assumptions. The pseudocode for Algorithms 1 and 2 is concrete enough to reproduce, and the numerical study is honest about the pseudo-threshold tradeoff; in particular, no parameter fitting to data is performed. The main caveat is that the central decoding guarantee rests on Lemma 1, whose proof currently contains a load-bearing gap. The contribution is therefore conditional on repairing or appropriately weakening that argument.

major comments (3)

[Section 2.4, Lemma 1] The proof's key step, 'If a cluster is not valid, then there must be some edge in H leaving the cluster', is asserted without proof. In Algorithm 1, after edge cancellation the syndrome information on vertices is s(v), and validity of a cluster is defined by the validity vector val(κ) in Eq. (4). The proof must show that a nontrivial validity vector forces the existence of a hidden edge crossing the cluster boundary, and that one growth step reduces the hidden weight by at least one. This is exactly the fact that connects the algebraic validity test to the geometric growth process; without it, the bounds t ≤ w − m and t ≤ h0, and hence the final half-distance conclusion, are not established.
[Section 2.4, d > 2 case] The subedge model is introduced without a demonstrated correspondence to the actual qubits on an edge. The fixed code has n_C qubits and distance d, and after edge cancellation the residual error on an edge is a vector in C_1, not a set of d subedges. The quantities c(e), h(e), and the 'closest subedges' are defined by correction weight, but the proof never shows that a nontrivial logical operator on an edge has weight related to h(e), nor that growth on subedges correctly refines the cluster-validity test. Consequently the final bound (2/d)w is not shown to be a bound on anything in the original error model.
[Section 2.4, final paragraph] The conclusion 'If w is smaller than the surface code distance, it decodes correctly' does not follow from the preceding diameter bound. On an L-by-L toric code, a noncontractible logical operator such as a vertical loop has weight L but graph diameter floor(L/2); hence a support set of diameter less than L can contain a nontrivial logical operator. The argument needs a bound on the number of edges or qubits in the union of clusters and paths, not merely on diameters, or it needs a different argument showing that the residual operator is trivial.

minor comments (4)

[Appendix A, Algorithm 2, line 11] The while condition reads 'val_i(κ) ≠ 1', but the text correctly defines a cluster to be valid when val_i(κ) = 0; the pseudocode condition should presumably be 'val_i(κ) ≠ 0'.
[Introduction and Section 3.1] The introduction states that Section 3 treats fixed codes with redundancies in their stabilizers, but Section 3.1 explicitly assumes that the fixed code has no redundancies; these statements should be aligned.
[Figures 2 and 3] The numerical plots do not report the number of Monte Carlo samples or confidence intervals; adding this information would make the performance comparison easier to evaluate.
[Throughout] There are several typographical issues, including 'On can erase' in Section 2, 'in in Section 3' in the introduction, and 'has this this property' in Section 4; these should be corrected.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the decoder construction is compositional, the half-distance argument is an independent mathematical proof, and the cited self-papers are independent prior work.

full rationale

The paper's central construction reduces the decoding problem for a homological product code to a union-find decoder for the large code plus a brute-force decoder for the fixed code (Section 2.2 and Section 3). This is a compositional reduction, not a circular one: the validity test in Eq. (4) is derived from the Kunneth decomposition and from the logical operators of the fixed code, and Lemma 2 proves the correctness of that test under explicit assumptions on the subcomplex. The decode routine in Section 3.2 similarly uses the large-code decoder as a subroutine, and the proof is conditional on that subroutine's correctness, which is a legitimate reduction rather than an import of the target result. The half-distance claim in Lemma 1 is an independent mathematical argument that uses the fixed code's distance and the minimum-weight property of its decoder; even if the 'hidden edge' assertion in that proof is not fully justified in the text, that is a proof gap or correctness risk, not a circularity. No parameter is fitted to data and then renamed as a prediction: the numerical simulations compare the augmented toric code against independently simulated toric codes with no fitted constants. Self-citations, including [2], [11], and [17], are to independently published prior work: [11] supplies the known union-find surface-code decoder and a proof template, [17] supplies the standard peeling decoder, and [2] is used for background and for the known example that the distance bound is not always tight. None of these citations is invoked as an unverified premise that would force the paper's conclusion. The derivation chain is therefore self-contained in the sense relevant to circularity analysis.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

The central claim rests on a structural condition on the fixed code (no redundant checks, trivial zeroth and second homology), standard algebraic topology facts, and the existence of a union-find decoder for the large code. No free parameters are fitted to data; the decoder is deterministic and the simulations use physical error rate as an input.

assumptions (3)

domain assumption The fixed code C has no redundant checks and trivial zeroth and second homology, so nX+nZ+kC = nC.
Invoked in Section 1.2 to compute the number of logical qubits via the Kunneth formula and in Section 3.1 to ensure the validity test (Lemma 2) is exact; it restricts the class of codes the decoder applies to.
standard math Kunneth formula and universal coefficient theorem for Z2 chain complexes.
Used in Section 3.1 (Lemma 2 proof) to relate boundaries in the product complex to boundaries in the factors, and in Section 4 for the distance bound.
domain assumption The large code has a union-find decoder that can decide whether a syndrome vector is a boundary on any subcomplex.
The construction is an oracle reduction: it builds a decoder for the product assuming one for the large code. For the surface code case this holds by the known union-find decoder.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Union-Find Decoders For Homological Product Codes." pith.science (2026). https://pith.science/paper/4FJNYWXC

@misc{pith2026200914226,
  author       = {Pith},
  title        = {Pith review of: Union-Find Decoders For Homological Product Codes},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/4FJNYWXC}},
  note         = {Machine review of arXiv:2009.14226}
}

abstract

Homological product codes are a class of codes that can have improved distance while retaining relatively low stabilizer weight. We show how to build union-find decoders for these codes, using a union-find decoder for one of the codes in the product and a brute force decoder for the other code. We apply this construction to the specific case of the product of a surface code with a small code such as a $[[4,2,2]]$ code, which we call an augmented surface code. The distance of the augmented surface code is the product of the distance of the surface code with that of the small code, and the union-find decoder, with slight modifications, can decode errors up to half the distance. We present numerical simulations, showing that while the threshold of these augmented codes is lower than that of the surface code, the low noise performance is improved.

Figures

Figures reproduced from arXiv: 2009.14226 by the authors.

**Figure 2.** Qubit overhead n/k as a function of the minimum distance for the toric code and augmented toric code. The toric code reaches d = 30 with 900 physical qubits per logical qubit while the augmented toric code requires only 562.5 physical qubits per logical qubit saving almost 40% of the qubits. procedure. So, for us, the error patterns will be on 2-cells of the product complex and the syndrome of an error will be the s… view at source ↗

**Figure 3.** Comparison of augmented toric codes TC(m) ⊗ [[4, 2, 2]] with toric codes with smaller or equal overhead for m = 3, 4, 5, 6. Toric codes are decoder is the standard union-find decoder and Algorithm 2 is used to decode augmented toric codes. Augmented toric codes achieve a better logical error rate than toric codes in the regime of low physical error rate. The overhead reported in these plots is the number of physical… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

18 extracted references · 18 canonical work pages

[1]

Quantum systems on non-k-hyperﬁnite complexes: A generalization of classical statistical mechanics on expander graphs

Michael H Freedman and Matthew B Hastings. Quantum systems on non-k-hyperﬁnite complexes: A generalization of classical statistical mechanics on expander graphs. QIC, 14:144, 2014

work page 2014
[2]

Homological product codes

Sergey Bravyi and Matthew B Hastings. Homological product codes. In Proceedings of the forty- sixth annual ACM symposium on Theory of computing , pages 273–282, 2014

work page 2014
[3]

Weight reduction for quantum codes

Mathew B Hastings. Weight reduction for quantum codes. Quantum Information & Computation , 17(15-16):1307–1334, 2017

work page 2017
[4]

Decodable quantum LDPC codes beyond the $\sqrt{n}$ distance barrier using high dimensional expanders

Shai Evra, Tali Kaufman, and Gilles Z´ emor. Decodable quantum ldpc codes beyond the √n distance barrier using high dimensional expanders. arXiv preprint arXiv:2004.07935 , 2020

work page Pith review arXiv 2004
[5]

On tensor products of CSS Codes

Benjamin Audoux and Alain Couvreur. On tensor products of css codes. arXiv preprint arXiv:1512.07081, 2015

work page Pith review arXiv 2015
[6]

Quantum ldpc codes with positive rate and minimum distance proportional to the square root of the blocklength

Jean-Pierre Tillich and Gilles Z´ emor. Quantum ldpc codes with positive rate and minimum distance proportional to the square root of the blocklength. IEEE Transactions on Information Theory, 60(2):1193–1202, 2013. doi:10.1109/isit.2009.5205648

work page arXiv 2013
[7]

Quantum expander codes

Anthony Leverrier, Jean-Pierre Tillich, and Gilles Z´ emor. Quantum expander codes. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science , pages 810–824. IEEE, 2015. doi:10.1109/focs.2015.55

work page doi:10.1109/focs.2015.55 2015
[8]

Constant overhead quantum fault- tolerance with quantum expander codes

Omar Fawzi, Antoine Grospellier, and Anthony Leverrier. Constant overhead quantum fault- tolerance with quantum expander codes. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS) . IEEE, oct 2018. URL: https://doi.org/10.1109%2Ffocs.2018. 00076, doi:10.1109/focs.2018.00076

work page arXiv 2018

Show all 18 references

[9]

Degenerate quantum ldpc codes with good ﬁnite length performance

Pavel Panteleev and Gleb Kalachev. Degenerate quantum ldpc codes with good ﬁnite length performance. arXiv preprint arXiv:1904.02703 , 2019

1904 arXiv
[10]

Single-shot error correction of three-dimensional homological product codes

Armanda O Quintavalle, Michael Vasmer, Joschka Roﬀe, and Earl T Campbell. Single-shot error correction of three-dimensional homological product codes. arXiv preprint arXiv:2009.11790 , 2020

2009 arXiv
[11]

Almost-linear time decoding algorithm for topological codes

Nicolas Delfosse and Naomi H Nickerson. Almost-linear time decoding algorithm for topological codes. arXiv preprint arXiv:1709.06218 , 2017

2017 arXiv
[12]

Homological codes and abelian anyons.Reviews in Mathematical Physics, 31(10):1950038, 2019

P´ eter Vrana and M´ at´ e Farkas. Homological codes and abelian anyons.Reviews in Mathematical Physics, 31(10):1950038, 2019. doi:10.1142/s0129055x19500387

2019 doi
[13]

Noise thresholds for the [[4, 2, 2]]-concatenated toric code

Ben Criger and Barbara Terhal. Noise thresholds for the [[4, 2, 2]]-concatenated toric code. arXiv preprint arXiv:1604.04062, 2016. 15

2016 arXiv
[14]

Fault-tolerant quantum computation by anyons

A Yu Kitaev. Fault-tolerant quantum computation by anyons. Annals of Physics , 303(1):2–30,
[15]

Projective plane and planar quantum codes

Michael H Freedman and David A Meyer. Projective plane and planar quantum codes. Founda- tions of Computational Mathematics , 1(3):325–332, 2001. doi:10.1007/s102080010013

2001 doi
[16]

Homological error correction: Classical and quan- tum codes

Hector Bombin and Miguel A Martin-Delgado. Homological error correction: Classical and quan- tum codes. Journal of mathematical physics , 48(5):052105, 2007. doi:10.1063/1.2731356

2007 doi
[17]

Linear-time maximum likelihood decoding of surface codes over the quantum erasure channel

Nicolas Delfosse and Gilles Z´ emor. Linear-time maximum likelihood decoding of surface codes over the quantum erasure channel. Physical Review Research, 2(3):033042, 2020. doi:10.1103/ physrevresearch.2.033042. A Union-Find decoder with modiﬁed growth In this section, we desc...

2020
[2003]

doi:10.1016/s0003-4916(02)00018-0

doi

Pith tools

Reviewed August 27, 2026 · model on record in the stance chip above.

[1] [1]

Quantum systems on non-k-hyperﬁnite complexes: A generalization of classical statistical mechanics on expander graphs

Michael H Freedman and Matthew B Hastings. Quantum systems on non-k-hyperﬁnite complexes: A generalization of classical statistical mechanics on expander graphs. QIC, 14:144, 2014

work page 2014

[2] [2]

Homological product codes

Sergey Bravyi and Matthew B Hastings. Homological product codes. In Proceedings of the forty- sixth annual ACM symposium on Theory of computing , pages 273–282, 2014

work page 2014

[3] [3]

Weight reduction for quantum codes

Mathew B Hastings. Weight reduction for quantum codes. Quantum Information & Computation , 17(15-16):1307–1334, 2017

work page 2017

[4] [4]

Decodable quantum LDPC codes beyond the $\sqrt{n}$ distance barrier using high dimensional expanders

Shai Evra, Tali Kaufman, and Gilles Z´ emor. Decodable quantum ldpc codes beyond the √n distance barrier using high dimensional expanders. arXiv preprint arXiv:2004.07935 , 2020

work page Pith review arXiv 2004

[5] [5]

On tensor products of CSS Codes

Benjamin Audoux and Alain Couvreur. On tensor products of css codes. arXiv preprint arXiv:1512.07081, 2015

work page Pith review arXiv 2015

[6] [6]

Quantum ldpc codes with positive rate and minimum distance proportional to the square root of the blocklength

Jean-Pierre Tillich and Gilles Z´ emor. Quantum ldpc codes with positive rate and minimum distance proportional to the square root of the blocklength. IEEE Transactions on Information Theory, 60(2):1193–1202, 2013. doi:10.1109/isit.2009.5205648

work page arXiv 2013

[7] [7]

Quantum expander codes

Anthony Leverrier, Jean-Pierre Tillich, and Gilles Z´ emor. Quantum expander codes. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science , pages 810–824. IEEE, 2015. doi:10.1109/focs.2015.55

work page doi:10.1109/focs.2015.55 2015

[8] [8]

Constant overhead quantum fault- tolerance with quantum expander codes

Omar Fawzi, Antoine Grospellier, and Anthony Leverrier. Constant overhead quantum fault- tolerance with quantum expander codes. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS) . IEEE, oct 2018. URL: https://doi.org/10.1109%2Ffocs.2018. 00076, doi:10.1109/focs.2018.00076

work page arXiv 2018