A Noise-Invariant Determinism Theorem for Multi-Base Post-Processing in Shor's Order Finding (v0.5.0: nonstabilizerness / magic across quantum speedups)
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.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.
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.
Quantum advantage is widely understood to rely on key quantum resources beyond entanglement, among which nonstabilizerness (quantum ``magic'') plays a central role in enabling universal quantum computation. However, the exact evaluation of the second-order stabilizer Rényi entropy for generic many-body quantum states remains computationally challenging, with brute-force methods scaling as O(8N) for an N-qubit state. Here we develop a deterministic and exact algorithm that reduces this cost to O(N4N) while retaining natural parallelism. This advance enables high-precision exact calculations for generic state vectors at medium system sizes, and provides a practical tool for investigating the scaling, phase structure, and nonequilibrium dynamics of quantum magic in many-body systems.
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.
Nonstabilizerness (magic) is the quantum resource that, together with stabilizer operations, makes universal quantum computation possible. However, quantifying nonstabilizerness is difficult. The standard measure sums over exponentially many Pauli operators, and for quantum codes no quantitative theory has been available. A structural observation removes this obstacle: the Clifford sector carries no magic and can be removed by a Clifford transformation, leaving an order-three object whose magic is an exactly evaluable fourth moment. Removing this inert background yields closed forms for several code families: a formula for all Dicke states, reducing a 100-qubit case from 4100 terms to a short binomial sum; a bound for cubic-phase codes (twisted quantum doubles and non-Abelian topological order), saturated only by the D4 code; and a cyclic/zero criterion for group multiplication states. For codeword-stabilized (CWS) codes, the companion paper \cite{Liu26arXiv} carries this reduction to its conclusion: the most magical codes are exactly the Sidon sets, and the nonstabilizerness bounds the code's transversal non-Clifford power. Together these results reduce the computation of nonstabilizerness for a broad class of codes to finite classical counting problems, and identify the maximally magical codes among them.
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.