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

Quantum 2.0 Conference and Exhibition

Recursion Depth Reduction in Shor’s Algorithm

Shuangbao Paul Wang

Published Jan 1, 2022• 0 citations
Publisher

Abstract

Mathematical-oriented analog quantum computing paradigm seeks perfectness in searching for solutions. However, the errors propagation due to noises may offset the accuracy over time. This paper aims to shorten the execution time on QFT transforms.
DOI
10.1364/quantum.2022.qtu2a.36

Related papers

Operator Imprecision and Scaling of Shor's Algorithm

Connie R. Hill, George F. Viamontes

Shor's algorithm (SA) is a quantum algorithm for factoring integers. Since SA has polynomial complexity while the best classical factoring algorithms are sub-exponential, SA is cited as evidence that quantum computers are more powerful than classical computers. SA is critically dependent on the Quantum Fourier Transform (QFT) and it is known that the QFT is sensitive to errors in the quantum state input to it. In this paper, we show that the polynomial scaling of SA is destroyed by input errors to the QFT part of the algorithm. We also show that Quantum Error Correcting Codes (QECC) are not capable of suppressing errors due to operator imprecision and that propagation of operator precision errors is sufficient to severely degrade the effectiveness of SA. Additionally we show that operator imprecision in the error correction circuit for the Calderbank-Shor-Steane QECC is mathematically equivalent to decoherence on every physical qubit in a register. We conclude that, because of the effect of operator precision errors, it is likely that physically realizable quantum computers will be capable of factoring integers no more efficiently than classical computers.

arXiv:0804.3076•Apr 18, 2008•0 citations

Three-Qubit Implementation of Quantum Fourier Transform for Shor’s Algorithm

Deepanshu Trivedi, Ankur Saharia, Kamal Kishor Choure +3 more

Lecture notes in electrical engineering•Sep 1, 2021•3 citations

Efficient FPGA Emulation of Quantum Fourier Transform

Yu Qian, Mingyu Wang, Jialin Chen +2 more

Quantum computation shows its great advantage on exponential speed-up for some complex algorithms. Compared to software simulation with sequential execution, hardware emulation based on Field Programmable Gate Array (FPGA) can help to realize the intrinsic quantum parallelism. Quantum Fourier Transform (QFT) is the core of several quantum algorithms like Shor's algorithm. This paper proposes a recursive decomposition of QFT-n, which can be emulated with a pipeline architecture based on Intel Stratix IV FPGA device. Although QFT-8 is much more complex than QFT-5, experimental results show that our QFT-8 architecture can reduces 91% DSP blocks and 76% combinational ALUTs at the cost of 11x registers compared with QFT-5 in [4] on average.

China Semiconductor Technology International Conference (CSTIC)•Mar 1, 2019•6 citations

Speeding up implementation for Shor＇s factorization quantum algorithm

 Fu, Xiang-Qun, Bao +3 more

中国科学通报：英文版•Jan 1, 2010•0 citations

Speeding up implementation for Shor’s factorization quantum algorithm

Xiang-Qun Fu, Wan‐Su Bao, Chun Hua Zhou

Chinese Science Bulletin•Nov 1, 2010•11 citations

Performance Evaluations of Noisy Approximate Quantum Fourier Arithmetic

Robert Basili, Wenyang Qian, Shuo Tang +5 more

The Quantum Fourier Transform (QFT) grants competitive advantages, especially in resource usage and circuit approximation, for performing arithmetic operations on quantum computers, and offers a potential route towards a numerical quantum-computational paradigm. In this paper, we utilize efficient techniques to implement QFT-based integer addition and multiplications. These operations are fundamental to various quantum applications including Shor's algorithm, weighted sum optimization problems in data processing and machine learning, and quantum algorithms requiring inner products. We carry out performance evaluations of these implementations based on IBM's superconducting qubit architecture using different compatible noise models. We isolate the sensitivity of the component quantum circuits on both one-/two-qubit gate error rates, and the number of the arithmetic operands' superposed integer states. We analyze performance, and identify the most effective approximation depths for quantum add and quantum multiply within the given context. We observe significant dependency of the optimal approximation depth on the degree of machine noise and the number of superposed states in certain performance regimes. Finally, we elaborate on the algorithmic challenges - relevant to signed, unsigned, modular and non-modular versions - that could also be applied to current implementations of QFT-based subtraction, division, exponentiation, and their potential tensor extensions. We analyze performance trends in our results and speculate on possible future development within this computational paradigm.

IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum•May 1, 2022•2 citations
Shor's algorithm (SA) is a quantum algorithm for factoring integers. Since SA has polynomial complexity while the best classical factoring algorithms are sub-exponential, SA is cited as evidence that quantum computers are more powerful than classical computers. SA is critically dependent on the Quantum Fourier Transform (QFT) and it is known that the QFT is sensitive to errors in the quantum state input to it. In this paper, we show that the polynomial scaling of SA is destroyed by input errors to the QFT part of the algorithm. We also show that Quantum Error Correcting Codes (QECC) are not capable of suppressing errors due to operator imprecision and that propagation of operator precision errors is sufficient to severely degrade the effectiveness of SA. Additionally we show that operator imprecision in the error correction circuit for the Calderbank-Shor-Steane QECC is mathematically equivalent to decoherence on every physical qubit in a register. We conclude that, because of the effect of operator precision errors, it is likely that physically realizable quantum computers will be capable of factoring integers no more efficiently than classical computers.
Quantum computation shows its great advantage on exponential speed-up for some complex algorithms. Compared to software simulation with sequential execution, hardware emulation based on Field Programmable Gate Array (FPGA) can help to realize the intrinsic quantum parallelism. Quantum Fourier Transform (QFT) is the core of several quantum algorithms like Shor's algorithm. This paper proposes a recursive decomposition of QFT-n, which can be emulated with a pipeline architecture based on Intel Stratix IV FPGA device. Although QFT-8 is much more complex than QFT-5, experimental results show that our QFT-8 architecture can reduces 91% DSP blocks and 76% combinational ALUTs at the cost of 11x registers compared with QFT-5 in [4] on average.
The Quantum Fourier Transform (QFT) grants competitive advantages, especially in resource usage and circuit approximation, for performing arithmetic operations on quantum computers, and offers a potential route towards a numerical quantum-computational paradigm. In this paper, we utilize efficient techniques to implement QFT-based integer addition and multiplications. These operations are fundamental to various quantum applications including Shor's algorithm, weighted sum optimization problems in data processing and machine learning, and quantum algorithms requiring inner products. We carry out performance evaluations of these implementations based on IBM's superconducting qubit architecture using different compatible noise models. We isolate the sensitivity of the component quantum circuits on both one-/two-qubit gate error rates, and the number of the arithmetic operands' superposed integer states. We analyze performance, and identify the most effective approximation depths for quantum add and quantum multiply within the given context. We observe significant dependency of the optimal approximation depth on the degree of machine noise and the number of superposed states in certain performance regimes. Finally, we elaborate on the algorithmic challenges - relevant to signed, unsigned, modular and non-modular versions - that could also be applied to current implementations of QFT-based subtraction, division, exponentiation, and their potential tensor extensions. We analyze performance trends in our results and speculate on possible future development within this computational paradigm.