Recognition: unknown
The true cost of factoring: Linking magic and number-theoretic complexity in Shor's algorithm
Pith reviewed 2026-05-08 16:35 UTC · model grok-4.3
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.
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
- 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.
Referee Report
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)
- [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.
- [§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)
- 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.
- 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
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
-
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
-
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
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
axioms (1)
- standard math Standard definitions and properties of non-stabilizerness (magic) from quantum resource theory
Reference graph
Works this paper leans on
-
[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)
2022
-
[2]
& König, R
Bravyi, S., Gosset, D. & König, R. Quantum advantage with shallow circuits.Science362, 308–311 (2018)
2018
-
[3]
& Kitaev, A
Bravyi, S. & Kitaev, A. Universal quantum computation with ideal Clifford gates and noisy ancillas.Phys. Rev. A 71, 022316 (2005)
2005
-
[4]
& Haah, J
Bravyi, S. & Haah, J. Magic-state distillation with low overhead.Phys. Rev. A86, 052329 (2012)
2012
-
[5]
Theory of fault-tolerant quantum compu- tation.Phys
Gottesman, D. Theory of fault-tolerant quantum compu- tation.Phys. Rev. A57, 127–137 (1998)
1998
-
[6]
& Gottesman, D
Aaronson, S. & Gottesman, D. Improved simulation of stabilizer circuits.Phys. Rev. A70, 052328 (2004)
2004
-
[7]
& Laflamme, R
Knill, E. & Laflamme, R. Theory of quantum error- correcting codes.Phys. Rev. A55, 900–911 (1997)
1997
-
[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)
2014
-
[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)
2019
-
[10]
& Knill, E
Eastin, B. & Knill, E. Restrictions on Transversal En- coded Quantum Gate Sets.Phys. Rev. Lett.102, 110502 (2009)
2009
-
[11]
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]
Shor, P. W. Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer.SIAM Journal on Computing26, 1484–1509 (1997)
1997
-
[13]
Nielsen, M. A. & Chuang, I. L.Quantum computation and quantum information(Cambridge University Press, 2010)
2010
-
[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)
2007
-
[15]
A., Smith, G
Smolin, J. A., Smith, G. & Vargo, A. Oversimplifying quantum factoring.Nature499, 163–165 (2013)
2013
-
[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)
2025
-
[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)
2019
-
[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)
2021
-
[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]
work page internal anchor Pith review arXiv 2024
-
[20]
Pollard, J. M. Monte Carlo Methods for Index Computa- tion(modp).Mathematics of Computation32, 918–924 (1978)
1978
-
[21]
& Mexico, A
Luca, F., Shparlinski, I. & Mexico, A. Average Multi- plicative Orders of Elements Modulo n.Acta Arithmetica 109(2002)
2002
-
[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)
2003
-
[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)
1999
-
[24]
Griffiths, R. B. & Niu, C.-S. Semiclassical Fourier Trans- form for Quantum Computation.Phys. Rev. Lett.76, 3228–3231 (1996)
1996
-
[25]
The Heisenberg Representation of Quantum Computers
Gottesman, D. The Heisenberg Representation of Quan- tum Computers (1998). arXiv:quant-ph/9807006 [quant- ph]
work page internal anchor Pith review arXiv 1998
-
[26]
& Haah, J
Nahum, A., Ruhman, J., Vijay, S. & Haah, J. Quantum Entanglement Growth under Random Unitary Dynamics. Phys. Rev. X7(2017)
2017
-
[27]
& Fisher, M
Li, Y., Chen, X. & Fisher, M. P. A. Measurement-driven entanglementtransitioninhybridquantumcircuits.Phys. Rev. B100, 134306 (2019)
2019
-
[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)
2003
-
[29]
& Gosset, D
Bravyi, S. & Gosset, D. Improved Classical Simulation of Quantum Circuits Dominated by Clifford Gates.Phys. Rev. Lett.116, 250501 (2016)
2016
-
[30]
Leone, L., Oliviero, S. F. E. & Hamma, A. Stabilizer Rényi Entropy.Phys. Rev. Lett.128(2022)
2022
-
[31]
Leone, L., Oliviero, S. F. E., Zhou, Y. & Hamma, A. Quantum Chaos is Quantum.Quantum5, 453 (2021)
2021
-
[32]
& Piroli, L
Haug, T. & Piroli, L. Quantifying nonstabilizerness of matrix product states.Phys. Rev. B107(2023)
2023
-
[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)
2023
-
[34]
Tarabunga, P. S. Critical behaviors of non-stabilizerness in quantum spin chains.Quantum8, 1413 (2024)
2024
-
[35]
& Collura, M
Lami, G. & Collura, M. Nonstabilizerness via Perfect PauliSamplingofMatrixProductStates.Phys. Rev. Lett. 131, 180401 (2023)
2023
-
[36]
Oliviero, S. F. E., Leone, L., Hamma, A. & Lloyd, S. Measuring magic on a quantum processor.npj Quantum Information8(2022)
2022
-
[37]
ScalableMeasuresofMagicResource for Quantum Computers.PRX Quantum4, 010301 (2023)
Haug, T.&Kim, M. ScalableMeasuresofMagicResource for Quantum Computers.PRX Quantum4, 010301 (2023)
2023
-
[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)
2024
-
[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)
2024
-
[40]
& Silva, A
Paviglianiti, A., Lami, G., Collura, M. & Silva, A. Esti- mating Nonstabilizerness Dynamics Without Simulating It.PRX Quantum6, 030320 (2025)
2025
-
[41]
& Sierant, P
Turkeshi, X., Tirrito, E. & Sierant, P. Magic spreading in random quantum circuits.Nature Communications16 (2025)
2025
-
[42]
& Turkeshi, X
Magni, B. & Turkeshi, X. Quantum complexity and chaos in many-qudit doped clifford circuits.Quantum9, 1956 (2025). 9
1956
-
[43]
& Hamma, A
Odavić, J., Viscardi, M. & Hamma, A. Stabilizer entropy in nonintegrable quantum evolutions.Phys. Rev. B112, 104301 (2025)
2025
-
[44]
& Sierant, P
Tirrito, E., Turkeshi, X. & Sierant, P. Anticoncentration and Nonstabilizerness Spreading under Ergodic Quantum Dynamics.Phys. Rev. Lett.135, 220401 (2025)
2025
-
[45]
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]
& 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)
2017
-
[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)
2023
-
[48]
& Maslov, D
Nam, Y., Su, Y. & Maslov, D. Approximate quantum Fourier transform with O(n log(n)) T gates.npj Quantum Information6(2020)
2020
-
[49]
Coppersmith, D. An approximate Fourier transform use- fulinquantumfactoring(2002). arXiv:quant-ph/0201067
-
[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)
2023
-
[51]
& Ekerå, M
Gidney, C. & Ekerå, M. How to factor 2048 bit RSA integersin8hoursusing20millionnoisyqubits.Quantum 5, 433 (2021)
2048
-
[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]
work page internal anchor Pith review arXiv 2048
-
[53]
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]
work page internal anchor Pith review Pith/arXiv arXiv 2026
- [54]
- [55]
-
[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 ...
2011
-
[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]
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]
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...
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.