Shor's algorithm requires Fanout

• URL: http://arxiv.org/abs/2608.06703v2
• Date: Mon, 10 Aug 2026 17:30:15 GMT
• Title: Shor's algorithm requires Fanout
• Abstract summary: Shor's algorithm is a canonical quantum supremacy target whose core operation relies on the Quantum Fourier Transform (QFT)<n>We show that approximating QFT in constant depth, for any $n$-qubit modulus, necessarily requires the $n$-qubit Fanout operation.<n>We prove the converse by using a $mathsfQFT_q$ gate to construct a state of "non-negligible felinity"
• Score: 0.14323566945483496
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• QAC0 Can Prepare Every Logarithmic-Qubit State [1.4018975578160688]
  $mathsfQAC0$ is the class of constant-depth $mathrmpoly(n)$-ancilla circuits.<n>We show that every $O(log n)$-qubit state can be exactly and cleanly prepared by a $mathrmpoly(n)$-ancilla $mathsfQAC0$ circuit.
  arXiv  Detail & Related papers  (2026-09-15T16:35:52Z)
• Fanout Complexity of Symmetric Boolean Functions in $\mathsf{QAC}^0$ [7.883691246794115]
  Computing $mathttPARITY_n$ is equivalent to implementing $mathttFANOUT_(f)$ under $mathsfQAC0$ reductions.<n>We show that the answer is exactly the transition radius $(f)$: computing $f$ and implementing $mathttFANOUT_(f)$ are equivalent under $mathsfQAC0$ reductions.
  arXiv  Detail & Related papers  (2026-09-04T13:55:20Z)
• $\mathsf{QAC}^0$ Contains $\mathsf{TC}^0$ (with Many Copies of the Input) [0.9023122463034333]
  $mathsfQAC0$ is the class of constant-depth quantum circuits constructed from arbitrary single-qubit gates and generalized Toffoli gates.<n>We show that $mathsfQAC0$ circuits are significantly more powerful than their classical counterparts.
  arXiv  Detail & Related papers  (2026-01-06T18:40:44Z)
• A Faster Quantum Fourier Transform [0.0]
  We present anally improved algorithm for implementing the Quantum Fourier Transform (QFT) in both the exact and approximate settings.<n>We show that these costs can be reduced by leveraging a novel formulation of the QFT that recurses on two partitions of the qubits.
  arXiv  Detail & Related papers  (2025-01-19T06:18:52Z)
• Quantum Sabotage Complexity [0.7812210699650152]
  We show $mathsfQ(f_mathsfsab)$, the quantum query complexity of $f_mathsfsab$. We show that when $f$ is the Indexing function, $mathsfQ(f_mathsfsab)=Theta(sqrtmathsfsab)$, ruling out the possibility that $mathsfQ(f_mathsfsab)=Theta(sqrtmathsf
  arXiv  Detail & Related papers  (2024-08-22T17:57:58Z)
• Provably learning a multi-head attention layer [55.2904547651831]
  Multi-head attention layer is one of the key components of the transformer architecture that sets it apart from traditional feed-forward models. In this work, we initiate the study of provably learning a multi-head attention layer from random examples. We prove computational lower bounds showing that in the worst case, exponential dependence on $m$ is unavoidable.
  arXiv  Detail & Related papers  (2024-02-06T15:39:09Z)
• SQ Lower Bounds for Learning Bounded Covariance GMMs [46.289382906761304]
  We focus on learning mixtures of separated Gaussians on $mathbbRd$ of the form $P= sum_i=1k w_i mathcalN(boldsymbol mu_i,mathbf Sigma_i)$. We prove that any Statistical Query (SQ) algorithm for this problem requires complexity at least $dOmega (1/epsilon)$.
  arXiv  Detail & Related papers  (2023-06-22T17:23:36Z)
• Learning a Single Neuron with Adversarial Label Noise via Gradient Descent [50.659479930171585]
  We study a function of the form $mathbfxmapstosigma(mathbfwcdotmathbfx)$ for monotone activations. The goal of the learner is to output a hypothesis vector $mathbfw$ that $F(mathbbw)=C, epsilon$ with high probability.
  arXiv  Detail & Related papers  (2022-06-17T17:55:43Z)
• Low-degree learning and the metric entropy of polynomials [44.99833362998488]
  We prove that any (deterministic or randomized) algorithm which learns $mathscrF_nd$ with $L$-accuracy $varepsilon$ requires at least $Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon) satisfies the two-sided estimate $$c (1-varepsilon)2dlog
  arXiv  Detail & Related papers  (2022-03-17T23:52:08Z)
• On the Self-Penalization Phenomenon in Feature Selection [69.16452769334367]
  We describe an implicit sparsity-inducing mechanism based on over a family of kernels. As an application, we use this sparsity-inducing mechanism to build algorithms consistent for feature selection.
  arXiv  Detail & Related papers  (2021-10-12T09:36:41Z)
• Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
  We study the problem of PAC learning halfspaces on $mathbbRd$ with Massart noise under Gaussian marginals. Our results qualitatively characterize the complexity of learning halfspaces in the Massart model.
  arXiv  Detail & Related papers  (2021-08-19T16:16:48Z)
• StoqMA meets distribution testing [0.0]
  We provide a novel connection between $mathsfStoqMA$ and distribution testing via reversible circuits. We show that both variants of $mathsfStoqMA$ that without any ancillary random bit and with perfect soundness are contained in $mathsfNP$. Our results make a step towards collapsing the hierarchy $mathsfMA subseteq mathsfStoqMA subseteq mathsfSBP$ [BBT06], in which all classes are contained in $
  arXiv  Detail & Related papers  (2020-11-11T12:30:42Z)
• Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
  We study the problem of agnostic $Q$-learning with function approximation in deterministic systems. We show that if $delta = Oleft(rho/sqrtdim_Eright)$, then one can find the optimal policy using $Oleft(dim_Eright)$.
  arXiv  Detail & Related papers  (2020-02-17T18:41:49Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.