Skip to content

[Mac agent] CC engine: redundant sparse checks and XOR unit propagation #181

Open
Open
[Mac agent] CC engine: redundant sparse checks and XOR unit propagation#181

Description

@guluchen
guluchen
opened on Oct 29, 2026

Hub: #15. Baseline: main 6083e662 (CC defaults excl,pack,orbf,parity,leaf,overlap, -cc-aut=on, -ub-search Stern). PR #161 (charge, GH-157) and PR #180 (tiebreak, GH-162) are open and not merged; this round is independent of both (an optional combined run with tiebreak is reported if the merge is easy).

Goal of the round: strengthen the CC node lower bound and add a cheap propagation step, aimed at the TN codes whose pack bound is weak (4-cycles make odd rows share candidates).

Background

At a CC node S (target weight w) every odd row h of the half's parity checks H needs a qubit of e \ S for every extension e in F, because h.e = 0. pack greedily selects odd rows with pairwise disjoint candidate sets; |S| + p > w prunes. Every vector r in the row space of H also satisfies r.e = 0 for every e in ker H, so a redundant row r = h1 + h2 can be used exactly like an original row wherever the argument only needs "r.e = 0 for every e in ker H". Low-weight pair sums give more, smaller odd-row neighbourhoods. A second, independent observation: a row (original or redundant) that is currently even and has exactly one free qubit q left forces q out of every extension (adding q would make the row odd with nothing left to repair it), and an odd row with exactly one free qubit forces that qubit in. Neither step is covered by the current rules (pack looks only at odd rows; leaf only at remaining budget 1-2; overlap only at stabilizer rows).

Proposals

  1. Redundant sparse checks (sparse). Per half, add the distinct pair sums r = h1 + h2 of rows of H with |r| <= max(|h1|, |h2|) (deduplicated against H and each other; deterministic order; a count cap). Use them in pack (after the original odd rows, so the packing can only grow), in mrv branching (branching on an odd redundant row is complete), and in xorunit (below). Not used in the leaf lookup, the parity rule or the syndrome-free test, which keep the original H. Overlap: rows of H are stabilizers of the other type, so H-derived rows are NOT valid overlap rows (that is mutant 9). The valid analogue is a pair sum of two same-type stabilizer rows g1 + g2 (still in ker H with G(g1 + g2) = 0); it may be added to the overlap row set K with its own limit floor(|g1 + g2| / 2), as a separate token (sparseov) with separate counters.
  2. XOR unit propagation (xorunit). At each node, to a fixpoint: an even row with exactly one free qubit forbids that qubit for the subtree; an odd row with exactly one free qubit is branched on first (a single child); an odd row with no free qubit is a dead end. Rows: H, plus the redundant rows when sparse is on. Chains with the overlap forbids (a tight stabilizer row can leave an even row with one free qubit). Soundness follows from H e = 0 alone: every element of F of weight w that extends S and avoids the forbidden set keeps those properties.
  3. Exact edge cover at small degree. When every free qubit meets at most two odd rows, the minimum hitting set is a minimum edge cover (Gallai). Not selected for this round: it overlaps with [Mac agent] CC engine: fractional-charge / edge-cover node lower bounds #157 (charge).

Selection

Proposals 1 and 2 as new -cc-rules tokens sparse, sparseov and xorunit, off by default. With the tokens off, output is byte-identical to the base. -cc-stats reports per-level node counts and the new counters (redundant rows added per half, packing rows contributed by redundant rows, unit forbids, forced branchings, unit conflicts).

Correctness risk: low to medium. The redundant rows must lie in the row space of H (checked at construction: each one is the XOR of two named rows); the unit rule must never fire on an even row as a forcing rule.

Plan

  • Tier 0:
    • byte identity with the tokens off (tier0+1 -v, -engine=cc, plus -no-card / -card-mto);
    • make test-cc with every rule subset including the new tokens vs brute force, over relabeling seeds;
    • new mutants that must change answers: (a) a redundant row outside the row space of H (one bit flipped); (b) xorunit forcing on an even row; (c) a redundant overlap row from H instead of K;
    • independent GF(2) witness checks.
  • Tiers 1-4: 5-seed medians vs main CC, node counts per level. Rows are expected only where pair sums stay sparse (TN codes with mixed row weights such as TN_200 and TN_250, the open TN_496_2_23to30, and a few tier-0 codes); xorunit alone applies everywhere.
  • Tier 5 (6 h, default seed): TN_496_2_23to30 and every other code where rows are added, main CC alongside on the same server. Any raised lower bound on an open code is reported as PLAUSIBLE; no stems are renamed.
  • Server: yfclab2 cores 4-23 only, one process per pinned core, 4 GB cap.

Credit (NOTICE / MODIFICATIONS.md / code comments): Qubitserf (github.com/Quantinuum/Qubitserf, commit 04b9349, S. Cercelescu, MIT), augment_sparse_checks (pair-XOR redundant checks); Puchert and Tillmann, arXiv:2004.03387 (redundant parity-check cuts); Okada and Kasai, cpm-ldpc-distance (forced unit). Clean-room implementation from the mathematics above; no code copied.

Activity

  1. guluchen
    added 7 commits that reference this issue on Oct 29, 2026

    GH-181 WIP: CC rules sparse, sparseov, xorunit (opt-in)

    cd28884

    GH-181 WIP: sparse pack scan by weight class; redundant rows ordered …

    6e34787

    GH-181: sparsemrv token, flag checks, runner (copied from GH-162)

    a6cb07c

    GH-181: two instantiations of the search (no GH-181 work on halves wi…

    091c105

    GH-181: pair_sums counts row overlaps first (no per-pair allocation; …

    9930c67

    GH-181: docs (MODIFICATIONS, NOTICE, README) and experiment records (…

    70f43ad

    GH-181: Tier 5 records (TN_496 main vs candidate, two relabelled cros…

    c9eac7e

  2. guluchen commented on Oct 29, 2026

    @guluchen
    guluchen
    on Oct 29, 2026
    OwnerAuthor

    Results: PR #203 (branch experiment/gh-181-cc-sparse-rows, records in optimization/experiments/GH-181/). Not merged; waiting for the PI.

    Candidate: -cc-rules=excl,pack,orbf,parity,leaf,overlap,sparse,sparseov,sparsemrv. All tokens are opt-in and default off. sparsemrv was added during the round: fewest-candidate branching over H and the redundant rows, only on halves where rows were added. It is the largest single lever.

    • Rows are added on: TN_200, TN_250, TN_496_2_23to30, and the tier-0 codes LP_34, TN_36_8_3, TN_54, TN_72_14. Every other code is idle, with node counts identical to main.
    • Tier 0: PASS.
      • make test-cc passes, including the new Part X: 576 000 ladders, 0 bad.
      • Mutants 19, 20 and 21 are caught.
      • test-cc-flags: 426 checks pass.
      • Tier0+1 identity with the tokens off: 120/120.
      • 207 answer runs are correct, and the GF(2) witness check finds 0 bad.
    • Tier 1-4 (5-seed medians vs main CC): 0.908 / 0.791 / 0.998 / 0.081, max cell 1.000. PASS.
      • TN_250: 0.081x time, 0.052x nodes.
      • TN_200: 0.27x time, 0.12x nodes.
    • Tier 5 (6 h): TN_496_2_23to30 reaches lb 27, vs lb 23 for main.
      • It reaches lb 27 with seed 0 and with relabelled seeds 1 and 2.
      • Main's lb 23 takes 13 151 s; the candidate reaches it in 396 s.
      • Level 22: 0.018x nodes.
      • The bound is PLAUSIBLE, from one implementation in three search orders. It needs an independent cross-check, and the stem is not renamed.
    • xorunit: reject. It saves at most 11 % of nodes and runs 1.3-1.5x slower.
    • Optional combination with tiebreak (scratch merge, CC engine: orbit-compatible even-weight overlap tie-break (GH-162, opt-in; do not merge before PI says merge) #180): TN_250 0.067x, BB_288 0.76x.

    Server cores 4-23 are free again.

  3. guluchen
    added a commit that references this issue on Oct 30, 2026

    GH-181: TN_496 lb 27 cross-check (sparse alone, sparse+tiebreak merge…

    f0afded

  4. guluchen commented on Oct 30, 2026

    @guluchen
    guluchen
    on Oct 30, 2026
    OwnerAuthor

    Cross-check of TN_496_2_23to30 lb 27: REPRODUCED. Details: PR #203, section 7a; optimization/experiments/GH-181/XC27/.

    Setup: 8 h per run (-cpu-lim=28800), cores 4-9, one pinned process per core, 4 GB cap. Each configuration differs from the run that found lb 27 (sparse,sparseov,sparsemrv, seeds 0/1/2).

    • (a) sparse alone, seeds 3 and 4: lb 25 / 25. Levels 1-24 EMPTY.
    • (b) sparse,sparseov,sparsemrv,tiebreak, from a different binary (scratch merge with the [Mac agent] CC engine: orbit-compatible even-weight overlap tie-break #162 code), seeds 0 and 3: lb 27 / 27, reached at 11 864 s and 10 739 s. Levels 1-26 EMPTY.
    • Extra arm, sparse,sparsemrv without sparseov, seeds 3 and 4: lb 26 / 26. Levels 1-25 EMPTY.
    • (c) MaxSAT path started at level 23: skipped. No such entry point exists: there is no lower-bound or start-cap flag.

    None of the six runs printed a FOUND, INCONSISTENT, TRAP or error line, and the upper bound stays 30.

    Caveat: all runs are DistQLDPC's CC engine; (b) differs in binary, overlap rule and search order. The stem is not renamed; the PI decides. Cores 4-23 are free.

  5. guluchen
    added 8 commits that reference this issue on Oct 30, 2026

    Rename eight tier5 stems with GH-157/GH-162/GH-183/GH-181 CC lower bo…

    dab3aa9

    Rename eight tier5 stems with GH-157/GH-162/GH-183/GH-181 CC lower bo…

    6ffc0a0

    Merge pull request #216 from guluchen/data/cc-lb-stems-20261031

    39ba87e

    Merge GH-206 stack (GH-162, GH-183, GH-206 and main c94d390 with GH-157…

    aa64110

    Merge main (a516ef0: GH-162 merge, stem renames #216) into GH-181

    6eb377e

    GH-181 merge: restore the closing fi of the GH-206 flag section

    79a62a9

    Merge main (30ce62a: GH-162, GH-183, GH-206 merges) into GH-181

    10fa542

    Merge pull request #203 from guluchen/experiment/gh-181-cc-sparse-rows

    02879a9

  6. guluchen commented on Oct 30, 2026

    @guluchen
    guluchen
    on Oct 30, 2026
    OwnerAuthor

    Merged into main at 02879a9 as opt-in (PI-approved order 2026-10-31).

    sparse, sparseov, sparsemrv and xorunit are still off by default. The CC default rule set is unchanged: excl,pack,orbf,parity,leaf,overlap,charge. The TN_496 stem was already renamed by #216 (TN_496_2_27to30).

    Mutant renumbering
    GH-181's mutants 19/20/21 clashed with GH-183's 19 and 20 and with GH-206's 21. They are now:

    • 22: a redundant row with a flipped qubit.
    • 23: xorunit branches on an even unit row.
    • 24: sparseov pair sums taken from H.

    -cc-mutant accepts 0..15 and 17..24. All IDs are unique.

    Conflict notes (main, with GH-157/162/183/206, merged into the branch)

    Checks (yfclab2, cores 3-23, 4 GB cap)

    • make test-cc: PASS.
    • make test-cc-flags: PASS (545 checks).
    • Tier 0+1 answers equal the stems, 15/15 in each of three configurations:
      • the CC default;
      • -cc-rules=excl,pack,orbf,parity,leaf,overlap,charge,sparse,sparseov,sparsemrv;
      • the same plus tiebreak.
    • TN_250_10_15 (tier 4) gave d = 15 in all four runs: +sparse,sparseov,sparsemrv; plus tiebreak; plus tiebreak with -cc-roworder=auto; and plus tiebreak,mrv with -cc-roworder=bfs.
    • With the tokens off, the tier 0+1 -v logs are byte-identical to main (which has the same default path):
      • -ub-search=off, -cc-stats and -cc-aut=off: 45/45 identical.
      • CC default: 14/15 identical. The remaining one differs only in a time-sliced ub-search finder line.
    • GitHub CI passed.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions