A Noise-Invariant Determinism Theorem for Multi-Base Post-Processing in Shor's Order Finding (v0.3.0: closed-form σ-curve framework + §3.6 self-correction)
v0.3.0 of the multi-base post-processing analysis of Shor's order finding. The original five theorems (v0.2.1, DOI 10.5281/zenodo.20681847) are retained unchanged: (1) noise-invariant determinism, (2) logarithmic coverage time, (3) exact noise scaling 1/g_M(η), (4) conditional compatibility with Regev's 2023 multi-base framework, and (5) a hybrid (C)+Regev b-trick factoring algorithm with closed-form bound matching N=437 empirical mean within 4%. New in v0.3.0: §3.6 of v0.2.1 is *self-corrected*. The previously claimed 'boundary-flip + universal direction stochasticity + plateau/overload' framework is shown to be the finite-trial expression of a single closed form p(σ) = ρ + (p_0 - ρ)·exp(-σ²) derived from the standard phase-noise dephasing of the FFT. The closed form is verified across five algorithm classes — Grover (R²=0.88), Shor pure (0.95), QPE isolated (0.96), Simon (0.99), Hybrid (C)+b-trick (paper §3.6 setup, 0.91). Positioning: analytical complement to Yang-Markidis (arXiv:2605.16074, ICS Workshops '26), whose empirical recoverability model (1-ε)·P_s + ε·distractors has the same structural form; we provide the analytical foundation ε = 1 - exp(-σ²). Implication: SR-based factoring acceleration is precluded by a closed-form bound on |ΔK|. v0.3.0 retracts the 'boundary flip' lexicon as a distinct mechanism; all raw measurement data and theorems 1-5 are retained.
v0.3.0 of the multi-base post-processing analysis of Shor's order finding. The original five theorems (v0.2.1, DOI 10.5281/zenodo.20681847) are retained unchanged: (1) noise-invariant determinism, (2) logarithmic coverage time, (3) exact noise scaling 1/g_M(η), (4) conditional compatibility with Regev's 2023 multi-base framework, and (5) a hybrid (C)+Regev b-trick factoring algorithm with closed-form bound matching N=437 empirical mean within 4%. New in v0.3.0: §3.6 of v0.2.1 is self-corrected. The previously claimed 'boundary-flip + universal direction stochasticity + plateau/overload' framework is shown to be the finite-trial expression of a single closed form p(σ) = ρ + (p_0 - ρ)·exp(-σ²) derived from the standard phase-noise dephasing of the FFT. The closed form is verified across five algorithm classes — Grover (R²=0.88), Shor pure (0.95), QPE isolated (0.96), Simon (0.99), Hybrid (C)+b-trick (paper §3.6 setup, 0.91). Positioning: analytical complement to Yang-Markidis (arXiv:2605.16074, ICS Workshops '26), whose empirical recoverability model (1-ε)·P_s + ε·distractors has the same structural form; we provide the analytical foundation ε = 1 - exp(-σ²). Implication: SR-based factoring acceleration is precluded by a closed-form bound on |ΔK|. v0.3.0 retracts the 'boundary flip' lexicon as a distinct mechanism; all raw measurement data and theorems 1-5 are retained.
v0.3.0 of the multi-base post-processing analysis of Shor's order finding. The original five theorems (v0.2.1, DOI 10.5281/zenodo.20681847) are retained unchanged: (1) noise-invariant determinism, (2) logarithmic coverage time, (3) exact noise scaling 1/g_M(η), (4) conditional compatibility with Regev's 2023 multi-base framework, and (5) a hybrid (C)+Regev b-trick factoring algorithm with closed-form bound matching N=437 empirical mean within 4%. New in v0.3.0: §3.6 of v0.2.1 is *self-corrected*. The previously claimed 'boundary-flip + universal direction stochasticity + plateau/overload' framework is shown to be the finite-trial expression of a single closed form p(σ) = ρ + (p_0 - ρ)·exp(-σ²) derived from the standard phase-noise dephasing of the FFT. The closed form is verified across five algorithm classes — Grover (R²=0.88), Shor pure (0.95), QPE isolated (0.96), Simon (0.99), Hybrid (C)+b-trick (paper §3.6 setup, 0.91). Positioning: analytical complement to Yang-Markidis (arXiv:2605.16074, ICS Workshops '26), whose empirical recoverability model (1-ε)·P_s + ε·distractors has the same structural form; we provide the analytical foundation ε = 1 - exp(-σ²). Implication: SR-based factoring acceleration is precluded by a closed-form bound on |ΔK|. v0.3.0 retracts the 'boundary flip' lexicon as a distinct mechanism; all raw measurement data and theorems 1-5 are retained.
Five theorems on classical post-processing of multi-base order-finding measurements in Shor's algorithm: (1) noise-invariant determinism, (2) logarithmic coverage time, (3) exact noise scaling 1/g_M(η), (4) conditional compatibility with Regev's 2023 multi-base framework, and (5) a hybrid (C) + Regev b-trick factoring algorithm with closed-form bound matching N=437 empirical mean within 4%. Verified across 17,700 measurements at six composite sizes. Additionally documents a universal trial-level mechanism observation at (N, d) = (437, 4): across 13 independent base sets (200 trials × 12 sigma values each = 31,200 trial-measurements), phase noise universally flips trials at one of the K-bin boundaries (77% K=1/K=2, 15% K=2/K=3, 8% long-jump) of single-run hybrid factoring, with stochastic per-seed direction (mean SR +0.14%, t=0.51, p=0.31, not significant). The mechanism follows the classical Benzi-Buchleitner stochastic resonance shape (saturation plateau + overload decline) and provides a clean conceptual bridge between integer factoring and the noise-as-resource literature (ENAQT), with no cryptographic implication. Companion code is ~1000 lines of numpy with no quantum libraries required.
v0.5.0 adds a new direction to the multi-base order-finding work: nonstabilizerness ("magic") across quantum speedups, measured and proven on a numpy statevector simulation. Retained unchanged: six theorems on classical post-processing of Shor's order finding (T1 noise-invariant determinism, T2 logarithmic coverage time, T3 exact noise scaling 1/g_M(eta), T4 Regev-2023 compatibility, T5 hybrid (C)+Regev b-trick factoring, T6 stochastic-resonance no-go) and the closed-form sigma-curve verified across five algorithm classes. New (magic): using a verified stabilizer 2-Renyi entropy (SRE) tool via the XOR fast Walsh-Hadamard transform (cross-checked to 1e-15), the amount/density of nonstabilizerness separates the TYPE of quantum speedup. (i) Grover's search magic peaks at exactly 3 bits as a function of problem size and returns to zero at the answer (density M2/n -> 0; closed form, peak = max of -log2(a^8+(1-a^2)^4) at a^2=1/2). (ii) The function graph state (1/sqrt N) sum_x |x>|f(x)> has M2=0 iff f is F2-affine, so Simon with a linear (Clifford) oracle generates zero magic despite an exponential query speedup, while Shor's modular exponentiation is nonlinear and forces magic — formalizing how an oracle/FFT black box hides the nonlinearity that is magic's source. (iii) Shor's post-measurement comb magic grows with problem size, completing a speedup ladder: Clifford/affine -> 0, Grover (quadratic) -> bounded density 0, Shor (exponential) -> growing toward maximal. Includes a 42-assertion proposition checker and a prior-art survey vs arXiv:2605.05347 (Shor magic), Phys. Rev. Research 10.1103/7rwg-lhpv and Phys. Rev. B 10.1103/nzrp-49mr (quantum-walk magic). numpy + Python stdlib only.
v0.5.1 extends the magic (nonstabilizerness) direction of v0.5.0 (DOI 10.5281/zenodo.20725965). The six order-finding theorems (T1-T6) are RETAINED unchanged; the magic direction is now integrated into the canonical paper as Section 9. NEW IN v0.5.1: (1) A coding-theory of marker sets for the flat state |flat_W> over a support W in F2^n: an additive-energy closed form M2 = -log2(M^-4 sum_x E(W cap (W+x))) (Prop 4), the exact zero-test M2=0 iff the autocorrelation A_W is two-valued ({0,M}) iff W is an affine subspace, a Sidon (B2) law M2 = log2(M^3/(7M-6)) -> 2 log2 M - log2 7 (Prop 5), and an exact expectation for a uniform random M-subset E[xi] M^4 = (7M^2-6M) + 7(M)_4/(N-3) + N(N-1)(N-2)(N-4)(M)_8/(N)_8 (Prop 5'). The minimum Hamming distance is shown NOT to determine magic ({0,1,2,3} vs {0,1,2,4} share d_min=1 but M2=0 vs 1.54). (2) Oracle-hiding = T-cost (Prop 6): M2(graph state of f) > 0 iff f has a degree>=2 ANF monomial iff the oracle U_f needs non-Clifford (Toffoli/T) gates, all zero iff f is affine; a fault-tolerant resource estimate (oracle_ftqc_estimate.py) converts the nonlinear ANF (degree-d monomial -> (2d-3) Toffolis -> 7T each) into a T-count, with the honest caveat that per-output-bit ANF synthesis is an UPPER bound (real modular exponentiation is far cheaper via windowed arithmetic; cf. Gidney-Ekera 2021). HONEST NOVELTY AUDIT (the headline of this release): full-text comparison of all four code<->magic literatures shows the flat-state closed form (Prop 4) is the uniform-support specialization of Tarabunga-Castelnovo's Rokhsar-Kivelson SRE formula (Quantum 8, 1347 (2024), Eq. 8) -- CREDITED, not claimed as new -- and the 2 log M growth rate is the saturation of the standard bound M_alpha <= 2 log R. The surviving defensible contributions are the Grover 3-bit ladder (carried from v0.5.0), the coding-theoretic SPECIALIZATION (zero-test, exact Sidon constant, exact random expectation, d_min refutation, Grover multi-marked application), and oracle-hiding = T-cost; differentiated from hypergraph-state magic (phase-encoded / RM(2): arXiv:2308.01886, 2602.23687), weight-enumerator SRE tools (arXiv:2308.05152), and permutation-invariant/Dicke magic (arXiv:2402.08551). Carried from v0.5.0: a verified stabilizer 2-Renyi entropy tool (XOR fast Walsh-Hadamard, cross-checked to 1e-15), the speedup ladder (Simon/affine -> 0; Grover quadratic -> bounded, density 0; Shor exponential -> growing), and a 42-assertion proposition checker (all pass). ALSO ADDED LATE IN v0.5.1 (JAMES-DISCOVER): an automated discovery loop (Generator -> Probe -> Miner -> Adversary -> Promoter, numpy-only, no LLM) layered on the existing magic infrastructure. The loop first passes a D1 sanity gate by re-deriving the Sidon constant and the additive-energy closed form from scratch (discover_poc.py), then yields a D3 finding (discover_d3_jensen.py) that PARTIALLY CLOSES one of v0.5.1's listed open items: defining the Jensen gap J(M,N) := E[M2] + log2 E[xi] >= 0, the loop discovers J ~ 1/N in the sparse regime M^2 << N (measured slope -0.96 across M in {6,8,10}, n in {10..13}), so Prop 5' (E[xi] closed form) is not merely a Jensen lower bound but an asymptotically tight estimate of E[M2] with absolute error O(1/N). The saturation boundary M^2/N -> 1 and the prefactor kappa(M) = J * N remain open. numpy + Python standard library only; no quantum libraries required.
Order finding is the core subroutine of Shor's algorithm. On NISQ hardware, phase estimation output distributions are often distorted by noise, making correct order recovery difficult. We study recoverability in noisy order finding: given a measured precision-register distribution, when does standard classical post-processing still return the true order? We analyze 680 distributions from IBM quantum systems across problem instances and circuit settings. For each distribution, we apply continued-fraction post-processing with modular verification and define recoverability as whether the recovered order equals the true one. We characterize each distribution using four features: autocorrelation peak strength, normalized entropy, dominant verified mass fraction, and verified margin fraction. We evaluate these quantities using marginal feature comparisons, single-feature AUROC analysis, and multivariate tree-based classifiers. We use random-forest permutation importance to assess which quantities contribute distinct predictive information once the other features are known. To make classification behavior interpretable, we train a decision tree that exposes threshold rules for recoverable and non-recoverable distributions. We find that recoverability is strongly associated with residual comb-like structure in the measured distribution and the way verified probability mass is organized across candidate denominators. The dominant verified mass fraction is the strongest single-feature indicator of recoverability, and tree-based analysis shows it also provides the primary split in an interpretable threshold description. Some highly distorted distributions remain recoverable when one verified denominator dominates the post-processing mass, while some visibly structured distributions fail because classical post-processing favors an incorrect verified denominator.
For a pure encoded state perturbed as exp(i epsilon W) with W drawn from an arbitrary centered Gaussian ensemble of Hermitian operators, the complete fourth-order coefficient of the mean relative-entropy disturbance of any reduced state is derived in closed form. The coefficient decomposes into five channels - the disconnected drift term and four connected channels - each an explicit finite sum over pairs of Karhunen-Loeve modes of the noise covariance, contracted with exact confluent divided-difference kernels of the logarithm. This closes, for arbitrary structured ensembles, the remainder that previous work in this programme controlled only for unitarily invariant ensembles: for the invariant case the mode-completeness identity reproduces Wick's theorem and the pair sums collapse to the known closed forms, while for structured ensembles all five channels are computable deterministically with no sampling, and the dominance of the drift term is governed by a computable coherence ratio rather than a universal law. Two consequences are developed. For stabilizer codes under Knill-Laflamme-protected Pauli noise the three commutator channels vanish identically and the total quartic coefficient reduces to a pure counting expression, verified rational-exactly at three configurations spanning the five-qubit, Steane, and [[4,2,2]] codes. Every closed form is certified against direct simulation, including a genuinely retrodictive test: two quartic coefficients measured and archived in an earlier study of this programme, before the present theory existed, are reproduced to 0.0 and +0.4 standard errors, with the previously unexplained connected excess of one of them given exactly by a new channel formula. This paper is posted here for the first time. It is the fifth of a series: the reconstruction-error hierarchy (DOI 10.13140/RG.2.2.19676.14723), the chi-squared divergence law (Zenodo DOI 10.5281/zenodo.23621356), the induced Lindblad drift (Zenodo DOI 10.5281/zenodo.23621898), and the Knill-Laflamme danger maps (Zenodo DOI 10.5281/zenodo.23622023). Its references point to the corrected versions of those papers. Simulation scripts and data: Zenodo DOI 10.5281/zenodo.21246031.