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.
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.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.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.
We provide two improvements to Regev's recent quantum factoring algorithm (Journal of the ACM 2025), addressing its space efficiency and its noise-tolerance. Our first contribution is to improve the quantum space efficiency of Regev's algorithm while keeping the circuit size the same. Our main result constructs a quantum factoring circuit using O(nlogn) qubits and O(n3/2logn) gates. We achieve the best of Shor and Regev (upto a logarithmic factor in the space complexity): on the one hand, Regev's circuit requires O(n3/2) qubits and O(n3/2logn) gates, while Shor's circuit requires O(n2logn) gates but only O(nlogn) qubits. As with Regev, to factor an n-bit integer N, we run our circuit independently O(n) times and apply Regev's classical postprocessing procedure. Our optimization is achieved by implementing efficient and reversible exponentiation with Fibonacci numbers in the exponent, rather than the usual powers of 2, adapting work by Kaliski (arXiv:1711.02491) from the classical reversible setting to the quantum setting. This technique also allows us to perform quantum modular exponentiation that is efficient in both space and size without requiring significant precomputation, a result that may be useful for other quantum algorithms. A key ingredient of our exponentiation implementation is an efficient circuit for a function resembling in-place quantum-quantum modular multiplication. Our second contribution is to show that Regev's classical postprocessing procedure can be modified to tolerate a constant fraction of the quantum circuit runs being corrupted by errors. In contrast, Regev's analysis of his classical postprocessing procedure requires all ≈n runs to be successful. In a nutshell, we achieve this using lattice reduction techniques to detect and filter out corrupt samples.
Quantum computing promises revolutionary advances in cryptography, particularly through Shor's algorithm, which can factor large integers in polynomial time and threaten traditional RSA encryption. Through simulation experiments, our research compares Shor's algorithm implementation in ideal versus noisy quantum environments. Under ideal conditions, we factored semiprimes up to N=299 with reasonable resources, but with noise introduction, this ceiling dropped to approximately N=95, beyond which computational costs increased exponentially. The performance gap is striking: ideal simulations factored N=91 in 4 seconds, while noisy simulations required 2,600 seconds—a 650-fold increase. Our hybrid quantum-classical approach showed that noise simulation required modified circuit architectures, reducing gate count growth from 50 to 42.5 gates for comparable test numbers. Qubit requirements followed a step-function pattern in both environments, scaling from 12 qubits for N=15 to 21 qubits for N=91-95, while circuit depth increased from 11 to 17-19 units, with slightly shallower circuits in noisy conditions. In our paper, we propose a hybrid implementation strategy that addresses hardware limitations, present empirical findings on the impact of quantum noise on factoring efficiency, and evaluate the cryptographic security implications under realistic conditions. Our findings underscore the need for fault-tolerant quantum computing and error correction, especially as optimizations suggest factoring 2048-bit RSA keys would require approximately 20 million qubits running for 8 hours. This highlights the urgency in transitioning to post-quantum cryptographic algorithms like CRYSTALS-Dilithium and CRYSTALS-Kyber being standardized by NIST.