Non-Reversibility Is All You Need: Classical Super-Quantum Speedup via Lifted Markov Chains

Quantum computing derives its speedup from evaluating superpositions over exponentially many computational paths in O(1) operations—the quantum parallel computation thesis. Whether this speedup requires quantum mechanics, or whether it arises from a more general mathematical structure, is an open question since Deutsch (1985). We present four independent empirical proofs that non-reversible classical computation on doubled state spaces reproduces the essential features of quantum parallelism, using the PS-Lifted algorithm (Foss, 2026) and the Möbius-Lorentz correspondence on doubly stochastic spectra (Foss, 2026). Block 1: PS-Lifted consensus achieves Foss Convergence—O(1) rounds independent of network size—on Barabási-Albert graphs from n = 100 to n = 30,000, with bootstrap-confirmed super-constant spectral gap (β = −0.022, 95% CI −0.031, −0.012, entirely below zero). Block 2: The PS-Lifted eigenspectrum is rank-identical to the FDLA spectrum (Spearman ρ = 0.997, p < 10⁻²⁰), with uniform 4% compression—the classical projection of the Szegedy quantum walk operator from unitary to row-stochastic. Block 3: Birkhoff-von Neumann decomposition distributes 414 permutation paths ("parallel universes") across a network; PS-Lifted consensus computes their global sum in 11 rounds, independent of path count. This is the defining property of quantum parallelism achieved classically. Block 4: PS-Lifted pays 51× more entropy per step than FDLA but uses O(1) steps, establishing a new Foss entropy-round duality. Total entropy curves cross at n ≈ 50,000; beyond this, PS-Lifted is thermodynamically superior. Landauer's principle does not forbid O(1) consensus. The speedup does not come from quantum mechanics. It comes from non-reversibility on doubled state spaces—the same Möbius coupling f(λ,v) = (λ+v)/(1+λv) that reproduces special relativity from Markov chain dynamics (Foss, 2026). The Szegedy quantum walk and PS-Lifted consensus are spectral projections of the same operator—one unitary, one contractive.