Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Physical Review A

Performance scaling of Shor's algorithm with a banded quantum Fourier transform

Yunseong Nam, R. Blümel

Published Oct 23, 2012• 14 citations
Publisher

Abstract

In excellent agreement with our numerical simulations of Shor's algorithm, equipped with a truncated quantum Fourier transform of bandwidth $b$, we find that its performance scales $\ensuremath{\sim}$${2}^{\ensuremath{-}{\ensuremath{\xi}}_{b}n}$, where $n$ is the number of qubits, ${\ensuremath{\xi}}_{b}=1.1\ifmmode\times\else\texttimes\fi{}{2}^{\ensuremath{-}2b}$, and the bandwidth $b$ is the number of quantum states coupled by the quantum Fourier transform. Nonexponential behavior is observed for small $n$ and explained analytically. The large-$n$ exponential scaling implies that $b=7$ is sufficient to operate a 1000-qubit quantum computer running Shor's algorithm on the $95%$ performance level and implies hardware savings of the order of half a million rotation gates.

DOI
10.1103/physreva.86.044303

Related papers

Scaling laws for Shor's algorithm with a banded quantum Fourier transform

Yunseong Nam, R. Blümel

We investigate the performance of a streamlined version of Shor's algorithm in which the quantum Fourier transform is replaced by a banded version that, for each qubit, retains only coupling to its $b$ nearest neighbors. Defining the performance $P(n,b)$ of the $n$-qubit algorithm for bandwidth $b$ as the ratio of the success rates of Shor's algorithm equipped with the banded and the full-bandwidth ($b=n\ensuremath{-}1$) versions of the quantum Fourier transform, our numerical simulations show that $P(n,b)\ensuremath{\approx}\mathrm{exp}[\ensuremath{-}{\ensuremath{\varphi}}_{\mathrm{max}}^{2}(n,b)/100]$ for $n<{n}_{t}(b)$ (nonexponential regime) and $P(n,b)\ensuremath{\approx}{2}^{\ensuremath{-}{\ensuremath{\xi}}_{b}(n\ensuremath{-}8)}$ for $n>{n}_{t}(b)$ (exponential regime), where ${n}_{t}(b)$, the location of the transition, is approximately given by ${n}_{t}(b)\ensuremath{\approx}b+5.9+\sqrt{7.7(b+2)\ensuremath{-}47}$ for $b\ensuremath{\gtrsim}8$, ${\ensuremath{\varphi}}_{\mathrm{max}}(n,b)=2\ensuremath{\pi}[{2}^{\ensuremath{-}b\ensuremath{-}1}(n\ensuremath{-}b\ensuremath{-}2)+{2}^{\ensuremath{-}n}]$, and ${\ensuremath{\xi}}_{b}\ensuremath{\approx}1.1\ifmmode\times\else\texttimes\fi{}{2}^{\ensuremath{-}2b}$. Analytically we obtain $P(n,b)\ensuremath{\approx}\mathrm{exp}[\ensuremath{-}{\ensuremath{\varphi}}_{\mathrm{max}}^{2}(n,b)/64]$ for $n<{n}_{t}(b)$ and $P(n,b)\ensuremath{\approx}{2}^{\ensuremath{-}{\ensuremath{\xi}}_{b}^{(a)}n}$ for $n>{n}_{t}(b)$, where ${\ensuremath{\xi}}_{b}^{(a)}\ensuremath{\approx}\frac{{\ensuremath{\pi}}^{2}}{12\mathrm{ln}(2)}\ifmmode\times\else\texttimes\fi{}{2}^{\ensuremath{-}2b}\ensuremath{\approx}1.19\ifmmode\times\else\texttimes\fi{}{2}^{\ensuremath{-}2b}$. Thus, our analytical results predict the ${\ensuremath{\varphi}}_{\mathrm{max}}^{2}$ scaling ($n<{n}_{t}$) and the ${2}^{\ensuremath{-}2b}$ scaling ($n>{n}_{t}$) of the data perfectly. In addition, in the large-$n$ regime, the prefactor in ${\ensuremath{\xi}}_{b}^{(a)}$ is close to the results of our numerical simulations, and in the low-$n$ regime, the numerical scaling factor in our analytical result is within a factor 2 of its numerical value. As an example we show that $b=8$ is sufficient for factoring RSA-2048 with a 95$%$ success rate.

arXiv:1302.5844•Physical Review A•Mar 27, 2013•23 citations

Streamlining Shor's algorithm for potential hardware savings

Yunseong Nam, R. Blümel

We constructed a virtual quantum computer by running a complete, scaling, quantum-gate--by--quantum-gate implementation of Shor's algorithm on a 128-core classical cluster computer. In mode A [quantum period finding (PF) only, supplied with classical results for the modular exponentiation (ME) part of Shor's algorithm], factoring semiprimes up to $N=557\phantom{\rule{0.16em}{0ex}}993$ with up to $n=39$ qubits, we confirm earlier, smaller-$n$ results concerning the performance scaling of Shor's algorithm equipped with a truncated (banded) quantum Fourier transform. Running our virtual quantum computer in mode B (full quantum implementation of ME and PF), we find that a large number of gates may be discarded in a scalable way in both the ME and PF parts of Shor's algorithm in exchange for only a small reduction in performance. We explicitly state the associated scaling laws. Implying significant savings in quantum gates, we suggest that these results are of importance for future experimental and technical large-$n$ implementations of quantum computers.

Physical Review A•Jun 26, 2013•6 citations

Entanglement and its role in Shor's algorithm

Viv M. Kendon, William J. Munro

Entanglement has been termed a critical resource for quantum information processing and is thought to be the reason that certain quantum algorithms, such as Shor's factoring algorithm, can achieve exponentially better performance than their classical counterparts. The nature of this resource is still not fully understood: here we use numerical simulation to investigate how entanglement between register qubits varies as Shor's algorithm is run on a quantum computer. The shifting patterns in the entanglement are found to relate to the choice of basis for the quantum Fourier transform.

arXiv:quant-ph/0412140•Quantum Information and Computation•Nov 1, 2006•31 citations

Deconstructing Shor’s Algorithm Using Quantum Fourier Transform

Dushyant Kumar, Balwinder Raj, Gurmohan Singh

Shor's algorithm proved a significant milestone in quantum computing since it promises an exponential speedup over conventional algorithms for integer factorization, a problem critical to modern cryptography systems. This work covers implementation steps of Shor’s algorithm and analyzes Quantum Fourier Transform (QFT) usage for extracting periodicity from quantum superpositions. Firstly, theoretical foundations of algorithm are illustrated concentrating on QFT construction and operation within the setting of the quantum circuit. Thereafter, each implementation step such as qubit optimization, modular exponentiation, and circuit design is discussed. Our findings validate the theoretical effectiveness of the QFT in solving the period-finding subroutine, while also highlighting the practical difficulties and scaling constraints presented by existing quantum hardware. The paper ends with a summary of possible advancements and future paths for error mitigation strategies and quantum algorithm design.

Indian Journal of Pure & Applied Physics•Jan 1, 2026•0 citations

A simplification of the Shor quantum factorization algorithm employing a quantum Hadamard transform

Rupert C. D. Young, Philip M. Birch, Chris R. Chatwin

The Shor quantum factorization algorithm allows the factorization or large integers in logarithmic squared time whereas classical algorithms require an exponential time increase with the bit length of the number to be factored. The hardware implementation of the Shor algorithm would thus allow the factorization of the very large integers employed by commercial encryption methods. We propose some modifications of the algorithm by employing some simplification to the stage employing the quantum Fourier transform. The quantum Hadamard transform may be used to replace the quantum Fourier transform in certain cases. This would reduce the hardware complexity of implementation since phase rotation gates with only two states of 0 and π would be required.

Pattern Recognition and Tracking•Apr 27, 2018•4 citations

Shor's algorithm requires Fanout

Lucas Gretta, Malvika Raj Joshi

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.

quant-pharXiv:2608.06703•Aug 10, 2026•0 citations
In excellent agreement with our numerical simulations of Shor's algorithm, equipped with a truncated quantum Fourier transform of bandwidth bbb, we find that its performance scales \ensuremath{\sim}$${2}^{\ensuremath{-}{\ensuremath{\xi}}_{b}n}, where nnn is the number of qubits, \ensuremathξb=1.1\ifmmode×\else\texttimes\fi2\ensuremath−2b{\ensuremath{\xi}}_{b}=1.1\ifmmode\times\else\texttimes\fi{}{2}^{\ensuremath{-}2b}\ensuremathξb​=1.1\ifmmode×\else\texttimes\fi2\ensuremath−2b, and the bandwidth bbb is the number of quantum states coupled by the quantum Fourier transform. Nonexponential behavior is observed for small nnn and explained analytically. The large-nnn exponential scaling implies that b=7b=7b=7 is sufficient to operate a 1000-qubit quantum computer running Shor's algorithm on the 9595%95 performance level and implies hardware savings of the order of half a million rotation gates.
We investigate the performance of a streamlined version of Shor's algorithm in which the quantum Fourier transform is replaced by a banded version that, for each qubit, retains only coupling to its bbb nearest neighbors. Defining the performance P(n,b)P(n,b)P(n,b) of the nnn-qubit algorithm for bandwidth bbb as the ratio of the success rates of Shor's algorithm equipped with the banded and the full-bandwidth ($b=n\ensuremath{-}1$) versions of the quantum Fourier transform, our numerical simulations show that $P(n,b)\ensuremath{\approx}\mathrm{exp}[\ensuremath{-}{\ensuremath{\varphi}}_{\mathrm{max}}^{2}(n,b)/100]$ for n<nt(b)n<{n}_{t}(b)n<nt​(b) (nonexponential regime) and $P(n,b)\ensuremath{\approx}{2}^{\ensuremath{-}{\ensuremath{\xi}}_{b}(n\ensuremath{-}8)}$ for n>nt(b)n>{n}_{t}(b)n>nt​(b) (exponential regime), where nt(b){n}_{t}(b)nt​(b), the location of the transition, is approximately given by ${n}_{t}(b)\ensuremath{\approx}b+5.9+\sqrt{7.7(b+2)\ensuremath{-}47}$ for $b\ensuremath{\gtrsim}8$, ${\ensuremath{\varphi}}_{\mathrm{max}}(n,b)=2\ensuremath{\pi}[{2}^{\ensuremath{-}b\ensuremath{-}1}(n\ensuremath{-}b\ensuremath{-}2)+{2}^{\ensuremath{-}n}]$, and ${\ensuremath{\xi}}_{b}\ensuremath{\approx}1.1\ifmmode\times\else\texttimes\fi{}{2}^{\ensuremath{-}2b}$. Analytically we obtain $P(n,b)\ensuremath{\approx}\mathrm{exp}[\ensuremath{-}{\ensuremath{\varphi}}_{\mathrm{max}}^{2}(n,b)/64]$ for n<nt(b)n<{n}_{t}(b)n<nt​(b) and $P(n,b)\ensuremath{\approx}{2}^{\ensuremath{-}{\ensuremath{\xi}}_{b}^{(a)}n}$ for n>nt(b)n>{n}_{t}(b)n>nt​(b), where ${\ensuremath{\xi}}_{b}^{(a)}\ensuremath{\approx}\frac{{\ensuremath{\pi}}^{2}}{12\mathrm{ln}(2)}\ifmmode\times\else\texttimes\fi{}{2}^{\ensuremath{-}2b}\ensuremath{\approx}1.19\ifmmode\times\else\texttimes\fi{}{2}^{\ensuremath{-}2b}$. Thus, our analytical results predict the ${\ensuremath{\varphi}}_{\mathrm{max}}^{2}$ scaling (n<ntn<{n}_{t}n<nt​) and the ${2}^{\ensuremath{-}2b}$ scaling (n>ntn>{n}_{t}n>nt​) of the data perfectly. In addition, in the large-nnn regime, the prefactor in ${\ensuremath{\xi}}_{b}^{(a)}$ is close to the results of our numerical simulations, and in the low-nnn regime, the numerical scaling factor in our analytical result is within a factor 2 of its numerical value. As an example we show that b=8b=8b=8 is sufficient for factoring RSA-2048 with a 95% success rate.
We constructed a virtual quantum computer by running a complete, scaling, quantum-gate--by--quantum-gate implementation of Shor's algorithm on a 128-core classical cluster computer. In mode A [quantum period finding (PF) only, supplied with classical results for the modular exponentiation (ME) part of Shor's algorithm], factoring semiprimes up to N=557993N=557\phantom{\rule{0.16em}{0ex}}993N=557993 with up to n=39n=39n=39 qubits, we confirm earlier, smaller-nnn results concerning the performance scaling of Shor's algorithm equipped with a truncated (banded) quantum Fourier transform. Running our virtual quantum computer in mode B (full quantum implementation of ME and PF), we find that a large number of gates may be discarded in a scalable way in both the ME and PF parts of Shor's algorithm in exchange for only a small reduction in performance. We explicitly state the associated scaling laws. Implying significant savings in quantum gates, we suggest that these results are of importance for future experimental and technical large-nnn implementations of quantum computers.
Entanglement has been termed a critical resource for quantum information processing and is thought to be the reason that certain quantum algorithms, such as Shor's factoring algorithm, can achieve exponentially better performance than their classical counterparts. The nature of this resource is still not fully understood: here we use numerical simulation to investigate how entanglement between register qubits varies as Shor's algorithm is run on a quantum computer. The shifting patterns in the entanglement are found to relate to the choice of basis for the quantum Fourier transform.
Shor's algorithm proved a significant milestone in quantum computing since it promises an exponential speedup over conventional algorithms for integer factorization, a problem critical to modern cryptography systems. This work covers implementation steps of Shor’s algorithm and analyzes Quantum Fourier Transform (QFT) usage for extracting periodicity from quantum superpositions. Firstly, theoretical foundations of algorithm are illustrated concentrating on QFT construction and operation within the setting of the quantum circuit. Thereafter, each implementation step such as qubit optimization, modular exponentiation, and circuit design is discussed. Our findings validate the theoretical effectiveness of the QFT in solving the period-finding subroutine, while also highlighting the practical difficulties and scaling constraints presented by existing quantum hardware. The paper ends with a summary of possible advancements and future paths for error mitigation strategies and quantum algorithm design.
The Shor quantum factorization algorithm allows the factorization or large integers in logarithmic squared time whereas classical algorithms require an exponential time increase with the bit length of the number to be factored. The hardware implementation of the Shor algorithm would thus allow the factorization of the very large integers employed by commercial encryption methods. We propose some modifications of the algorithm by employing some simplification to the stage employing the quantum Fourier transform. The quantum Hadamard transform may be used to replace the quantum Fourier transform in certain cases. This would reduce the hardware complexity of implementation since phase rotation gates with only two states of 0 and π would be required.
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 nnn-qubit modulus, necessarily requires the nnn-qubit Fanout operation. Formally, let QFTq\mathsf{QFT}_qQFTq​ be the gate acting on n=⌈log⁡q⌉n = \lceil \log q \rceiln=⌈logq⌉ qubits that computes the QFT under modulus qqq. It is known that any nnn-qubit QFTq\mathsf{QFT}_qQFTq​ can be implemented in constant depth using FANOUTn\mathsf{FANOUT}_nFANOUTn​, i.e. QFTq∈QACf0\mathsf{QFT}_q \in \mathsf{QAC}^0_fQFTq​∈QACf0​. We prove the converse by using a QFTq\mathsf{QFT}_qQFTq​ gate to construct a state of "non-negligible felinity". Consequently, QFTq∈QAC0  ⟺  FANOUTn∈QAC0\mathsf{QFT}_q \in \mathsf{QAC}^0 \iff \mathsf{FANOUT}_n \in \mathsf{QAC^0}QFTq​∈QAC0⟺FANOUTn​∈QAC0. In the case of q=2nq = 2^nq=2n, such as in Shor's, we approximate FANOUTn\mathsf{FANOUT}_nFANOUTn​ using a single QFT2n\mathsf{QFT}_{2^n}QFT2n​ gate and O(1)O(1)O(1) two-qubit local gates, thus tying the feasibility of realizing Shor's algorithm with NISQ circuits to that of Fanout.