{"id":"9f2c5ea0-f85d-4871-8e96-249184b4d5b2","arxiv_id":"2506.14745","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A new linear-time decoder, UIUF, exploits correlations between X and Z errors in surface and toric codes, guaranteeing correction of errors up to half the code distance and outperforming standard Union-Find and MWPM decoders in simulations.","lead":"This paper introduces a new decoder, Union-Intersection Union-Find (UIUF), for correcting quantum errors on topological codes. It claims to outperform existing decoders like Minimum Weight Perfect Matching in some settings while running in linear time.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 8 proof substitutes a diameter bound for Lemma 6's erasure-count condition and asserts the intersection-cluster diameter bound without proof.","rationale":"The reader's weakest assumption identifies exactly the two places where the proof of Theorem 8 is under-specified: the intersection-cluster diameter bound in Section IV-A and the application of Lemma 6 to an erasure set controlled only by diameter rather than by cardinality. My stress-test agrees with that assessment. The proof of Theorem 8 is the central theoretical contribution of the paper; if it is not valid, the claim that UIUF 'ensures error correction up to half the code distance' is unsupported. The numerical results are extensive and the algorithmic idea is plausible, but simulation at a few error rates does not verify a worst-case distance guarantee. I do not see a basis for moving the verdict to REJECT without a concrete counterexample, and the reader's CONDITIONAL verdict already requires the missing proof. Therefore the verdict should remain UNCHANGED: conditional acceptance pending a rigorous proof of the diameter bound and a generalized lemma that justifies applying UF to the enlarged erasure set.","tokens_in":18743,"tokens_out":11116,"duration_ms":134008,"concrete_test":"Implement Algorithm 2 exactly and exhaustively enumerate all Pauli errors of weight at most floor((d-1)/2) on a small code, e.g., the [[25,1,5]] rotated surface code (2775 errors of weight at most 2), and separately enumerate small r erasure patterns with r+2t<d. If any such error is misdecoded, Theorem 8 is false. If all are corrected, the concern reduces to a proof gap, and the authors should supply a rigorous diameter-based erasure-decoding lemma generalizing Lemma 6 before the distance guarantee is claimed.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section IV-A's proof of Theorem 8 does not establish the distance guarantee. Lemma 6 guarantees correction when r+2t<d, where r is the number of actual erasure qubits. Algorithm 2 adds to the erasure set every qubit in the intersection I of the GX and GZ clusters, and the proof never upper-bounds |I|. It only claims a diameter bound: diam(I) ≤ min{2s+2q, 2t−2s}+r. Even if that bound were true, Lemma 6 gives no license to replace erasure count by erasure-set diameter. A correct argument would need a separate lemma stating that a bounded-diameter erasure region containing no logical operator, together with t residual errors, is correctable by UF peeling. Moreover, the diameter claim itself is asserted without proof: a component of I can be connected by alternating X-check and Z-check adjacencies, so it need not lie inside one GX cluster or one GZ cluster; the bound min(diam LZ, diam LX) is therefore not immediate. Equations (2) and (3) bound a quantity whose relevance to Lemma 6 is not established. The simulations do not fill this gap because they do not exhaustively test all weight-t errors.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes the Union-Intersection Union-Find (UIUF) decoder for CSS topological codes, which uses the intersection of syndrome-validation clusters in the X and Z decoding graphs as an erasure set before running two UF decoding steps. The authors claim that UIUF corrects all errors of weight up to half the code distance while retaining O(n) time complexity, and they support this with extensive simulations under code-capacity, phenomenological, and biased noise models, reporting logical error rates below UF and, on rotated surface codes, below MWPM, as well as threshold estimates.","tokens_in":18968,"tokens_out":12906,"duration_ms":123435,"significance":"If the distance guarantee of Theorem 8 is valid, UIUF is a valuable practical decoder: it offers an order-of-magnitude improvement in logical error rate over UF in the low-error regime, a provable worst-case linear-time complexity, and a parameter-free algorithm with no fitted constants. The simulation study is broad (four code families, three noise models, runtime benchmarks) and the comparisons with standard UF and PyMatching-based MWPM are informative. However, the central theoretical contribution is Theorem 8, and the correctness of its proof is essential to the paper's claims. The manuscript's proof of Theorem 8 has significant gaps, detailed below; the numerical results alone cannot establish the claimed distance guarantee. With a complete proof, this would be a strong contribution; in its current form, the main theoretical claim is not rigorously supported.","major_comments":[{"comment":"The proof asserts without proof that the set I of qubits covered by both an LX cluster and an LZ cluster has connected components of diameter at most min{2s+2q, 2t−2s}+r. A connected component of I may be formed by qubits whose GX-edges belong to one cluster while their GZ-edges belong to several different clusters (and vice versa); it need not be contained in any single GX or GZ cluster. The manuscript does not provide a bound for such alternating components, so the inequalities in Eqs. (2) and (3) are not justified.","section":"§IV-A, proof of Theorem 8"},{"comment":"Lemma 6 is stated for r erasure qubits, i.e., an erasure count, not for an erasure set of bounded diameter. The proof of Theorem 8 substitutes a claimed diameter bound for the erasure count and then invokes Lemma 6 without deriving a separate statement that a UF decoder corrects t errors when the erasure set has diameter D and D+2t<d. Such a lemma is plausible and may follow from the methods of [13], but it is not stated or proved, so the logical step from diameter to correction is missing.","section":"§IV-A, invocation of Lemma 6"},{"comment":"The sentence 'Note that the Y errors are now covered by erasures' is central to the proof, but no argument is given that every Y error's edges are always contained in the final LX and LZ clusters. If a Y error lies outside either cluster, the remaining error counts in the subsequent UF subroutines exceed s or t−s−q, and the diameter bounds (2) and (3) no longer apply. The proof needs an explicit argument that the syndrome-validation clusters cover the support of every Y error.","section":"§IV-A, coverage of Y errors"}],"minor_comments":[{"comment":"The word 'deomposed' should be 'decomposed'.","section":"§II-B"},{"comment":"The phrase 'Then we introduced the UIUF decoder' should be 'Then we introduce the UIUF decoder'.","section":"§I"},{"comment":"The abstract claims that UIUF achieves lower logical error rates than MWPM on rotated surface codes under both noise models without qualification; in Figures 13 and 14, MWPM performs better for small distances (d=3,5) and, in the phenomenological model, for d=13 above ϵ=0.03. The abstract should state the regime where UIUF is superior.","section":"Abstract and §V-C"},{"comment":"The caption says 'total errors' but it is unclear what set of errors is counted; please clarify whether these are all weight-(t+1) Pauli errors and specify the counting convention.","section":"Table II"},{"comment":"The term 'diameter' is used throughout the proof of Theorem 8 but never formally defined; please specify the graph metric (decoding graph or lattice) and whether it applies to vertices or edges of the clusters and erasure sets.","section":"§IV-A"},{"comment":"The notation for the iteration limit is inconsistent: 'iter max' in Algorithm 1, 'itermax' in Figures 8 and the text. Please unify.","section":"Algorithm 1 and Figure 8"}],"recommendation":"major_revision","confidential_remarks":"The main concern is the unproven intersection-cluster diameter bound in Theorem 8. If the authors cannot provide a rigorous proof or modify the algorithm to make the bound true, the distance guarantee claim must be withdrawn; the paper would then be a purely numerical study of a heuristic decoder, which is still of some interest but less significant. I would ask the editor to insist on a complete proof before acceptance."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The intersection-of-clusters idea is new and worth engaging with: take the syndrome-validation clusters from the X and Z decoding graphs, mark the qubits at the intersection as erasures, and rerun UF on both graphs. That is a simple, plausible way to exploit X/Z correlations without iterating, and the simulation work is extensive—toric, rotated toric, surface, and rotated surface codes; code-capacity, phenomenological, and biased noise; thresholds from finite-size scaling; comparison against PyMatching MWPM. The reported order-of-magnitude improvement over UF at low error rates, and beating MWPM on rotated surface codes, looks credible from the figures. The time-complexity claim (roughly 1.5x UF) is also supported by the runtime plots.\n\nThe soft spot is Theorem 8. The proof as written does not establish the distance guarantee. Lemma 6 guarantees correction when r+2t<d, where r is the number of actual erasure qubits. After the intersection step, Algorithm 2 adds every qubit in the intersection of the X and Z clusters to the erasure set, and the proof never bounds the number of qubits added. Instead it asserts a diameter bound for the intersection set and then invokes Lemma 6. But Lemma 6 has no diameter-based version; you would need a separate lemma stating that a bounded-diameter erasure region, containing no logical operator and combined with t residual errors, is correctable by UF peeling. Moreover, the diameter claim itself is stated without proof: a component of the intersection can be connected by alternating X-check and Z-check adjacencies, so it need not be contained in a single GX or GZ cluster. Equations (2) and (3) bound a quantity whose connection to Lemma 6 is not established. The simulations do not fill the gap because they are not exhaustive over weight-(t+1) errors.\n\nI think this is a repairable flaw rather than a demolished central claim. The algorithm's performance is plausible independent of the proof, and the half-distance guarantee may well hold with a more careful argument. But as submitted, the proof is not rigorous, and I would not cite the guarantee in my own work until it is fixed. The citation pattern is fine—the prior X/Z-correlation work is acknowledged, and the load-bearing dependencies are external UF and peeling results, not self-citations.\n\nFor peer review: yes, send it to referees. The idea and the simulation evidence deserve serious scrutiny, but acceptance should require a complete proof of Theorem 8, ideally with code or data for the simulations. I would bring it to a reading group to work through the proof gap, but I would not present it as a decoder with a proven distance guarantee.","headline":"A genuinely new UF variant with strong simulations, but the half-distance proof has a load-bearing gap: diameter is substituted for erasure count, and the diameter bound itself is asserted, not proved.","tokens_in":19474,"tokens_out":2269,"would_cite":false,"duration_ms":26020,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["81P70","81P68"],"pacs":["03.67.Pp","03.67.Lx"],"model":"deepseek-v4-flash","headline":"UIUF provably corrects depolarizing errors on toric and surface codes up to half the code distance in linear time, and outperforms MWPM on rotated surface codes in simulations.","keywords":["quantum error correction","Union-Find decoder","depolarizing errors","topological codes","surface codes","X/Z correlation","erasure decoding","linear-time decoding"],"falsifier":"Enumerate all Pauli errors of weight $\\lfloor (d-1)/2\\rfloor$ on a small code where the bound matters, such as the [[25,1,4]] surface code or the [[72,2,6]] toric code, and run UIUF on each syndrome; a single logical failure would disprove Theorem 8. To isolate the proof's weak step, construct two valid clusters, one in $G_X$ and one in $G_Z$, whose intersection as edge sets has diameter strictly larger than the smaller of the two cluster diameters; that would contradict the diameter claim used to derive the inequalities in the proof.","tokens_in":18537,"feed_emoji":"⚛️","tokens_out":14053,"duration_ms":119764,"temperature":0.7,"pith_summary":"The paper introduces the Union-Intersection Union-Find (UIUF) decoder for depolarizing errors in toric and surface codes. Its aim is to combine the standard Union-Find decoder's proven half-distance guarantee with the better practical performance of iterative Union-Find decoders. UIUF first runs syndrome validation separately on the X and Z decoding graphs, then marks any qubit whose edge is covered by a cluster in both graphs as an erasure, and finally reruns Union-Find with these extra erasures. The paper proves that the decoder corrects r erasure errors plus an additional Pauli error of weight t whenever $r+2t<d$, hence every error of weight at most $\\lfloor (d-1)/2\\rfloor$, and simulations under code-capacity, phenomenological, and biased noise show a logical error rate reduction of over an order of magnitude near $10^{-5}$ compared with Union-Find, along with lower logical error rates than Minimum Weight Perfect Matching on rotated surface codes, all in $O(n)$ time.","feed_headline":"Union-Find variant corrects errors up to half the code distance","feed_subtitle":"UIUF uses X/Z cluster intersections to catch correlated Y errors while keeping standard Union-Find's provable guarantee.","key_machinery":"The load-bearing object is the cluster produced by syndrome validation: a connected component of check nodes in a decoding graph, grown until it is consistent with some error matching the observed syndrome. The new mechanism is the intersection step, in which a qubit is added to the erasure set whenever the edge it represents in $G_X$ lies inside a cluster of $L_X$ and the corresponding edge in $G_Z$ lies inside a cluster of $L_Z$. This converts likely Y-error locations into known erasures before the final Union-Find calls, which is how the decoder uses X/Z correlations without iterating. The proof then uses cluster-diameter bounds, at most $2t+r$ for a Pauli error of weight $t$ with $r$ erasures, to show the enlarged erasure set still satisfies the erasure-plus-error condition of the standard Union-Find guarantee, so Lemma 6 applies.","core_discovery":"The central discovery, stated on the paper's own terms, is that a non-iterative decoder can exploit X/Z correlations and still keep a distance guarantee. The UIUF procedure is: syndrome-validation on each decoding graph produces a collection of valid clusters; the intersection step marks a qubit as an erasure exactly when the edges it represents in $G_X$ and $G_Z$ are both covered by their respective clusters; two ordinary Union-Find calls then produce the corrections using the enlarged erasure set. Because a Y error contributes to both decoding graphs, its position tends to be covered by both clusters and is thereby turned into a known erasure, which makes the remaining X and Z subproblems easier. Theorem 8 states that on a distance-$d$ toric or surface code, UIUF corrects up to r erasure errors plus a Pauli error of weight t on the remaining qubits whenever $r+2t<d$; in particular it corrects all errors of weight at most $\\lfloor (d-1)/2\\rfloor$. The complexity remains $O(n)$, and the proof works by bounding the diameter of the intersection erasure set by the smaller of the two cluster diameters plus $r$, which reduces the required condition to the same $r+2t<d$ as the standard Union-Find guarantee.","pith_inferences":["The diameter-based structure of the proof suggests the guarantee likely transfers to other bounded-degree CSS topological codes whose decoding graphs obey the same cluster-diameter bound, so UIUF is a natural candidate for other lattice geometries.","The intersection erasure set could be exported as a preprocessing step for other decoders such as reweighted MWPM or belief propagation; one could test whether marking the same qubits as erasures improves their low-error-rate performance without iteration.","Because UIUF's advantage over MWPM concentrates at low error rates and larger distances, a practical decoder might use UIUF's fast clustering for most shots and invoke a more expensive decoder only when the intersection step produces an unusually large or ambiguous erasure set."],"forward_implications":["UIUF corrects every error of weight at most $\\lfloor (d-1)/2\\rfloor$ on a distance-$d$ toric or surface code, giving it the same half-distance guarantee as the standard Union-Find decoder.","The guarantee is stated for the mixed setting of $r$ erasures plus $t$ Pauli errors with $r+2t<d$, so the decoder also applies directly to erasure-assisted decoding problems.","The decoder keeps $O(n)$ worst-case complexity, with measured average runtime about 1.53 times that of Union-Find, so the performance gain does not sacrifice linear-time decoding.","On rotated surface codes, UIUF with weighted growth achieves lower logical error rates than MWPM for distance at least 7 under both code-capacity and phenomenological noise, even where its phenomenological threshold is lower than MWPM's.","Under biased noise with $p_Y=p_X$, UIUF's advantage over Union-Find persists for bias ratios below 100 and disappears above about 1000."],"supporting_citations":[{"why":"Defines the standard Union-Find decoder and its Lemma 6 distance guarantee that UIUF invokes for its final decoding steps.","marker":"[13]"},{"why":"Introduces the peeling decoder and the erasure-correction lemma underlying both Union-Find and UIUF.","marker":"[12]"},{"why":"Establishes that exploiting X/Z correlations can improve decoding of CSS codes under depolarizing noise, the premise of the intersection step.","marker":"[23]"},{"why":"Shows that reweighting the decoding graph with X/Z information improves MWPM, the approach UIUF adapts to the Union-Find setting.","marker":"[31]"},{"why":"Provides the MWPM threshold near 15.5 percent that the paper compares UIUF's code-capacity thresholds against.","marker":"[39]"},{"why":"Supplies the high-performance minimum-weight matching implementation used as the MWPM baseline in simulations.","marker":"[21]"},{"why":"Supports the claim that Union-Find decoding has worst-case linear complexity, which UIUF inherits.","marker":"[17]"}],"fun_headline_variants":["UIUF decoder: distance-half guarantee in linear time","Linear-time decoding with half-distance correction","Topological code decoder beats MWPM, keeps guarantee","UIUF: proven correction up to half code distance","X/Z intersection decoder guarantees half-distance"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof of Theorem 8 rests on the asserted, not separately proved, bound that the erasure set formed by intersecting an X-cluster and a Z-cluster has diameter no larger than the smaller of the two cluster diameters; if that diameter bound gives way, the half-distance guarantee does not follow.","fun_headline_variants_meta":{"raw":{"variants":["UIUF decoder: distance-half guarantee in linear time","Linear-time decoding with half-distance correction","Topological code decoder beats MWPM, keeps guarantee","UIUF: proven correction up to half code distance","X/Z intersection decoder guarantees half-distance"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000194,"raw_usage":{"total_tokens":1364,"prompt_tokens":963,"completion_tokens":401,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":579,"completion_tokens_details":{"reasoning_tokens":331}},"tokens_in":579,"tokens_out":401,"duration_ms":4275,"temperature":1.0,"reasoning_tokens":331,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T19:48:34.433099+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Enumerate all Pauli errors of weight $\\lfloor (d-1)/2\\rfloor$ on a small code where the bound matters, such as the [[25,1,4]] surface code or the [[72,2,6]] toric code, and run UIUF on each syndrome; a single logical failure would disprove Theorem 8. To isolate the proof's weak step, construct two valid clusters, one in $G_X$ and one in $G_Z$, whose intersection as edge sets has diameter strictly larger than the smaller of the two cluster diameters; that would contradict the diameter claim used to derive the inequalities in the proof.","supporting_citations":[{"cited_title":"Almost-linear time decoding algo- rithm for topological codes,","cited_arxiv_id":null,"evidence_quote":"Defines the standard Union-Find decoder and its Lemma 6 distance guarantee that UIUF invokes for its final decoding steps."},{"cited_title":"Linear-time maximum likelihood decoding of surface codes over the quantum erasure channel,","cited_arxiv_id":null,"evidence_quote":"Introduces the peeling decoder and the erasure-correction lemma underlying both Union-Find and UIUF."},{"cited_title":"A decoding algorithm for CSS codes using the X/Z correlations,","cited_arxiv_id":null,"evidence_quote":"Establishes that exploiting X/Z correlations can improve decoding of CSS codes under depolarizing noise, the premise of the intersection step."},{"cited_title":"Threshold error rates for the toric and planar codes,","cited_arxiv_id":null,"evidence_quote":"Provides the MWPM threshold near 15.5 percent that the paper compares UIUF's code-capacity thresholds against."},{"cited_title":"Union-find quantum decoding without union-find,","cited_arxiv_id":null,"evidence_quote":"Supports the claim that Union-Find decoding has worst-case linear complexity, which UIUF inherits."}],"review_version":2}