v0.5.0 — Magic (nonstabilizerness) across quantum speedups

Release notes — v0.5.0 (2026-06-17)

DOI: minted by Zenodo on release (backfilled after archival).

Summary

v0.5.0 is a new-direction release on top of v0.4.0 (DOI 10.5281/zenodo.20688069): nonstabilizerness ("magic") across quantum speedups. It leaves the order-finding theorems (T1–T6) unchanged and adds a measured + proven account of how the type of quantum speedup is tied to the amount/density of magic, directly on this repo's statevector simulation.

Key result — the speedup ladder

Algorithm	Speedup	M₂ behaviour	Density M₂/n
Simon / BV	exponential (query)	0 (affine oracle = Clifford)	0
Grover	quadratic	peak → 3 bits, 0 at the answer	→ 0
Shor (comb)	exponential	∝ t (grows)	~0.4–0.55
Shor (in-circuit)	exponential	→ L (maximal)	→ 1

The amount/density of nonstabilizerness separates the type of speedup. Magic lives not on the circuit surface but in the nonlinearity of the problem, and a black box (oracle / FFT) can hide it.

Propositions (magic-results.md)

• Lemma 1. A flat (uniform-amplitude, equal-phase) state has M₂ = 0 ⟺ its support is an 𝔽₂-affine subspace.
• Corollary 1. Graph state (1/√N)Σ|x⟩|f(x)⟩ has M₂ = 0 ⟺ f is affine. ⟹ Simon is solvable with a linear (Clifford) oracle, so M₂ ≡ 0 despite an exponential query speedup; Shor's aˣ mod N is nonlinear, so the oracle forces magic — formalizing oracle-hiding.
• Propositions 2–3. Closed form for the single-marked Grover state; its peak −log₂(a⁸+(1−a²)⁴) is maximized at a²=1/2, giving exactly 3 bits, with density M₂/n → 0.
• Proposition 2′ (general M). |ψ⟩ = b√N|+⟩ⁿ + (a−b)|W̃⟩: affine marked set W ⟹ bounded magic (superposition of two stabilizers); non-affine W ⟹ extra magic from the marked-set state itself.
• Correction. "comb magic = 0 ⟺ period is a power of two" is almost true; the exact criterion is Lemma 1 (affine support), with accidental exceptions (e.g. t=10, r=33).

What changed

New files

• magic.py — stabilizer 2-Rényi entropy tool (XOR-FWHT, exact O(n·4ⁿ)).
• experiments/grover_magic.py — Grover magic trajectory, peak saturation, general M.
• experiments/shor_comb_magic.py — comb magic, corrected T1, self-contained Shor contrast.
• experiments/oracle_magic.py — oracle-hiding (affine ⟺ M₂=0).
• experiments/magic_proofs_check.py — proposition regression checker (42 assertions).
• magic-results.md (propositions + proofs), magic-쉬운설명.md (elementary-level explanation), magic-and-quantum-speedup.md (research note), magic-prior-art.md (prior-art survey + DOI review).

Verification

• The SRE tool is cross-checked against three independent implementations (XOR-FWHT ↔ Pauli-permutation ↔ kron matrices) agreeing to 10⁻¹⁵.
• Bound 0 ≤ M₂ ≤ n confirmed. The proposition checker's 42 assertions all pass.
• Peak convergence: n=10 → 2.815, 20 → 2.994, 30 → 3.000.
• Reproduce: python -u -m experiments.magic_proofs_check (fast), and each python -u -m experiments.<name>.

Relation to prior work (full-text / journal-side review)

• arXiv:2605.05347 (Paviglianiti et al.): Shor magic ↔ period — cited as the preempting result. Still a preprint (pre-peer-review), so the novelty window stays open.
• Quantum-walk magic (published nearest neighbours): Phys. Rev. Research 10.1103/7rwg-lhpv (2506.17783), Phys. Rev. B 113, 075142 (2026) 10.1103/nzrp-49mr (2504.19750) — both 1D-lattice transport, so they do not treat Grover / complete-graph / search (verified in full text). Grover's 3-bit saturation fills that gap.
• Algorithm-magic comparisons (2505.17185, 2507.16543): variational / QFT circuits, not the Grover·Simon·Shor ladder.

Scope / limits

• The Prop 2–3 closed form is for a single marked item (M=1); general affine M has guaranteed boundedness via Prop 2′ but no explicit closed form yet.
• Comb magic is a property of the post-measurement marginal, distinct from the in-circuit → L (2605.05347).
• This release does not change the order-finding results (T1–T6) — magic is an additional direction.

Citing

Cite v0.5.0 for the magic results alongside v0.4.0 (Theorem 6) and v0.3.0 (closed-form framework). The Zenodo DOI is backfilled into CITATION.cff / README.md after archival.

---