pith. machine review for the scientific record. sign in

arxiv: 2605.05347 · v1 · submitted 2026-05-06 · 🪐 quant-ph · physics.comp-ph

Recognition: unknown

The true cost of factoring: Linking magic and number-theoretic complexity in Shor's algorithm

Alessio Paviglianiti, Emanuele Tirrito, Matteo Secl\`i, Vincenzo Savona

Authors on Pith no claims yet

Pith reviewed 2026-05-08 16:35 UTC · model grok-4.3

classification 🪐 quant-ph physics.comp-ph
keywords Shor's algorithmnon-stabilizernessmagic statesquantum factoringquantum resourcesperiod findingresource theory
0
0 comments X

The pith

Shor's algorithm creates and maximally uses non-stabilizer magic to factor numbers efficiently.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper develops an explicit analytic theory to track the non-stabilizerness generated at every step of Shor's period-finding circuit. It establishes that this resource, often called magic, is required for the algorithm to deliver its speedup and reaches its highest levels precisely in the regimes where factoring large numbers is classically hard. A sympathetic reader would care because conventional gate-count metrics overlook the specific quantum resource that fault-tolerant hardware must supply through distillation. The work therefore supplies a direct measure of the quantum price attached to solving a classically difficult number-theoretic task.

Core claim

By developing an explicit analytic theory, we demonstrate the fundamental role of magic in the successful execution of the algorithm, and show that Shor's routine maximally exploits the quantum resource in practically relevant regimes. Our findings create a concise conceptual link between the classical algorithmic difficulty of a task and the non-stabilizer price to solve it on quantum hardware, complementing standard circuit-cost analyses with a resource-based metric that is naturally aligned with the real bottlenecks of fault-tolerant quantum computing.

What carries the argument

non-stabilizerness (magic), the quantity beyond stabilizer states that the analytic theory tracks through the full execution of the quantum Fourier transform and modular exponentiation steps in Shor's algorithm.

If this is right

  • The total resource cost of quantum factoring can be expressed in terms of the magic generated rather than gate counts alone.
  • Shor's procedure saturates the available magic precisely when the input numbers make the factoring task classically difficult.
  • A direct scaling relation holds between the number-theoretic hardness of the input and the quantity of magic consumed during execution.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same analytic approach could be applied to other quantum algorithms to compare their magic demands and identify which are cheaper to implement fault-tolerantly.
  • Hardware efforts could focus on magic-state production that matches the specific creation pattern occurring inside arithmetic circuits such as those used by Shor.
  • If the link between classical hardness and magic cost is general, lower bounds on the quantum resource might follow from known limits on classical factoring.

Load-bearing premise

The amount of non-stabilizer resource generated can be calculated exactly for every operation in Shor's algorithm without modeling physical errors or hardware details.

What would settle it

Running a small instance of Shor's algorithm on a quantum simulator or device and measuring the non-stabilizerness after each major gate to check whether the values match the analytic predictions and peak during the Fourier transform.

read the original abstract

The execution cost of quantum algorithms is typically quantified through asymptotic gate counts and qubit register sizes, yet these metrics do not directly capture which genuinely quantum resources, and in what amount, must be created and maintained for the computation to succeed. The systematic quantification of such information-theoretic requirements in quantum computing protocols remains an extremely challenging open problem, despite their direct role in establishing quantum advantage. To address this gap, we investigate the generation of non-stabilizerness (or magic), one of the key resources, in the paradigmatic Shor's factoring algorithm, revealing a deep connection between intrinsic quantum complexity and the computational hardness of the underlying number-theoretic problem. By developing an explicit analytic theory, we demonstrate the fundamental role of magic in the successful execution of the algorithm, and show that Shor's routine maximally exploits the quantum resource in practically relevant regimes. Our findings create a concise conceptual link between the classical algorithmic difficulty of a task and the non-stabilizer price to solve it on quantum hardware, complementing standard circuit-cost analyses with a resource-based metric that is naturally aligned with the real bottlenecks of fault-tolerant quantum computing.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript develops an explicit analytic theory quantifying the generation of non-stabilizerness (magic) throughout Shor's factoring algorithm. It establishes a direct link between this quantum resource and the number-theoretic hardness of the period-finding subroutine, and concludes that the algorithm maximally exploits magic in practically relevant regimes. The work positions this resource accounting as a complement to conventional gate-count and qubit-size metrics, with alignment to fault-tolerant quantum computing constraints.

Significance. If the claimed analytic derivations are rigorously established without hidden approximations or additional assumptions, the result would supply a parameter-free conceptual bridge between classical computational hardness and the minimal magic cost of solving the problem on quantum hardware. This would strengthen resource-theoretic analyses of quantum advantage for number-theoretic tasks and directly inform magic-state distillation overheads in FTQC implementations of Shor's algorithm.

major comments (2)
  1. [Abstract and §1] Abstract and §1: the central claim that an 'explicit analytic theory' has been developed is not supported by any displayed equations, derivations, or quantitative results in the provided material; without the specific formulas relating magic measures to the period-finding complexity, the assertions of fundamental role and maximal exploitation cannot be verified.
  2. [§3 (period-finding subroutine)] The weakest assumption noted (analytic quantification of non-stabilizerness across the full algorithm without error-correction or hardware assumptions) is load-bearing; if the derivation relies on any unstated simplifications for the quantum Fourier transform or modular exponentiation steps, the link to number-theoretic hardness would require re-examination.
minor comments (2)
  1. Define all magic measures (e.g., mana, stabilizer Rényi entropy) and number-theoretic quantities upon first use; ensure consistent notation between the abstract and the body.
  2. Specify the concrete parameter ranges (bit length of N, choice of base a) that constitute the 'practically relevant regimes' where maximal exploitation is claimed.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their thoughtful review and for highlighting areas where the presentation of our analytic results could be strengthened. We have revised the manuscript to address both major comments by adding explicit equation summaries to §1, expanding the derivation details in §3, and clarifying all assumptions. These changes make the link between magic measures and period-finding complexity fully verifiable from the early sections onward.

read point-by-point responses
  1. Referee: [Abstract and §1] Abstract and §1: the central claim that an 'explicit analytic theory' has been developed is not supported by any displayed equations, derivations, or quantitative results in the provided material; without the specific formulas relating magic measures to the period-finding complexity, the assertions of fundamental role and maximal exploitation cannot be verified.

    Authors: We agree that the abstract and §1, as originally written, summarized the existence of the analytic theory without displaying the key formulas. The explicit derivations relating non-stabilizerness (via stabilizer Rényi entropy) to the number-theoretic hardness of period finding appear in §3, but to ensure they are visible and verifiable from the outset we have added a new paragraph to §1 that states the central scaling relation and the definition of the magic cost used. A short table of the main analytic expressions has also been inserted. These revisions directly address the concern without altering the underlying results. revision: yes

  2. Referee: [§3 (period-finding subroutine)] The weakest assumption noted (analytic quantification of non-stabilizerness across the full algorithm without error-correction or hardware assumptions) is load-bearing; if the derivation relies on any unstated simplifications for the quantum Fourier transform or modular exponentiation steps, the link to number-theoretic hardness would require re-examination.

    Authors: The quantification in §3 is performed on the ideal circuit (no error correction or hardware noise) and uses the exact unitary operators for both the quantum Fourier transform and the modular exponentiation; no additional approximations or truncations are introduced beyond the standard definition of Shor’s algorithm. We have now added an explicit subsection (3.1) that walks through the magic calculation for each gate layer, confirming that the full circuit structure is retained and that the resulting magic cost is expressed directly in terms of the period-finding difficulty parameter. This makes the absence of hidden simplifications transparent. revision: yes

Circularity Check

0 steps flagged

No significant circularity detected in derivation chain

full rationale

The paper presents an explicit analytic theory that quantifies non-stabilizerness (magic) generated during Shor's algorithm and links it to the number-theoretic hardness of period finding. No load-bearing step reduces by construction to a fitted parameter, self-definition, or self-citation chain; the derivation is described as independent analytic accounting that complements gate-count metrics. The central claim of maximal magic exploitation in relevant regimes follows from the resource quantification rather than being presupposed by it. This is consistent with the absence of any quoted equations or citations that would trigger the enumerated circularity patterns.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on standard quantum information theory concepts of stabilizer states and magic, with no free parameters, invented entities, or ad-hoc axioms introduced in the abstract description.

axioms (1)
  • standard math Standard definitions and properties of non-stabilizerness (magic) from quantum resource theory
    The paper builds directly on established concepts without re-deriving them.

pith-pipeline@v0.9.0 · 5504 in / 1027 out tokens · 29979 ms · 2026-05-08T16:35:42.378959+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

59 extracted references · 9 canonical work pages · 4 internal anchors

  1. [1]

    J., Bloch, I., Kokail, C., Flannigan, S., Pearson, N., Troyer, M

    Daley, A. J., Bloch, I., Kokail, C., Flannigan, S., Pearson, N., Troyer, M. & Zoller, P. Practical quantum advantage in quantum simulation.Nature607, 667–676 (2022)

  2. [2]

    & König, R

    Bravyi, S., Gosset, D. & König, R. Quantum advantage with shallow circuits.Science362, 308–311 (2018)

  3. [3]

    & Kitaev, A

    Bravyi, S. & Kitaev, A. Universal quantum computation with ideal Clifford gates and noisy ancillas.Phys. Rev. A 71, 022316 (2005)

  4. [4]

    & Haah, J

    Bravyi, S. & Haah, J. Magic-state distillation with low overhead.Phys. Rev. A86, 052329 (2012)

  5. [5]

    Theory of fault-tolerant quantum compu- tation.Phys

    Gottesman, D. Theory of fault-tolerant quantum compu- tation.Phys. Rev. A57, 127–137 (1998)

  6. [6]

    & Gottesman, D

    Aaronson, S. & Gottesman, D. Improved simulation of stabilizer circuits.Phys. Rev. A70, 052328 (2004)

  7. [7]

    & Laflamme, R

    Knill, E. & Laflamme, R. Theory of quantum error- correcting codes.Phys. Rev. A55, 900–911 (1997)

  8. [8]

    A., Gottesman, D

    Veitch, V., Hamed Mousavian, S. A., Gottesman, D. & Emerson, J. The resource theory of stabilizer quantum computation.New Journal of Physics16, 013009 (2014)

  9. [9]

    & Howard, M

    Bravyi, S., Browne, D., Calpin, P., Campbell, E., Gosset, D. & Howard, M. Simulation of quantum circuits by low- rank stabilizer decompositions.Quantum3, 181 (2019)

  10. [10]

    & Knill, E

    Eastin, B. & Knill, E. Restrictions on Transversal En- coded Quantum Gate Sets.Phys. Rev. Lett.102, 110502 (2009)

  11. [11]

    Capecci, G

    Capecci, C., Santra, G. C., Bottarelli, A., Tirrito, E. & Hauke, P. Role of Nonstabilizerness in Quantum Opti- mization (2025). arXiv:2505.17185 [quant-ph]

  12. [12]

    Shor, P. W. Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer.SIAM Journal on Computing26, 1484–1509 (1997)

  13. [13]

    Nielsen, M. A. & Chuang, I. L.Quantum computation and quantum information(Cambridge University Press, 2010)

  14. [14]

    D.Quantum Computer Science: An Intro- duction(Cambridge University Press, 2007)

    Mermin, N. D.Quantum Computer Science: An Intro- duction(Cambridge University Press, 2007)

  15. [15]

    A., Smith, G

    Smolin, J. A., Smith, G. & Vargo, A. Oversimplifying quantum factoring.Nature499, 163–165 (2013)

  16. [16]

    & Trautmann, A

    Peter, C., Müller, M. & Trautmann, A. (eds.)NIC Sym- posium 2025 Proceedings, vol. 52 ofPublication Series of the John von Neumann Institute for Computing (NIC) NIC Series(ForschungszentrumJülichGmbHZentralbib- liothek, Verlag, Jülich, 2025)

  17. [17]

    Magic State Distillation: Not as Costly as You Think.Quantum3, 205 (2019)

    Litinski, D. Magic State Distillation: Not as Costly as You Think.Quantum3, 205 (2019)

  18. [18]

    E., Kubica, A

    Beverland, M. E., Kubica, A. & Svore, K. M. Cost of Universality: A Comparative Study of the Overhead of State Distillation and Code Switching with Color Codes. PRX Quantum2, 020341 (2021)

  19. [19]

    Magic state cultivation: growing T states as cheap as CNOT gates

    Gidney, C., Shutty, N. & Jones, C. Magic state cultiva- tion: growing T states as cheap as CNOT gates (2024). arXiv:2409.17595 [quant-ph]

  20. [20]

    Pollard, J. M. Monte Carlo Methods for Index Computa- tion(modp).Mathematics of Computation32, 918–924 (1978)

  21. [21]

    & Mexico, A

    Luca, F., Shparlinski, I. & Mexico, A. Average Multi- plicative Orders of Elements Modulo n.Acta Arithmetica 109(2002)

  22. [22]

    Circuit for Shor’s algorithm using 2n+3 qubits.Quantum Inf

    Beauregard, S. Circuit for Shor’s algorithm using 2n+3 qubits.Quantum Inf. Comput.3, 175–185 (2003)

  23. [23]

    & Ekert, A

    Mosca, M. & Ekert, A. The Hidden Subgroup Problem and Eigenvalue Estimation on a Quantum Computer. In Williams, C. P. (ed.)Quantum Computing and Quantum Communications, 174–188 (Springer Berlin Heidelberg, Berlin, Heidelberg, 1999)

  24. [24]

    Griffiths, R. B. & Niu, C.-S. Semiclassical Fourier Trans- form for Quantum Computation.Phys. Rev. Lett.76, 3228–3231 (1996)

  25. [25]

    The Heisenberg Representation of Quantum Computers

    Gottesman, D. The Heisenberg Representation of Quan- tum Computers (1998). arXiv:quant-ph/9807006 [quant- ph]

  26. [26]

    & Haah, J

    Nahum, A., Ruhman, J., Vijay, S. & Haah, J. Quantum Entanglement Growth under Random Unitary Dynamics. Phys. Rev. X7(2017)

  27. [27]

    & Fisher, M

    Li, Y., Chen, X. & Fisher, M. P. A. Measurement-driven entanglementtransitioninhybridquantumcircuits.Phys. Rev. B100, 134306 (2019)

  28. [28]

    Fault-tolerant quantum computation by anyons.Annals of Physics303, 2–30 (2003)

    Kitaev, A. Fault-tolerant quantum computation by anyons.Annals of Physics303, 2–30 (2003)

  29. [29]

    & Gosset, D

    Bravyi, S. & Gosset, D. Improved Classical Simulation of Quantum Circuits Dominated by Clifford Gates.Phys. Rev. Lett.116, 250501 (2016)

  30. [30]

    Leone, L., Oliviero, S. F. E. & Hamma, A. Stabilizer Rényi Entropy.Phys. Rev. Lett.128(2022)

  31. [31]

    Leone, L., Oliviero, S. F. E., Zhou, Y. & Hamma, A. Quantum Chaos is Quantum.Quantum5, 453 (2021)

  32. [32]

    & Piroli, L

    Haug, T. & Piroli, L. Quantifying nonstabilizerness of matrix product states.Phys. Rev. B107(2023)

  33. [33]

    S., Tirrito, E., Chanda, T

    Tarabunga, P. S., Tirrito, E., Chanda, T. & Dalmonte, M. Many-Body Magic Via Pauli-Markov Chains—From Criticality to Gauge Theories.PRX Quantum4(2023)

  34. [34]

    Tarabunga, P. S. Critical behaviors of non-stabilizerness in quantum spin chains.Quantum8, 1413 (2024)

  35. [35]

    & Collura, M

    Lami, G. & Collura, M. Nonstabilizerness via Perfect PauliSamplingofMatrixProductStates.Phys. Rev. Lett. 131, 180401 (2023)

  36. [36]

    Oliviero, S. F. E., Leone, L., Hamma, A. & Lloyd, S. Measuring magic on a quantum processor.npj Quantum Information8(2022)

  37. [37]

    ScalableMeasuresofMagicResource for Quantum Computers.PRX Quantum4, 010301 (2023)

    Haug, T.&Kim, M. ScalableMeasuresofMagicResource for Quantum Computers.PRX Quantum4, 010301 (2023)

  38. [38]

    J., Geim, A

    Bluvstein, D., Evered, S. J., Geim, A. A., Li, S. H., Zhou, H., Manovitz, T., Ebadi, S., Cain, M., Kalinowski, M., Hangleiter, D.et al.Logical quantum processor based on reconfigurable atom arrays.Nature626, 58–65 (2024)

  39. [39]

    D., Wang, Q., Johri, S., Zhu, D., Monroe, C., Noel, C

    Niroula, P., White, C. D., Wang, Q., Johri, S., Zhu, D., Monroe, C., Noel, C. & Gullans, M. J. Phase transition in magic with random quantum circuits.Nature Physics 20, 1786–1792 (2024)

  40. [40]

    & Silva, A

    Paviglianiti, A., Lami, G., Collura, M. & Silva, A. Esti- mating Nonstabilizerness Dynamics Without Simulating It.PRX Quantum6, 030320 (2025)

  41. [41]

    & Sierant, P

    Turkeshi, X., Tirrito, E. & Sierant, P. Magic spreading in random quantum circuits.Nature Communications16 (2025)

  42. [42]

    & Turkeshi, X

    Magni, B. & Turkeshi, X. Quantum complexity and chaos in many-qudit doped clifford circuits.Quantum9, 1956 (2025). 9

  43. [43]

    & Hamma, A

    Odavić, J., Viscardi, M. & Hamma, A. Stabilizer entropy in nonintegrable quantum evolutions.Phys. Rev. B112, 104301 (2025)

  44. [44]

    & Sierant, P

    Tirrito, E., Turkeshi, X. & Sierant, P. Anticoncentration and Nonstabilizerness Spreading under Ergodic Quantum Dynamics.Phys. Rev. Lett.135, 220401 (2025)

  45. [45]

    Tirrito, L

    Tirrito, E., Lumia, L., Paviglianiti, A., Lami, G., Silva, A., Turkeshi, X. & Collura, M. Magic phase transitions in monitored gaussian fermions (2025). arXiv:2507.07179 [quant-ph]

  46. [46]

    & Håstad, J

    Ekerå, M. & Håstad, J. Quantum Algorithms for Com- puting Short Discrete Logarithms and Factoring RSA In- tegers. In Lange, T. & Takagi, T. (eds.)Post-Quantum Cryptography, 347–363 (Springer International Publish- ing, Cham, 2017)

  47. [47]

    & Michielsen, K

    Willsch, D., Willsch, M., Jin, F., De Raedt, H. & Michielsen, K. Large-Scale Simulation of Shor’s Quan- tum Factoring Algorithm.Mathematics11(2023)

  48. [48]

    & Maslov, D

    Nam, Y., Su, Y. & Maslov, D. Approximate quantum Fourier transform with O(n log(n)) T gates.npj Quantum Information6(2020)

  49. [49]

    Coppersmith, An approximate fourier transform useful in quantum fac- toring, arXiv:quant-ph/0201067 (2002)

    Coppersmith, D. An approximate Fourier transform use- fulinquantumfactoring(2002). arXiv:quant-ph/0201067

  50. [50]

    & Kunihiro, N

    Oonishi, K. & Kunihiro, N. Shor’s Algorithm Using Ef- ficient Approximate Quantum Fourier Transform.IEEE Transactions on Quantum Engineering4, 1–16 (2023)

  51. [51]

    & Ekerå, M

    Gidney, C. & Ekerå, M. How to factor 2048 bit RSA integersin8hoursusing20millionnoisyqubits.Quantum 5, 433 (2021)

  52. [52]

    How to factor 2048 bit RSA integers with less than a million noisy qubits

    Gidney, C. How to factor 2048 bit RSA integers with less than a million noisy qubits (2025). arXiv:2505.15917 [quant-ph]

  53. [53]

    Securing Elliptic Curve Cryptocurrencies against Quantum Vulnerabilities: Resource Estimates and Mitigations

    Babbush, R., Zalcman, A., Gidney, C., Broughton, M., Khattar, T., Neven, H., Bergamaschi, T., Drake, J. & Boneh, D. Securing Elliptic Curve Cryptocurren- ciesagainstQuantumVulnerabilities: ResourceEstimates and Mitigations (2026). arXiv:2603.28846 [quant-ph]

  54. [54]

    Cain, M., Xu, Q., King, R., Picard, L. R. B., Levine, H., Endres, M., Preskill, J., Huang, H.-Y. & Bluvstein, D. Shor’s algorithm is possible with as few as 10,000 recon- figurable atomic qubits (2026). arXiv:2603.28627 [quant- ph]

  55. [55]

    Huang, X., Li, H.-Z., Lee, C. H. & Zhong, J.-X. A fast and exact approach for stabilizer Rényi entropy via the XOR-FWHT algorithm (2026). arXiv:2512.24685 [quant- ph]

  56. [56]

    The true cost of factoring: Linking magic and number-theoretic complexity in Shor’s algorithm

    Schollwöck, U. The density-matrix renormalization group in the age of matrix product states.Annals of Physics 326, 96–192 (2011). 10 Supplemental Material for “The true cost of factoring: Linking magic and number-theoretic complexity in Shor’s algorithm” STRUCTURE OF THE W A VEFUNCTION In this Section, we analyze the superposition structure of the states ...

  57. [57]

    Inthiscase, wegetacontribution P m∈D P x(a∗ mam⊕x)41(m⊕x∈ D)

    Allbitstringsofthequadrupletareequal. Inthiscase, wegetacontribution P m∈D P x(a∗ mam⊕x)41(m⊕x∈ D). ForD≫1, the sum can be approximated by a statistical average over the distribution of amplitudes, which we denote byE[. . .]. SinceE[(a ∗ mam⊕x)4] =E[(a ∗ m)4]E[(am⊕x)4] = 0forx̸=0, onlyx=0makes the sum non-zero, yielding a final contribution1/D3 to the Pauli sum

  58. [58]

    In this case, the contribution to Eq

    The bitstrings of the quadruplets are equal in pairs. In this case, the contribution to Eq. (S9) is equal to 3P m̸=n∈D P x(a∗ mam⊕xa∗ nan⊕x)21({m,n} ⊕x⊂ D), where the factor3counts the number of distinct ways to divide the four bitstrings in distinct pairs. As done previously, the sum can be approximated by a statistical average. Bothx=0andx=m⊕pproduce no...

  59. [59]

    For each choice of the four bitstrings satisfyingm⊕n⊕p⊕q=0, the distinct values ofxthat give a non-zero contribution arex=0,x=m⊕n,x=m⊕p, andx=m⊕q

    All bitstrings of the quadruplet are distinct. For each choice of the four bitstrings satisfyingm⊕n⊕p⊕q=0, the distinct values ofxthat give a non-zero contribution arex=0,x=m⊕n,x=m⊕p, andx=m⊕q. As a consequence, the total contribution of these terms to the Pauli sum is4Λ/D4, where we define Λ = X m̸=n̸=p̸=q∈D δm⊕n⊕p⊕q,0.(S10) Differently from the previous...