Shor's algorithm requires Fanout

Lucas Gretta; Malvika Raj Joshi

Shor's algorithm requires Fanout

T0 review · reviewed 2026-08-11 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Constant-depth QFT exists only if fanout does.

desk verdict Resolves the 2006 QFT/fanout question with a clean reduction, but the core felinity-to-fanout engine is in an unpublished companion paper; the stress-test's cancellation objection is wrong. read the letter →

arxiv 2608.06703 v2 pith:GOWXQACY submitted 2026-08-07 quant-ph cs.CC

Lucas Gretta , Malvika Raj Joshi This is my paper · ORCID

classification quant-phcs.CC MSC 68Q1281P68 PACS 03.67.Lx

keywords Shor'salgorithmQuantumFouriertransformFanoutgateQAC^0Constant-depthcircuitsFelinitycomplexitytheoryNISQ

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper establishes that an approximate constant-depth circuit for the quantum Fourier transform ($\mathsf{QFT}_q$) can be converted, for any $n$-qubit modulus $q$, into a constant-depth circuit for the $n$-qubit fanout gate. Since the opposite direction was already known, the paper concludes that $\mathsf{QFT}_q$ belongs to the constant-depth class $\mathsf{QAC}^0$ if and only if $\mathsf{FANOUT}_n$ does, resolving a 2006 open question about whether fanout is really necessary for constant-depth Fourier transforms. For the power-of-two modulus used by Shor's algorithm, the paper gives an explicit circuit: a single QFT on $2^n$ qubits plus $O(1)$ two-qubit local gates approximate fanout to arbitrary fixed precision. The result matters because it locates the genuine bottleneck for shallow quantum computation in the fanout operation rather than in the Fourier transform itself.

What carries the argument

The felinity functional $F_n(\rho)=2\sum_{y\in\{0,1\}^n}\langle y|\rho|y\rangle\langle y|X^{\otimes n}\rho X^{\otimes n}|y\rangle$, which measures how much weight a state spreads between complementary bit strings, is the quantity that carries the argument. The proof engineers a state whose QFT has constant amplitude on two complementary frequencies, so after the approximate gate the state has non-negligible felinity; the cited bridge result then converts non-negligible felinity into constant-depth fanout. Two concrete pieces of machinery do the constructing: the Dirichlet kernel identity $D_q(L)=e^{i\pi(L-1)/q}\sin(L\pi/q)/\sin(\pi/q)$, which gives the constant amplitudes, and, for $q=2^n$, a truncated version of the known constant-depth decrement gate, implemented with controlled-phase gates, which approximates fanout directly.

What would settle it

Produce a $\mathsf{QAC}^0$ circuit family that approximates $\mathsf{QFT}_q$ for some $q$ to non-negligible fidelity and, with the same techniques, a proof that $\mathsf{FANOUT}_n\notin\mathsf{QAC}^0$; the paper's Theorem 1.1 says these two objects cannot coexist. A smaller-scale check is to simulate Lemma 2.3's circuit with an ideal $\mathsf{QFT}_{2^n}$ on $n$ qubits and verify that the output fidelity to $|1\cdots1\rangle$ reaches $1-4^{1-k}$; a shortfall would show the circuit analysis is wrong.

Watch

Extended reading notes

Core claim

The paper's central claim is Theorem 1.1: for any $q$ and $n=\lceil\log_2 q\rceil$, if a $\mathsf{QAC}^0$ circuit approximates $\mathsf{QFT}_q$ to non-negligible fidelity $\delta$ (at least a polynomial inverse in $n$), then $\mathsf{FANOUT}_n$ is in $\mathsf{QAC}^0$. Because the reverse direction—fanout to constant-depth QFT—is already known, the corollary is the equivalence $\mathsf{QFT}_q\in\mathsf{QAC}^0\iff\mathsf{FANOUT}_n\in\mathsf{QAC}^0$. The proof constructs a product state whose ideal QFT has constant amplitude on two frequencies whose binary forms are complementary ($2^n-1$ and $2^n$), runs the approximate QFT alongside reflections about Fourier basis states, and extracts a state with felinity $\Omega(\delta^2)$; a cited companion result asserts that any $\mathsf{QAC}^0$ circuit preparing an $n$-qubit state with felinity at least $n^{-c}$ implies $\mathsf{FANOUT}_n\in\mathsf{QAC}^0$. For the Shor modulus $q=2^n$, Lemma 2.3 gives a depth-$k+2$ circuit that uses $\mathsf{QFT}_{2^n}^\dagger$, Hadamards, and $k$ controlled-phase gates to approximate $\mathsf{FANOUT}_n$ to fidelity at least $1-4^{1-k}$.

Load-bearing premise

The load-bearing premise is an unpublished result from a companion paper: any constant-depth circuit that prepares a state with 'felinity' at least a polynomial inverse in $n$ can be converted into a constant-depth fanout circuit; if that conversion fails, the main equivalence collapses.

Editorial extensions

If this is right

If any constant-depth approximate QFT circuit exists, then constant-depth fanout exists, so quantum circuit lower bounds for fanout would immediately become lower bounds for approximate QFT.
For Shor's power-of-two modulus, a single $\mathsf{QFT}_{2^n}$ plus $O(1)$ local two-qubit gates gives fanout to fidelity $1-4^{1-k}$, meaning NISQ devices with good constant-depth QFTs already have the raw material for fanout.
The approximation needed is only non-negligible fidelity $\delta\ge n^{-O(1)}$, far weaker than the standard $(1-\varepsilon)$ approximation, so the equivalence covers very noisy QFT implementations.
The 2006 question of whether fanout is necessary for constant-depth QFT is answered affirmatively, conditional on the cited felinity-to-fanout theorem.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

If the cited felinity-to-fanout theorem is eventually proven, the same construction likely yields a quantitative tradeoff: a QFT approximation with fidelity $\delta$ produces fanout with parameters controlled by $\delta$, so hardware noise thresholds for the two operations should track each other.
The $\Omega(\delta^2)$ felinity bound could be tested numerically on small registers by applying the construction to simulated noisy QFT circuits; finding a faster decay would suggest the bound is loose.
A natural extension is to replace $\mathsf{QFT}_q$ by more general constant-depth channels that approximate it, and ask whether the felinity-to-fanout implication survives under depolarizing or dephasing noise—this would give a NISQ-era 'requires fanout' statement per device.
Because the Shor-case circuit uses one QFT plus $O(1)$ gates, an experimental demonstration on a small register comparing the output fidelity to $1-4^{1-k}$ would directly expose whether a device's QFT gate is faithful enough to serve as fanout hardware.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Colleague,

The headline is that this note proves QFT_q in QAC^0 iff FANOUT_n in QAC^0, resolving the Fang et al. open question, and the proof is more believable than the stress-test suggests. The specific objection about Eq. (2.18)-(2.23) does not hold up: the identity term in R_b vanishes because the measured w-register state |1-b,b> is orthogonal to the EPR state. So the step from (2.19) to (2.20) is exact, not a dropped term. The algebra from there to the Omega(delta^2) felinity bound checks out.

What's genuinely new: the reduction from a delta-approximate QFT gate to a non-negligible felinity state is a nice trick, and the companion result that high felinity implies fanout is the engine. The note also gives a clean local approximation of fanout for power-of-two moduli (Lemma 2.3), which is a useful addition for the NISQ discussion. The writing is clear and the logic is coherent.

The soft spot is exactly what the reader flagged: the engine is cited to [GGJ26a] (felinity-to-fanout) and the reflection/amplification tools to [GGJ26b]. Both are unpublished companion papers by the same group. Nothing in this note independently verifies those claims. That makes the result conditional rather than self-contained. It is not a fatal flaw in the reduction itself, but it means a referee cannot check the central step without the companions.

Minor points: the notion of 'non-negligible fidelity' is weaker than the usual approximation, which is fine but should be explicit (it is). The appendix's exact QFT from fanout is a sketch, not a full proof. And the acknowledgement of ChatGPT is not an issue.

Bottom line: this is a serious paper worth a serious referee. If the companions are posted or their key theorems proven in the paper, I would accept it. As it stands, I would send it out but require the authors to make the dependencies publicly available.

Recommendation: send to peer review, not desk reject. The stress-test's main objection is wrong.

Circularity Check

2 steps flagged · score 8.0 of 10

The central implication is delegated to same-author companion papers [GGJ26a] and [GGJ26b]; no proof of the felinity=>FANOUT engine is given in this note.

self citation load bearing [Proof of Theorem 1.1, final paragraph after Eq. (2.23)]
"From [GGJ26a], preparing |ψ′⟩inQAC 0 impliesFANOUT n ∈QAC 0."

This is the decisive step of Theorem 1.1: the high-felinity state |ψ′⟩ is only useful because an unstated, unpublished companion paper by the same authors asserts that high felinity implies FANOUT_n in QAC^0. The target implication QFT_q∈QAC^0 ⇒ FANOUT_n∈QAC^0 therefore does not follow from the equations in this manuscript; it follows from an unverified self-citation. If [GGJ26a] were removed, the proof stops exactly at the point where the claimed conclusion is drawn.
self citation load bearing [Theorem 1.1 proof, paragraph before Eq. (2.18); also Lemma 2.2 proof]
"For any state |φ⟩preparable inQAC 0, it is known that the reflection about it,I−2|φ⟩ ⟨φ|, isalso implementable inQAC 0 (Fact 3.9 [GGJ26b])."

The construction of |ν_q⟩ = R′_0 R′_1 |ψ_q⟩|EPR⟩ requires the reflections R′_b to be implementable in QAC^0. This fact, together with the O(1)-depth amplification used in Lemma 2.2 (Cor. 3.16 [GGJ26b]), is cited to another unpublished companion by the same authors. Without these imported primitives, the high-felinity state cannot be shown preparable in QAC^0, so the bridge to [GGJ26a] itself rests on a second unverified self-citation.

full rationale

The paper contains a genuine construction: it attempts to show that an approximate QFT_q gate can prepare a state with felinity Ω(δ²), and the Shor-modulus Lemma 2.3 is self-contained. The apparent cancellation in Eqs. (2.18)–(2.23) is not a circularity, because the identity term of R_b carries the factor ⟨(1−b)b|EPR⟩=0 and therefore vanishes; that is a purely mathematical check, not a circularity. The circularity is the self-citation chain: the two external facts that actually deliver the theorem—felinity⇒FANOUT ([GGJ26a]) and the QAC^0 reflection/amplification toolbox ([GGJ26b])—are unpublished companions by the same authors and are not proved or independently verified here. Since Theorem 1.1's conclusion is drawn directly from those citations, the central claim reduces to an unverified self-citation chain rather than to a derivation contained in this note. Score 8: the result is forced by the self-citation chain, though not by definitional equivalence.

Assumptions & free parameters 0 free parameters · 5 assumptions · 1 invented entities

The paper's central theorem depends on multiple unpublished or recently-cited results by the same authors. No free parameters are fitted; the construction parameters (gamma, k, l) are chosen existentially. The primary invented entity is 'felinity', a measure defined in the companion paper [GGJ26a].

assumptions (5)

ad hoc to paper Felinity-to-fanout: any QAC^0 circuit preparing a state with felinity >= n^{-c} implies FANOUT_n in QAC^0 (from [GGJ26a]).
The central reduction engine; cited to an unpublished companion paper by the same authors, no proof included in this note.
ad hoc to paper Reflections about QAC^0-preparable states are implementable in QAC^0 (Fact 3.9 of [GGJ26b]).
Used to build the reflections R'_b; from an unpublished companion paper, no independent verification available.
ad hoc to paper Exact amplitude amplification in O(1) depth for QAC^0 states (Cor 3.16 of [GGJ26b]).
Used to amplify the approximate Fourier state in Lemma 2.2; from unpublished companion paper.
domain assumption QAC^0 contains TC^0 with many copies of the input ([GMW26]), used to implement comparators in QAC^0.
Needed in Lemma 2.2 to prepare high-weight prefix states; the cited paper is recent and the claim is surprising given parity lower bounds, but the 'many copies' qualifier may make it consistent.
standard math Dirichlet kernel identity D_q(L) = e^{i pi (L-1)/q} sin(L pi/q)/sin(pi/q), Eq. (2.2).
Used throughout for Fourier amplitude estimates.

invented entities (1)

Felinity
purpose: A complexity measure of a quantum state used to trigger the fanout implication; defined in [GGJ26a] as F_n(rho) = 2 sum_y <y|rho|y><y|X^{otimes n} rho X^{otimes n}|y>.
Introduced in the authors' companion paper; no falsifiable external handle independent of that paper.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Shor's algorithm requires Fanout." pith.science (2026). https://pith.science/paper/GOWXQACY

@misc{pith2026260806703,
  author       = {Pith},
  title        = {Pith review of: Shor's algorithm requires Fanout},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/GOWXQACY}},
  note         = {Machine review of arXiv:2608.06703}
}

abstract

Shor's algorithm is a canonical quantum supremacy target whose core operation relies on the Quantum Fourier Transform (QFT). In this note, we resolve an open question of Fang, Fenner, Green, Homer and Zhang from 2006 by showing that approximating QFT in constant depth, for any $n$-qubit modulus, necessarily requires the $n$-qubit Fanout operation. Formally, let $\mathsf{QFT}_q$ be the gate acting on $n = \lceil \log q \rceil$ qubits that computes the QFT under modulus $q$. It is known that any $n$-qubit $\mathsf{QFT}_q$ can be implemented in constant depth using $\mathsf{FANOUT}_n$, i.e. $\mathsf{QFT}_q \in \mathsf{QAC}^0_f$. We prove the converse by using a $\mathsf{QFT}_q$ gate to construct a state of "non-negligible felinity". Consequently, $\mathsf{QFT}_q \in \mathsf{QAC}^0 \iff \mathsf{FANOUT}_n \in \mathsf{QAC^0}$. In the case of $q = 2^n$, such as in Shor's, we approximate $\mathsf{FANOUT}_n$ using a single $\mathsf{QFT}_{2^n}$ gate and $O(1)$ two-qubit local gates, thus tying the feasibility of realizing Shor's algorithm with NISQ circuits to that of Fanout.

Review history (2 revisions) →

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

69 extracted references · 5 linked inside Pith

[1]

2021 , biburl =

Gregory Rosenthal , title =. 2021 , biburl =

2021
[2]

2024 , biburl =

Shivam Nadimpalli and Natalie Parham and Francisca Vasconcelos and Henry Yuen , title =. 2024 , biburl =

2024
[3]

2025 , biburl =

Daniel Grier and Jackson Morris , title =. 2025 , biburl =

2025
[4]

Electron

Cristopher Moore , title =. Electron. Colloquium Comput. Complex. , volume =. 1999 , biburl =

1999
[5]

Theory Comput

Peter Hoyer and Robert Spalek , title =. Theory Comput. , volume =. 2005 , url =. doi:10.4086/TOC.2005.V001A005 , timestamp =

doi:10.4086/toc.2005.v001a005 2005
[6]

Yasuhiro Takahashi and Seiichiro Tani , title =. Comput. Complex. , volume =. 2016 , biburl =

2016
[7]

2025 , biburl =

Anurag Anshu and Yangjing Dong and Fengning Ou and Penghui Yao , title =. 2025 , biburl =

2025
[8]

CoRR , volume =

Ben Foxman and Natalie Parham and Francisca Vasconcelos and Henry Yuen , title =. CoRR , volume =. 2025 , biburl =

2025

Show all 69 references

[9]

Learning shallow quantum circuits with many-qubit gates , booktitle =

Francisco Vasconcelos and Hsin. Learning shallow quantum circuits with many-qubit gates , booktitle =
[10]

2410.15822 , archivePrefix=

Jinge Bao and Francisco Escudero-Gutiérrez , year=. 2410.15822 , archivePrefix=

arXiv
[11]

2005.12169 , archivePrefix=

Daniel Padé and Stephen Fenner and Daniel Grier and Thomas Thierauf , year=. 2005.12169 , archivePrefix=

2005 arXiv
[12]

Fenner and Daniel Grier and Daniel Pad

Stephen A. Fenner and Daniel Grier and Daniel Pad. Tight bounds on depth-2 QAC-circuits computing parity , journal =. 2025 , url =. doi:10.48550/ARXIV.2504.06433 , eprinttype =. 2504.06433 , timestamp =

2025 doi arXiv
[13]

Fenner and Frederic Green and Steven Homer and Yong Zhang , title =

Maosen Fang and Stephen A. Fenner and Frederic Green and Steven Homer and Yong Zhang , title =. Quantum Inf. Comput. , volume =. 2006 , biburl =

2006
[14]

Quantum Inf

Frederic Green and Steven Homer and Cristopher Moore and Christopher Pollett , title =. Quantum Inf. Comput. , volume =. 2002 , biburl =

2002
[15]

Browne and Elham Kashefi and Simon Perdrix , title =

Dan E. Browne and Elham Kashefi and Simon Perdrix , title =. 2010 , biburl =

2010
[16]

Anne Broadbent and Elham Kashefi , title =. Theor. Comput. Sci. , volume =. 2009 , biburl =

2009
[17]

Fenner , year=

Stephen A. Fenner , year=. quant-ph/0309163 , archivePrefix=

arXiv
[18]

Nathan Linial and Yishay Mansour and Noam Nisan , title =. J. 1993 , biburl =

1993
[19]

Debajyoti Bera , title =. Inf. Process. Lett. , volume =. 2011 , biburl =

2011
[20]

O'Donnell, Ryan , year=
[21]

Johan Hastad , title =. Adv. Comput. Res. , volume =. 1989 , biburl =

1989
[22]

An entropy proof of the switching lemma and tight bounds on the decision-tree size of

Rossman, Benjamin , year=. An entropy proof of the switching lemma and tight bounds on the decision-tree size of
[23]

Furst and James B

Merrick L. Furst and James B. Saxe and Michael Sipser , title =. Math. Syst. Theory , volume =. 1984 , biburl =

1984
[24]

Annals of Pure and Applied Logic , year =

Miklos Ajtai , title =. Annals of Pure and Applied Logic , year =
[25]

Separating the Polynomial-Time Hierarchy by Oracles (Preliminary Version) , booktitle =

Andrew Chi. Separating the Polynomial-Time Hierarchy by Oracles (Preliminary Version) , booktitle =. 1985 , biburl =

1985
[26]

1994 , institution=

A switching lemma primer , author=. 1994 , institution=

1994
[27]

Avishay Tal , title =
[28]

2019 , biburl =

Adam Bene Watts and Robin Kothari and Luke Schaeffer and Avishay Tal , title =. 2019 , biburl =

2019
[29]

Mathematical Notes of the Academy of Sciences of the USSR , volume=

Lower bounds on the size of bounded depth circuits over a complete basis with logical addition , author=. Mathematical Notes of the Academy of Sciences of the USSR , volume=. 1987 , publisher=

1987
[30]

Proceedings of the nineteenth annual ACM symposium on Theory of computing , pages=

Algebraic methods in the theory of lower bounds for Boolean circuit complexity , author=. Proceedings of the nineteenth annual ACM symposium on Theory of computing , pages=
[31]

and Tan, Li-Yang , title =

Hastad, Johan and Rossman, Benjamin and Servedio, Rocco A. and Tan, Li-Yang , title =. 2017 , issue_date =. doi:10.1145/3095799 , journal =

2017 doi
[32]

2601.03243 , archivePrefix=

Daniel Grier and Jackson Morris and Kewen Wu , year=. 2601.03243 , archivePrefix=
[33]

Quantum Computers Can Search Rapidly by Using Almost Any Transformation , author =. Phys. Rev. Lett. , volume =. 1998 , month =. doi:10.1103/PhysRevLett.80.4329 , url =

1998 doi
[34]

arXiv: Quantum Physics , year=

Quantum Amplitude Amplification and Estimation , author=. arXiv: Quantum Physics , year=
[35]

Bennett, C. H. , title =. 1973 , issue_date =. doi:10.1147/rd.176.0525 , journal =

1973 doi
[36]

2026 , eprint=

Improved Lower Bounds for QAC0 , author=. 2026 , eprint=

2026
[37]

2026 , eprint=

Constant-Depth Unitary Preparation of Dicke States , author=. 2026 , eprint=

2026
[38]

2013 , publisher=

Bell's theorem, quantum theory and conceptions of the universe , author=. 2013 , publisher=

2013
[39]

Nature photonics , volume=

Advances in quantum metrology , author=. Nature photonics , volume=. 2011 , publisher=

2011
[40]

New Journal of Physics , volume=

Quantum metrology with Dicke squeezed states , author=. New Journal of Physics , volume=. 2014 , publisher=

2014
[41]

Physical Review Letters , volume=

14-qubit entanglement: Creation and coherence , author=. Physical Review Letters , volume=. 2011 , publisher=

2011
[42]

Nature , volume=

Optimization by decoded quantum interferometry , author=. Nature , volume=. 2025 , publisher=

2025
[43]

Information Processing Letters , volume=

Linear-size constant-depth polylog-threshold circuits , author=. Information Processing Letters , volume=. 1991 , publisher=

1991
[44]

2006 , publisher=

Grinstead and Snell's introduction to probability , author=. 2006 , publisher=

2006
[45]

2016 , publisher=

The probabilistic method , author=. 2016 , publisher=

2016
[46]

William Feller , title =
[47]

2017 , publisher=

Probability and computing: Randomization and probabilistic techniques in algorithms and data analysis , author=. 2017 , publisher=

2017
[48]

SIAM Journal on Computing , volume=

Constant depth reducibility , author=. SIAM Journal on Computing , volume=. 1984 , publisher=

1984
[49]

Journal of Computer and System Sciences , volume=

Uniform constant-depth threshold circuits for division and iterated multiplication , author=. Journal of Computer and System Sciences , volume=. 2002 , publisher=

2002
[50]

Computational Complexity , volume=

Reducing the complexity of reductions , author=. Computational Complexity , volume=. 2001 , publisher=

2001
[51]

SIAM Journal on Computing , volume=

On the correlation of parity and small-depth circuits , author=. SIAM Journal on Computing , volume=. 2014 , publisher=

2014
[52]

Physics Physique Fizika , volume=

On the einstein podolsky rosen paradox , author=. Physics Physique Fizika , volume=. 1964 , publisher=

1964
[53]

2009 , publisher=

Computational complexity: a modern approach , author=. 2009 , publisher=

2009
[54]

Quantum advantage with shallow circuits , volume=

Bravyi, Sergey and Gosset, David and König, Robert , year=. Quantum advantage with shallow circuits , volume=. Science , publisher=. doi:10.1126/science.aar3106 , number=

doi
[55]

A theorem on probabilistic constant depth computations , booktitle =

Mikl. A theorem on probabilistic constant depth computations , booktitle =
[56]

2026 , eprint=

Parity QAC0 QAC0 is Fourier-Concentrated , author=. 2026 , eprint=

2026
[57]

Physical review , volume=

Coherence in spontaneous radiation processes , author=. Physical review , volume=. 1954 , publisher=

1954
[58]

Reviews of Modern Physics , volume=

Programmable quantum simulations of spin systems with trapped ions , author=. Reviews of Modern Physics , volume=. 2021 , publisher=

2021
[59]

CoRR , volume =

Gregory Rosenthal , title =. CoRR , volume =. 2021 , url =. 2111.07992 , timestamp =

2021 arXiv
[60]

PRX Quantum , volume =

Resilience of Quantum Random Access Memory to Generic Noise , author =. PRX Quantum , volume =. 2021 , month =. doi:10.1103/PRXQuantum.2.020311 , url =

2021 doi
[61]

and Foxman, Ben and Girvin, Steven M

Xu, Shifan and Hann, Connor T. and Foxman, Ben and Girvin, Steven M. and Ding, Yongshan , title =. 2023 , isbn =. doi:10.1145/3613424.3614270 , booktitle =

2023
[62]

8th Innovations in Theoretical Computer Science Conference (ITCS 2017) , pages =

Kerenidis, Iordanis and Prakash, Anupam , title =. 8th Innovations in Theoretical Computer Science Conference (ITCS 2017) , pages =. 2017 , volume =. doi:10.4230/LIPIcs.ITCS.2017.49 , annote =

2017 doi
[63]

q-means: A quantum algorithm for unsupervised machine learning , url =

Kerenidis, Iordanis and Landman, Jonas and Luongo, Alessandro and Prakash, Anupam , booktitle =. q-means: A quantum algorithm for unsupervised machine learning , url =
[64]

and Watrous, J

Cleve, R. and Watrous, J. , booktitle=. Fast parallel circuits for the quantum Fourier transform , year=
[65]

2011 , publisher=

Fourier analysis: an introduction , author=. 2011 , publisher=

2011
[66]

Scientific reports , volume=

Demonstration of Shor’s factoring algorithm for N= 21 on IBM quantum processors , author=. Scientific reports , volume=. 2021 , publisher=

2021
[67]

Shor, Peter W. , year=. Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer , volume=. SIAM Journal on Computing , publisher=. doi:10.1137/s0097539795293172 , number=

doi
[68]

2026 , eprint=

Polylogarithmic-Weight Dicke States in QAC ^0 and Arbitrary Symmetric States in QAC ^0_f , author=. 2026 , eprint=

2026
[69]

2003 , eprint=

Exact quantum Fourier transforms and discrete logarithm algorithms , author=. 2003 , eprint=

2003

Pith tools

Reviewed August 11, 2026 · model on record in the stance chip above.

[1] [1]

2021 , biburl =

Gregory Rosenthal , title =. 2021 , biburl =

2021

[2] [2]

2024 , biburl =

Shivam Nadimpalli and Natalie Parham and Francisca Vasconcelos and Henry Yuen , title =. 2024 , biburl =

2024

[3] [3]

2025 , biburl =

Daniel Grier and Jackson Morris , title =. 2025 , biburl =

2025

[4] [4]

Electron

Cristopher Moore , title =. Electron. Colloquium Comput. Complex. , volume =. 1999 , biburl =

1999

[5] [5]

Theory Comput

Peter Hoyer and Robert Spalek , title =. Theory Comput. , volume =. 2005 , url =. doi:10.4086/TOC.2005.V001A005 , timestamp =

doi:10.4086/toc.2005.v001a005 2005

[6] [6]

Yasuhiro Takahashi and Seiichiro Tani , title =. Comput. Complex. , volume =. 2016 , biburl =

2016

[7] [7]

2025 , biburl =

Anurag Anshu and Yangjing Dong and Fengning Ou and Penghui Yao , title =. 2025 , biburl =

2025

[8] [8]

CoRR , volume =

Ben Foxman and Natalie Parham and Francisca Vasconcelos and Henry Yuen , title =. CoRR , volume =. 2025 , biburl =

2025