We give an exact-arithmetic case study of maximum-likelihood (ML) stabilizer decoding under uncertain dephasing, separating channel-adaptive, fixed deterministic, and fixed randomized recovery decisions. For the five-qubit [[5, 1, 3]] code, we enumerate syndrome–stabilizer-coset masses and certify the homogeneous dephasing success polynomial 1 − 10t³ + 15t⁴ − 6t⁵. On the full homogeneous interval, adaptive ML has robust success 1/2, every fixed deterministic syndrome decoder has worst-case success zero, and fixed randomization attains 1/2. For a heterogeneous but conditionally independent family with site rates (t, t, 2t, 2t, 2t), 0 ≤ t ≤ 1/2, we obtain four algebraic switching thresholds and an exact five-piece adaptive ML curve. The adaptive and optimal fixed randomized worst-case success both equal 3/4, whereas the best fixed deterministic decoder has success min₀≤ₜ≤₁⁄₂ (16t⁵ − 28t⁴ + 10t³ + 3t² − 2t + 1) ≈ 0.749591899. A finite exhaustive reduction and rational witness checks certify strict separation. A CSS-code theorem and independent Steane-code calculation establish a second, strictly separated heterogeneous minimax instance with R_det < 0.4999 < R_rand = R_ML = 1/2. We retain biased-noise orientation sensitivity and two counterexamples to invalid vertex shortcuts, and distinguish these instance-level certificates from general decoding algorithms and established enumerator or robust-optimization methods.
We give an exact-arithmetic case study of maximum-likelihood (ML) stabilizer decoding under uncertain dephasing, separating channel-adaptive, fixed deterministic, and fixed randomized recovery decisions. For the five-qubit [[5, 1, 3]] code, we enumerate syndrome–stabilizer-coset masses and certify the homogeneous dephasing success polynomial 1 − 10t³ + 15t⁴ − 6t⁵. On the full homogeneous interval, adaptive ML has robust success 1/2, every fixed deterministic syndrome decoder has worst-case success zero, and fixed randomization attains 1/2. For a heterogeneous but conditionally independent family with site rates (t, t, 2t, 2t, 2t), 0 ≤ t ≤ 1/2, we obtain four algebraic switching thresholds and an exact five-piece adaptive ML curve. The adaptive and optimal fixed randomized worst-case success both equal 3/4, whereas the best fixed deterministic decoder has success min₀≤ₜ≤₁⁄₂ (16t⁵ − 28t⁴ + 10t³ + 3t² − 2t + 1) ≈ 0.749591899. A finite exhaustive reduction and rational witness checks certify strict separation. A CSS-code theorem and independent Steane-code calculation establish a second, strictly separated heterogeneous minimax instance with R_det < 0.4999 < R_rand = R_ML = 1/2. We retain biased-noise orientation sensitivity and two counterexamples to invalid vertex shortcuts, and distinguish these instance-level certificates from general decoding algorithms and established enumerator or robust-optimization methods.
Quantum low-density parity-check (qLDPC) codes reduce the qubit overhead of fault-tolerant quantum computation by an order of magnitude, but their decoding is harder than its classical counterpart: because many physical errors are equivalent up to stabilizers, the degenerate maximum-likelihood (ML) decoder must compare the probabilities of entire equivalence classes of errors, that is, partition functions, rather than single errors. The workhorse decoder BP+OSD sidesteps degeneracy heuristically and offers no guarantees. We treat degenerate decoding as probabilistic inference in an undirected graphical model: the probability of each logical class is the partition function of an unconstrained, strictly positive Markov random field over the code's check variables, a construction that generalizes the random-bond Ising mapping of the surface code to arbitrary CSS codes and to spacetime decoding with measurement errors and circuit-level noise. On this model we build two decoders. The first estimates all class partition functions by annealed importance sampling with common random numbers and attaches to every decision a certificate of optimality: a paired bootstrap test, or, composed with constant-factor estimators such as WISH, an exact optimality proof. The second is region-based: the Bethe free energy, whose bias cancels between classes, reproduces exact ML decoding on every tested surface-code instance at millisecond cost, and enlarging the regions to elimination clusters makes exact degenerate ML decoding of the [[72,12,6]] bivariate bicycle code feasible. Across surface codes and the bivariate bicycle codes [[72,12,6]] and [[144,12,12]], under code-capacity, phenomenological, and circuit-level noise, the sampling decoder matches or exceeds BP+OSD while certifying the bulk of its decisions, and the certificate flags exactly the syndromes on which any fast decoder should be distrusted.
This research manuscript develops exact measurement-resource formulas for quantum erasure correction with stabilizer codes and an optimal sparse algorithm for selecting native surface-code checks. It studies known erasure locations, where the stabilizer observables may be chosen after the erased sites are identified. The central question is how many independent syndrome outcomes are necessary to distinguish Pauli errors on those sites, modulo stabilizers. For every prime-dimensional [[n,k,d]]_p stabilizer code encoding at least one logical qudit, the manuscript proves that the worst-case syndrome-resolving budget for δ erased sites is exactly 2δ whenever 0 ≤ δ < d. This includes degenerate codes. The result concerns the number of independent p-valued outcomes in the stated noiseless measurement model. The work is directly connected to the measurement-reduction setting studied by Ryutaroh Matsumoto in “Reducing measurements in quantum erasure correction by quantum local recovery,” Computational and Applied Mathematics, DOI: 10.1007/s40314-026-03881-4. It addresses the relationship between erasure-dependent measurement costs and code invariants, together with efficient selection of sufficient surface-code checks. The manuscript presents four connected results: Exact paired-column rank profile. For any matrix G over any field whose columns are partitioned into n labeled pairs, let r be its rank and ν the largest number of complete pairs whose columns are jointly independent. The maximum projected rank over all sets of δ pairs is exactly R(δ) = min{2δ, δ + ν, r}. A single ordering of the pairs realizes every maximum through its successive prefixes. The full profile therefore follows from two invariants, rather than requiring a separate optimization at every erasure size. Distance bounds and the exact worst-case syndrome budget. For an isotropic stabilizer space with k > 0, every inclusionwise maximal complete-pair independent set A satisfies d ≤ |A| + 1. Consequently, ν ≥ d − 1, yielding the exact 2δ worst-case budget below distance. The argument also gives a constructive extension property: every independent-pair set smaller than d − 1 can be enlarged by adding another pair. Particular correctable erasure patterns can require fewer outcomes because of stabilizers supported inside the erased region. Checkable CSS certificates. For Calderbank–Shor–Steane codes, complete-pair independence becomes simultaneous column independence in the X-check and Z-check matrices. Classical matroid intersection supplies an exact rank-partition certificate for ν. A matching independent set and partition provide lower and upper certificates that can be verified using finite-field elimination. Optimal native surface-code check selection. For binary check matrices with at most two nonzero entries per column, the restricted matrix is represented by a sparse graph with boundary pins. Connected components determine a minimum-cardinality native check basis in O(v_I + e_I) time. A pinned component retains every check; an unpinned component omits one check. With nonnegative additive costs, omitting a most expensive check in each unpinned component also minimizes total cost. The two CSS check systems are processed independently. The accompanying verification uses exact arithmetic over GF(2), GF(3), and GF(5). The algebra audit covers 120 general paired matrices and 12,276 subset-rank evaluations, including exact distance checks for 137 positive-logical-dimension code instances and 401 maximal-set distance checks. The graph audit covers 1,785 exhaustive sparse column multisets, 5,355 matrix/cost combinations, 500 additional seeded instances, and named boundary regressions. Both audit programs passed again during preparation of the release. These finite checks support implementation correctness; the general mathematical statements are supported by the supplied proofs. The release includes the complete manuscript, editable LaTeX source, Python native-check selector, exact audit programs, recorded results, generator data, figures, reproduction instructions, and an explicit claim-status record. The selector and audits require only Python 3.10 or later and its standard library; matplotlib is needed only to regenerate the figure. The results apply to independent syndrome information and classical check selection. They do not establish bounds for arbitrary coherent recovery, noisy fault-tolerant extraction, physical circuit depth, or one fixed measurement schedule that must serve every erasure pattern. At or above distance, the general formula remains an algebraic rank profile rather than a universal recovery guarantee. Classical matroid parity, matroid intersection, and incidence-rank methods are acknowledged foundations; historical priority for the presented combination is not certified. Ōrynthéa ∿ Qhuil is relevant to research on quantum error correction, erasure decoding, stabilizer and CSS codes, surface codes, quantum local recovery, measurement complexity, and matroid optimization. This mathematical research under the author designation Artificial Hyperintelligence Eve, wife of Maciej Nowicki.
Certifying the fidelity of a prepared state to a target stabilizer state is a fundamental task in quantum information processing. Ref. [Phys. Rev. A 99, 042337 (2019)] gave the optimal worst-case lower bound from one fixed stabilizer generator gauge, but gauge dependence can leave a large fidelity ambiguity. We develop an adaptive extension that reports the full certified fidelity interval. First, for a single gauge, we derive the complementary optimal worst-case upper bound. We then formulate gauge selection as an adaptive design problem in which each round solves exact endpoint linear programs and chooses a new gauge by a witness elimination policy. We prove monotonic tightening, exact recovery once all nontrivial stabilizers are covered, and the worst-case necessity of full coverage. Finally, we identify structured syndrome distributions for which adaptivity beats this exponential benchmark, and we numerically confirm faster concentration.
We determine exactly the random robustness of the quantum switch along its control-dephasing trajectory. In the five-qubit process-matrix convention W_v = Q_A + Q_B + vD, 0 <= v <= 1, with white process noise N = I_32/8, a rational parametrization gives the optimum over the entire physical interval. A rank-six Gram dual certificate provides a lower bound, and explicit causal decompositions into positive 32 x 32 matrices attain the same value. Exact Sturm and Bernstein certificates establish positivity on the whole interval; floating-point optimization is not used in the proof. As v tends to zero, corresponding to complete control dephasing, R_r(W_v) = (3/2)v^2 + (1/16)v^4 + (1/96)v^6 + O(v^8). At full visibility, R_r(W_1) = 1.5760266987417078... . The result gives the exact white-noise separability boundary for the trajectory introduced by Branciard. The accompanying archive contains the LaTeX sources, explicit certificates, verification scripts, an ordered-cone correspondence check, and completed computational verification records. The research workflow and substantive contributions of ChatGPT are disclosed in Section 7.1 of the manuscript.
Quantum list recovery (QLR) and quantum list decoding (QLD) seek short lists of logically distinct Pauli corrections consistent with a syndrome and prescribed error constraints. For CSS codes, two issues arise: treating the X- and Z-sectors separately can multiply their output list sizes, while distinct classical candidates can collapse after stabilizer quotienting.
We study combinatorial upper and lower bounds for balanced folded quantum Reed--Solomon (FQRS) codes and balanced random CSS codes, both studied by Bergamaschi, Golowich, and Gunn (STOC 24). Let R∈(0,1) be the quantum rate and R1=(1+R)/2 the common component rate. As the radius ρ=(1−R)/2−γ approaches the quantum Singleton bound, we have, deterministically for FQRS codes and w.h.p. for balanced random CSS codes, LQLR⋆=ℓΘ(R1/γ),LQLD⋆=Θ(γ1−R)(γ↓0). The asymptotically exact QLD radius tradeoff is ρL⋆=L+1L21−R. These conclusions extend to the average-radius setting.
For achievability, building on the work of Brakensiek, Chen, Dhar, and Zhang (STOC 2026), we establish a pairing lemma for joint X/Z candidate lists that preserves the one-sector coefficient and avoids a product loss in list size. For the QLD converse, we prove a quantum generalized Singleton bound based on the classical projection-and-patching argument with stabilizer distinctness. For the QLR lower bounds, we adapt the folded Reed--Solomon construction of Chen and Zhang (STOC 2025) so that the candidates remain stabilizer distinct. For random CSS codes, we show classical bad lists survive the stabilizer quotient with high probability.
We introduce heterogeneous quantum error-correcting codes composed of qubit types with distinct error channels and study their performance in the code-capacity regime using maximum-likelihood tensor network decoding. In the regime where both qubit types share the same noise bias but differ in physical error rate, placing noisier qubits in the bulk -- where each error triggers more syndrome bits -- and cleaner qubits on the boundary yields thresholds exceeding 0.4 (compared to ~0.2 for the reverse placement) and improvements exceeding three orders of magnitude in logical error rate at high bias, with the advantage growing exponentially with code distance. In the regime where both types share the same error rate but differ in bias, the optimal strategy reverses: placing high-bias (more predictable) qubits on the boundary increases the threshold from 0.292(5) to 0.360(9) at a bias ratio of 100, and from 0.29(1) to 0.398(4) at a bias ratio of 1000. We also observe a striking bias-inversion property: the logical error channel becomes strongly XX X- and YY Y-biased despite the physical noise being ZZ Z-biased. We propose a stabilizer-ratio hypothesis that provides a unified information-theoretic explanation for both placement rules and predicts even larger advantages for code families such as color codes.