pith. sign in

arxiv: 2605.16998 · v1 · pith:YUND3VSGnew · submitted 2026-05-16 · 🪐 quant-ph · cs.LG

mathcal{O}(n) alternative to Quantum Fourier Transform with efficient neural net classical post-processing

Kaiming Bian , Zujin Wen , Oscar Dahlsten This is my paper

Pith reviewed 2026-05-19 20:32 UTC · model grok-4.3

classification 🪐 quant-ph cs.LG
keywords Shor's algorithmhidden subgroup problemquantum Fourier transformshallow circuitsneural networksFisher informationcircuit depth reduction
0
0 comments X

The pith

An O(n) circuit using Hadamards and controlled-phase gates can replace the O(n squared) quantum Fourier transform in Shor's algorithm with neural-net post-processing.

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

The paper seeks to reduce the circuit depth required for hidden-subgroup algorithms such as Shor's factoring. It shows that the quantum Fourier transform relies on shift invariance to remove random offsets and on retaining information about the hidden generator in its measurement statistics, which the authors quantify using discrete Fisher information. The authors construct HP-L circuits from Hadamard gates followed by L layers of controlled-phase gates and prove that these circuits are shift-invariant. Numerical results indicate that the Fisher information grows exponentially with qubit number even for small L. The linear-depth HP-1 version, when combined with a neural network for classical post-processing, successfully factors numbers in simulation, offering a shallower quantum routine for near-term devices.

Core claim

The central claim is that the HP-1 circuit preserves shift invariance and exponentially growing discrete Fisher information about the hidden subgroup generator. This allows the O(n) HP-1 circuit to substitute for the O(n squared) QFT in Shor's algorithm, with the period extraction performed by an efficient neural network instead of the standard inverse Fourier transform, as confirmed by numerical experiments.

What carries the argument

HP-L circuits, which apply Hadamard gates followed by L controlled-phase gate layers to maintain shift invariance and information retention for hidden subgroup problems.

If this is right

  • The quantum part of Shor's algorithm becomes feasible with shallower circuits suitable for noisy hardware.
  • Post-processing can be optimized separately using machine learning techniques.
  • The method may generalize to other instances of the hidden subgroup problem.
  • It demonstrates that not all properties of the QFT are necessary if classical resources can compensate.

Where Pith is reading between the lines

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

  • Hardware experiments could validate the approach for small n where current devices can run the HP-1 circuit.
  • If the Fisher information scaling is universal, it provides a new way to design minimal-depth circuits for phase-related tasks.
  • The neural net might be interpretable to reveal classical algorithms that achieve similar extraction without training.

Load-bearing premise

The neural network post-processing can extract the hidden subgroup generator reliably from the statistics produced by the HP-1 circuit for large n without requiring resources that scale exponentially with n or failing in the presence of realistic noise.

What would settle it

Numerical simulation or quantum hardware execution of the full pipeline for a Shor's problem instance with more than 30 qubits where the neural network outputs an incorrect period or factor.

Figures

Figures reproduced from arXiv: 2605.16998 by Kaiming Bian, Oscar Dahlsten, Zujin Wen.

Figure 1
Figure 1. Figure 1: FIG. 1 [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: FIG. 2 [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: (a), the neural network achieves rapid convergence when trained on 9-, 10-, and 11-qubit instances. Both the top-1 (correct period ranked first) and top-3 accuracies increase swiftly within a few epochs. (b) (a) FIG. 3. Numerical simulation shows successful Shor factoring via HP-L and neural net post-processing. There is a depth-7 HP-1 circuit with only 11 Hadamards and 30 controlled-phase gates on 11 qubi… view at source ↗
Figure 4
Figure 4. Figure 4: FIG. 4. Log-linear fits of the qubit-scaling curves in Fig. 2(b). Markers denote the mean Fisher-information values plotted [PITH_FULL_IMAGE:figures/full_fig_p017_4.png] view at source ↗
read the original abstract

The Quantum Fourier Transform (QFT) is required by hidden subgroup problem (HSP) algorithms, including Shor's algorithm for factoring. The circuit depth of the QFT remains challenging for near-term hardware. To find shallower alternatives we identify two properties that are exploited by the QFT to enable HSP. Firstly, the shift invariance of the QFT allows for the removal of a random overall shift. Secondly, the QFT retains information about the hidden subgroup generator accessible in the measurement outcomes. We quantify that information via the discrete Fisher information. We construct a family of shallow circuits using Hadamards and controlled-Phase gates, HP-$L$ circuits, that we prove preserve shift invariance. Numerical analysis shows these circuits retain exponentially growing Fisher information. The $\mathcal{O}(n)$ HP-$1$ can replace the $\mathcal{O}(n^2)$ QFT in Shor's algorithm, as demonstrated numerically, with an efficient neural network implementing classical post-processing.

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 paper identifies shift invariance and retention of hidden-subgroup-generator information (quantified by discrete Fisher information) as key properties exploited by the QFT in HSP algorithms such as Shor's. It constructs a family of shallow HP-L circuits (Hadamards followed by controlled-Phase gates) and proves that they preserve shift invariance. Numerical simulations are reported to show that the discrete Fisher information grows exponentially with n for these circuits. The central claim is that the O(n)-depth HP-1 member of the family, together with an efficient neural-network classical post-processor, can replace the O(n²) QFT in Shor's algorithm, supported by numerical demonstrations on small instances.

Significance. If the neural-network post-processing is shown to scale efficiently and generalize beyond the small-n regime, the result would offer a concrete route to shallower circuits for hidden-subgroup problems while retaining the necessary information-theoretic properties. The explicit proof of shift invariance for the HP-L family and the first-principles quantification of Fisher information from the measurement statistics are clear strengths that stand independently of the scaling claim.

major comments (2)
  1. [Numerical results and application to Shor's algorithm] The central claim that the O(n) HP-1 circuit replaces the QFT in Shor's algorithm rests on numerical demonstrations for small n together with the unproven assumption that the neural-network post-processor remains efficient (depth, width, and sample complexity polynomial in n) for arbitrary problem sizes. No analytic bound or scaling analysis is supplied; if the required resources grow exponentially or generalization fails, the overall O(n) cost claim does not hold. This assumption is load-bearing for the replacement result.
  2. [Fisher information analysis] While the discrete Fisher information is shown numerically to increase with n, the manuscript provides no rigorous lower bound establishing that the information retained by HP-1 is sufficient to recover the hidden subgroup generator with high probability for all n, independent of the neural-network training. The replacement argument therefore depends on the empirical behavior of the trained network rather than an information-theoretic guarantee.
minor comments (2)
  1. [Numerical analysis] Clarify the precise definition of the discrete Fisher information used in the numerical plots and confirm that the same estimator is applied uniformly across all circuit depths and problem sizes.
  2. [Neural-network post-processing] The manuscript would benefit from an explicit statement of the neural-network architecture (number of layers, activation functions, training procedure) and the training-set sizes employed for each n in the reported experiments.

Simulated Author's Rebuttal

2 responses · 2 unresolved

We thank the referee for their insightful comments on our manuscript. We provide detailed responses to the major comments below and indicate where revisions will be made to address the concerns raised.

read point-by-point responses

  1. Referee: [Numerical results and application to Shor's algorithm] The central claim that the O(n) HP-1 circuit replaces the QFT in Shor's algorithm rests on numerical demonstrations for small n together with the unproven assumption that the neural-network post-processor remains efficient (depth, width, and sample complexity polynomial in n) for arbitrary problem sizes. No analytic bound or scaling analysis is supplied; if the required resources grow exponentially or generalization fails, the overall O(n) cost claim does not hold. This assumption is load-bearing for the replacement result.

    Authors: We acknowledge that the efficiency of the neural-network post-processor for large n is not proven analytically in the manuscript. Our demonstrations are numerical for small n, as stated. However, the neural network we employ has a fixed architecture whose size does not grow with n, and the training uses a number of samples polynomial in the output dimension. The key properties preserved by HP-1—shift invariance and exponential Fisher information growth—ensure that the relevant information is present in the measurement outcomes in a structured way that the network can learn to extract. We will revise the manuscript to better clarify the neural network architecture used and to discuss why its efficiency is expected to hold based on the information retention properties. We maintain that this provides a viable O(n) alternative based on the evidence presented, though we agree that a full theoretical analysis of the post-processor scaling would be a valuable addition for future work. revision: partial

  2. Referee: [Fisher information analysis] While the discrete Fisher information is shown numerically to increase with n, the manuscript provides no rigorous lower bound establishing that the information retained by HP-1 is sufficient to recover the hidden subgroup generator with high probability for all n, independent of the neural-network training. The replacement argument therefore depends on the empirical behavior of the trained network rather than an information-theoretic guarantee.

    Authors: We agree that no rigorous lower bound is provided for the Fisher information in the current work. The analysis is numerical, demonstrating exponential growth with n for the HP-L circuits. This growth is computed directly from the probability distributions of the measurement outcomes. Combined with the proven shift invariance, this supports the use of classical post-processing to extract the generator. The replacement of the QFT is thus justified by the numerical success in small instances of Shor's algorithm. In the revised version, we will expand the discussion on the Fisher information calculation and its numerical growth to strengthen the presentation. A general lower bound independent of the specific post-processor is indeed not derived here and would require substantial additional theoretical development. revision: partial

standing simulated objections not resolved
  • Rigorous analytic proof that the neural network post-processor scales with polynomial resources in n for arbitrary n.
  • Rigorous lower bound on the discrete Fisher information for HP-1 that guarantees recovery of the hidden subgroup with high probability independent of neural network training.

Circularity Check

0 steps flagged

No circularity; derivation rests on independent proof of shift invariance and separate numerical evidence

full rationale

The paper first identifies two properties used by the QFT (shift invariance and retention of hidden-subgroup information via discrete Fisher information). It then constructs the HP-L family and proves shift invariance directly from the circuit definition. Fisher information is quantified from first principles and its exponential growth is shown numerically for the HP-1 instance. The claim that the O(n) HP-1 circuit plus neural-net post-processing can replace the QFT in Shor's algorithm is presented strictly as a numerical demonstration on small instances, not as a first-principles derivation or a fitted parameter renamed as a prediction. No self-citation is load-bearing, no ansatz is smuggled, and no quantity is defined in terms of itself. The overall chain therefore remains self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

2 free parameters · 1 axioms · 0 invented entities

The paper relies on standard quantum circuit axioms and the definition of discrete Fisher information; the HP-L family is constructed from existing gates rather than introducing new physical entities. The choice of circuit depth parameter L and the neural-net architecture constitute free parameters whose values are selected to achieve the reported performance.

free parameters (2)
  • L
    Integer depth parameter controlling the number of controlled-phase layers; L=1 yields the O(n) circuit used in the Shor's demonstration.
  • neural_net_architecture
    Hyperparameters of the classical neural network used for post-processing; chosen to achieve efficient extraction in the numerical experiments.
axioms (1)
  • domain assumption The discrete Fisher information quantifies the retained information about the hidden subgroup generator in the measurement outcomes.
    Invoked to justify that exponentially growing Fisher information is sufficient for successful post-processing.

pith-pipeline@v0.9.0 · 5702 in / 1447 out tokens · 43487 ms · 2026-05-19T20:32:19.389950+00:00 · methodology

discussion (0)

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

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

38 extracted references · 38 canonical work pages · 5 internal anchors

  1. [1]

    D. R. Simon, On the power of quantum computation, SIAM Journal on Computing26, 1474 (1997)

    work page 1997

  2. [2]

    P. W. Shor, Algorithms for quantum computation: Dis- crete logarithms and factoring, inProceedings 35th An- nual Symposium on Foundations of Computer Science (IEEE, 1994) pp. 124–134

    work page 1994

  3. [3]

    P. W. Shor, Polynomial-time algorithms for prime factor- ization and discrete logarithms on a quantum computer, SIAM Journal on Computing26, 1484 (1997)

    work page 1997

  4. [4]

    A. Y. Kitaev, Quantum measurements and the abelian stabilizer problem (1995), arXiv:quant-ph/9511026 [quant-ph]

    work page internal anchor Pith review Pith/arXiv arXiv 1995

  5. [5]

    Jozsa, Quantum factoring, discrete logarithms, and the hidden subgroup problem, Computing in Science & Engineering3, 34 (2001)

    R. Jozsa, Quantum factoring, discrete logarithms, and the hidden subgroup problem, Computing in Science & Engineering3, 34 (2001)

    work page 2001

  6. [6]

    The Hidden Subgroup Problem - Review and Open Problems

    C. Lomont, The hidden subgroup problem: Review and open problems (2004), arXiv:quant-ph/0411037 [quant- ph]

    work page internal anchor Pith review Pith/arXiv arXiv 2004

  7. [7]

    F. Liu, K. Bian, F. Meng, W. Zhang, and O. Dahlsten, Information compression via hidden subgroup quantum autoencoders, npj Quantum Information10, 74 (2024)

    work page 2024

  8. [8]

    Y. Kim, A. Eddins, S. Anand, K. X. Wei, E. Van Den Berg, S. Rosenblatt, H. Nayfeh, Y. Wu, M. Zale- tel, K. Temme,et al., Evidence for the utility of quan- tum computing before fault tolerance, Nature618, 500 (2023)

    work page 2023

  9. [9]

    Google Quantum AI and Collaborators, Quantum error correction below the surface code threshold, Nature638, 920 (2025)

    work page 2025

  10. [10]

    D. Gao, D. Fan, C. Zha,et al., Establishing a new bench- mark in quantum computational advantage with 105- qubit Zuchongzhi 3.0 processor, Phys. Rev. Lett.134, 090601 (2025)

    work page 2025

  11. [11]

    Takagi, S

    R. Takagi, S. Endo, S. Minagawa, and M. Gu, Funda- mental limits of quantum error mitigation, npj Quantum Information8, 114 (2022)

    work page 2022

  12. [12]

    Takagi, H

    R. Takagi, H. Tajima, and M. Gu, Universal sampling lower bounds for quantum error mitigation, Physical Re- view Letters131, 210602 (2023)

    work page 2023

  13. [13]

    Demonstrating Record Fidelity for the Quantum Fourier Transform

    P. Aumann, M. Fellner, D. Alber, M. Cykiert, C. Fleck- enstein, R. ter Hoeven, L. Stenzel, R. J. Valencia- Tortora, and W. Lechner, Demonstrating record fi- delity for the quantum fourier transform, arXiv preprint arXiv:2604.12465 (2026)

    work page internal anchor Pith review Pith/arXiv arXiv 2026

  14. [14]

    An approximate Fourier transform useful in quantum factoring

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

    work page internal anchor Pith review Pith/arXiv arXiv 2002

  15. [15]

    Park and D

    B. Park and D. Ahn, Reducing cnot count in quantum fourier transform for the linear nearest-neighbor archi- tecture, Scientific Reports13, 8638 (2023)

    work page 2023

  16. [16]

    Bäumeret al., Quantum fourier transform using dy- namic circuits, arXiv preprint arXiv:2403.09514 (2024)

    E. Bäumeret al., Quantum fourier transform using dy- namic circuits, arXiv preprint arXiv:2403.09514 (2024)

    work page arXiv 2024

  17. [17]

    W. Tanget al., CutQC: using small quantum comput- ers for large quantum circuit evaluations, inProceedings of the 26th ACM International Conference on Architec- tural Support for Programming Languages and Operating Systems(2021) pp. 473–486

    work page 2021

  18. [18]

    T.Peng, A.W.Harrow, M.Ozols,andX.Wu,Simulating large quantum circuits on a small quantum computer, Phys. Rev. Lett.125, 150504 (2020)

    work page 2020

  19. [19]

    Zaheer, S

    M. Zaheer, S. Kottur, S. Ravanbakhsh, B. Poczos, R. R. Salakhutdinov, and A. J. Smola, Deep sets, Advances in neural information processing systems30(2017)

    work page 2017

  20. [20]

    M. A. Nielsen and I. L. Chuang,Quantum Computation and Quantum Information(Cambridge University Press, 2000)

    work page 2000

  21. [21]

    D. G. Chapman and H. Robbins, Minimum variance es- timation without regularity assumptions, The Annals of Mathematical Statistics , 581 (1951)

    work page 1951

  22. [22]

    J. M. Hammersley, On estimating restricted parame- ters, Journal of the Royal Statistical Society. Series B (Methodological)12, 192 (1950)

    work page 1950

  23. [23]

    Towards a Neural Statistician

    H. Edwards and A. Storkey, Towards a neural statisti- cian, arXiv preprint arXiv:1606.02185 (2016)

    work page internal anchor Pith review Pith/arXiv arXiv 2016

  24. [24]

    Sutskever, O

    I. Sutskever, O. Vinyals, and Q. V. Le, Sequence to se- quence learning with neural networks, inAdvances in neural information processing systems, Vol. 27 (2014)

    work page 2014

  25. [25]

    Wiseman and A

    S. Wiseman and A. M. Rush, Sequence-to-sequence learning as beam-search optimization, inProceedings of the 2016 Conference on Empirical Methods in Natural Language Processing(2016) pp. 1296–1306

    work page 2016

  26. [26]

    Ramezani, S

    M. Ramezani, S. A. Zargar, S. Salami, A. Bahrampour, and A. Bahrampour, Learning Hamiltonians foro(1) oracle-query quantum state preparation, arXiv preprint arXiv:2512.19181 (2025)

    work page arXiv 2025

  27. [27]

    M. Yu, A. T. Calvino, M. Soeken, and G. De Micheli, Back-end-aware fault-tolerant quantum oracle synthesis, inProceedings of the 30th Asia and South Pacific Design Automation Conference (ASP-DAC)(IEEE, 2025) pp. 930–937

    work page 2025

  28. [28]

    Chen and C

    I.-T. Chen and C. Gupta, Towards efficient automatic oracle synthesis and resource estimation using QDK and QIR, in2023 IEEE International Conference on Quan- 6 tum Computing and Engineering (QCE)(IEEE, 2023)

    work page 2023

  29. [29]

    Carolan, C

    J. Carolan, C. Harrold, C. Sparrow, E. Martín-López, N. J. Russell, J. W. Silverstone, P. J. Shadbolt, N. Mat- suda, M. Oguma, M. Itoh,et al., Universal linear optics, Science349, 711 (2015)

    work page 2015

  30. [30]

    P. Kok, W. J. Munro, K. Nemoto, T. C. Ralph, J. P. Dowling, and G. J. Milburn, Linear optical quantum computing with photonic qubits, Rev. Mod. Phys.79, 135 (2007)

    work page 2007

  31. [31]

    Saffman, T

    M. Saffman, T. G. Walker, and K. Mølmer, Quantum information with Rydberg atoms, Reviews of modern physics82, 2313 (2010)

    work page 2010

  32. [32]

    S. J. Evered, D. Bluvstein, M. Kalinowski, S. Ebadi, T. Manovitz, H. Zhou, S. H. Li, A. A. Geim, T. T. Wang, N. Maskara,et al., High-fidelity parallel entangling gates on a neutral-atom quantum computer, Nature622, 268 (2023)

    work page 2023

  33. [33]

    Mohan, J

    M. Mohan, J. De Hond, and S. Kokkelmans, Parametrized multiqubit gates for neutral-atom quantum platforms, Physical Review Applied23, 054074 (2025)

    work page 2025

  34. [34]

    Leibfried, B

    D. Leibfried, B. DeMarco, V. Meyer, D. Lucas, M. Bar- rett, J. Britton, W. M. Itano, B. Jelenković, C. Langer, T. Rosenband, and D. J. Wineland, Experimental demonstration of a robust, high-fidelity geometric two ion-qubit phase gate, Nature422, 412 (2003)

    work page 2003

  35. [35]

    T. R. Tan, J. P. Gaebler, R. Bowler, Y. Lin, J. D. Jost, D. Leibfried, and D. J. Wineland, Demonstration of a dressed-state phase gate for trapped ions, Phys. Rev. Lett.110, 263002 (2013)

    work page 2013

  36. [36]

    L. M. Vandersypen and I. L. Chuang, NMR techniques for quantum control and computation, Reviews of Mod- ern Physics76, 1037 (2004)

    work page 2004

  37. [37]

    Ettinger, P

    M. Ettinger, P. Høyer, and E. Knill, The quantum query complexity of the hidden subgroup problem is polyno- mial, Information Processing Letters91, 43 (2004)

    work page 2004

  38. [38]

    i nX i=1 nX k=n−s+1 ˜θikxick # X y1,...,yn−s∈{0,1} exp  i nX i=1 n−sX j=1 ˜θijxiyj   2 (C16) 12 = 1 2n2n−s exp

    L. Grafakos,Classical Fourier Analysis, 3rd ed. (Springer, 2014). APPENDIX A. Hidden Subgroup Problem and Fourier Sampling For completeness, this section reviews the standard quantum algorithm for solving the Hidden Subgroup Problem (HSP) over finite abelian groups [4–6]. Formally, the HSP is defined as follows: Definition 3(Hidden Subgroup Problem).Given...

    work page 2014