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

arXiv:2207.05309

Quantum Algorithm based on Quantum Fourier Transform for Register-by-Constant Addition

Filipe C. Ferraz

Published Jul 12, 2022• 1 citation
arXivHTMLPDF

Abstract

Since Shor's proposition of the method for factoring products of prime numbers using quantum computing, there has been a quest to implement efficient quantum arithmetic algorithms. These algorithms are capable of applying arithmetic operations simultaneously on large sets of values using quantum parallelism. Draper proposed an addition algorithm based on the quantum Fourier transform whose operands are two quantum registers, which I refer to as register-by-register addition. However, for cases where there is the need to be added a constant value to a target register, Draper's algorithm is more complex than necessary in terms of number of operations and number of qubits used. In this paper, I present a more efficient addition algorithm than Draper's for cases where there needs to be added just a constant to a target register.

DOI
10.48550/arxiv.2207.05309

Related papers

IMPLEMENTATION OF QUANTUM ARITHMETIC OPERATIONS WITH INTEGER CHARACTERS USING THE QUANTUM FOURIER TRANSFORM

Aksultan Mukhanbet, Moldir Nakibayeva, Beimbet Daribayev

It has been proven that a quantum computer is superior to an electronic com puter in solving some NP problems. Based on quantum operations, this article proposes a new quantum sum and quantum multiplication, and then the floating point quantum multiplier and quantum sum are created on the basis of fixed point number operations. These studies lay the foundation for the quantum implementation of digital filters. This article provides a new way to calculate the summator on a quantum computer. This method uses the quantum Fourier transform (QFT) and reduces the number of qubits needed to be added by eliminating the need to temporarily transfer bits. This approach also allows you to add a classical number to a quantum superposition without encoding a classical number in a quantum register. This method also allows for mass parallelization during its execution. Adding and multiplying capabilities based on QFT are improved with some changes. The proposed operations are compared with the operations of close quantum arithmetic.

Journal of problem in computer science and information technologies•Apr 3, 2023•2 citations

Quantum Arithmetic Circuits: A Survey

Yasuhiro Takahashi

Quantum circuits for elementary arithmetic operations are important not only for implementing Shor's factoring algorithm on a quantum computer but also for understanding the computational power of small quantum circuits, such as linear-size or logarithmic-depth quantum circuits. This paper surveys some recent approaches to constructing efficient quantum circuits for elementary arithmetic operations and their applications to Shor's factoring algorithm. It covers addition, comparison, and the quantum Fourier transform used for addition.

IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences•Jan 1, 2009•34 citations

Addition on a Quantum Computer

Thomas G. Draper

A new method for computing sums on a quantum computer is introduced. This technique uses the quantum Fourier transform and reduces the number of qubits necessary for addition by removing the need for temporary carry bits. This approach also allows the addition of a classical number to a quantum superposition without encoding the classical number in the quantum register. This method also allows for massive parallelization in its execution.

arXiv:quant-ph/0008033•Aug 7, 2000•434 citations

Fast quantum modular exponentiation architecture for Shor's factoring alogrithm

Archimedes Pavlidis, Dimitris Gizopoulos

We present a novel and efficient, in terms of circuit depth, design for Shor's quantum factorization algorithm. The circuit effectively utilizes a diverse set of adders based on the Quantum Fourier transform (QFT) Draper's adders to build more complex arithmetic blocks: quantum multiplier/accumulators by constants and quantum dividers by constants. These arithmetic blocks are effectively architected into a quantum modular multiplier which is the fundamental block for the modular exponentiation circuit, the most computational intensive part of Shor's algorithm. The proposed modular exponentiation circuit has a depth of about $2000n^2$ and requires $9n+2$ qubits, where $n$ is the number of bits of the classic number to be factored. The total quantum cost of the proposed design is $1600n^3$. The circuit depth can be further decreased by more than three times if the approximate QFT implementation of each adder unit is exploited.

arXiv:1207.0511•Quantum Information and Computation•May 1, 2014•74 citations

Bridging Quantum and Classical: FPGA-Based Emulation of the Draper Adder Algorithm

Delphina Jerusha, B Chitti Babu, Rama Muni Reddy Yanamala

Quantum computers are known for high speed applications like cryptography and optimization, as they use qubits which exist in multiple states simultaneously. However, they are prone to hardware noise and high error rate. Thus quantum emulation can bridge the gap between theory and practical quantum computing. Field Programmable Gate Arrays (FPGA) based emulators are promising as highly parallel emulators can be designed. This work is carried out on PYNQ-Z2 FPGA board, where the Draper Adder algorithm was developed, using Quantum Fourier Transform, Phase rotation and Inverse Quantum Fourier Transform. This algorithm performs addition in the phase domain. A comparative analysis was carried out between two designs of the emulator with and without parallelism. The findings suggest that both designs satisfy the timing requirements and the resources were utilized within the limit of the FPGA. However, there was a trade-off between area and time, whereas there was no significant change in the power.

IEEE International Conference on VLSI Systems, Architecture, Technology and Applications (VLSI SATA)•Jun 1, 2026•0 citations

Truncated phase-based quantum arithmetic: Error propagation and resource reduction

Gregory A. L. White, Charles D. Hill, Lloyd C. L. Hollenberg

There are two important, and potentially interconnecting, avenues to the realization of large-scale quantum algorithms: improvement of the hardware, and reduction of resource requirements demanded by algorithm components. In focusing on the latter, one crucial subroutine to many sought-after applications is the quantum adder. A variety of different implementations exist with idiosyncratic pros and cons. One of these, the Draper quantum Fourier adder, offers the lowest qubit count of any adder, but requires a substantial number of gates as well as extremely fine rotations. In this work we present a modification of the Draper adder which eliminates small-angle rotations to highly coarse levels, matched with some strategic corrections. This reduces hardware requirements without sacrificing the qubit saving. We show that the inherited loss of fidelity is directly given by the rate of carry and borrow bits in the computation. We derive formulas to predict this, complemented by complete gate-level matrix product state simulations of the circuit. Moreover, we analytically describe the effects of possible stochastic control error. We present an in-depth analysis of this approach in the context of Shor's algorithm, focusing on the factoring of RSA-2048. Surprisingly, we find that each of the $7\ifmmode\times\else\texttimes\fi{}{10}^{7}$ quantum Fourier transforms may be truncated down to $\ensuremath{\pi}/64$, with additive rotations left only slightly finer. This result is much more efficient than previously realized. We quantify savings in terms of both logical resources and raw magic states, demonstrating that phase adders can be competitive with Toffoli-based constructions.

arXiv:2110.00217•Physical Review A•Nov 16, 2023•0 citations
Since Shor's proposition of the method for factoring products of prime numbers using quantum computing, there has been a quest to implement efficient quantum arithmetic algorithms. These algorithms are capable of applying arithmetic operations simultaneously on large sets of values using quantum parallelism. Draper proposed an addition algorithm based on the quantum Fourier transform whose operands are two quantum registers, which I refer to as register-by-register addition. However, for cases where there is the need to be added a constant value to a target register, Draper's algorithm is more complex than necessary in terms of number of operations and number of qubits used. In this paper, I present a more efficient addition algorithm than Draper's for cases where there needs to be added just a constant to a target register.
It has been proven that a quantum computer is superior to an electronic com puter in solving some NP problems. Based on quantum operations, this article proposes a new quantum sum and quantum multiplication, and then the floating point quantum multiplier and quantum sum are created on the basis of fixed point number operations. These studies lay the foundation for the quantum implementation of digital filters. This article provides a new way to calculate the summator on a quantum computer. This method uses the quantum Fourier transform (QFT) and reduces the number of qubits needed to be added by eliminating the need to temporarily transfer bits. This approach also allows you to add a classical number to a quantum superposition without encoding a classical number in a quantum register. This method also allows for mass parallelization during its execution. Adding and multiplying capabilities based on QFT are improved with some changes. The proposed operations are compared with the operations of close quantum arithmetic.
Quantum circuits for elementary arithmetic operations are important not only for implementing Shor's factoring algorithm on a quantum computer but also for understanding the computational power of small quantum circuits, such as linear-size or logarithmic-depth quantum circuits. This paper surveys some recent approaches to constructing efficient quantum circuits for elementary arithmetic operations and their applications to Shor's factoring algorithm. It covers addition, comparison, and the quantum Fourier transform used for addition.
We present a novel and efficient, in terms of circuit depth, design for Shor's quantum factorization algorithm. The circuit effectively utilizes a diverse set of adders based on the Quantum Fourier transform (QFT) Draper's adders to build more complex arithmetic blocks: quantum multiplier/accumulators by constants and quantum dividers by constants. These arithmetic blocks are effectively architected into a quantum modular multiplier which is the fundamental block for the modular exponentiation circuit, the most computational intensive part of Shor's algorithm. The proposed modular exponentiation circuit has a depth of about 2000n22000n^22000n2 and requires 9n+29n+29n+2 qubits, where nnn is the number of bits of the classic number to be factored. The total quantum cost of the proposed design is 1600n31600n^31600n3. The circuit depth can be further decreased by more than three times if the approximate QFT implementation of each adder unit is exploited.
Quantum computers are known for high speed applications like cryptography and optimization, as they use qubits which exist in multiple states simultaneously. However, they are prone to hardware noise and high error rate. Thus quantum emulation can bridge the gap between theory and practical quantum computing. Field Programmable Gate Arrays (FPGA) based emulators are promising as highly parallel emulators can be designed. This work is carried out on PYNQ-Z2 FPGA board, where the Draper Adder algorithm was developed, using Quantum Fourier Transform, Phase rotation and Inverse Quantum Fourier Transform. This algorithm performs addition in the phase domain. A comparative analysis was carried out between two designs of the emulator with and without parallelism. The findings suggest that both designs satisfy the timing requirements and the resources were utilized within the limit of the FPGA. However, there was a trade-off between area and time, whereas there was no significant change in the power.
There are two important, and potentially interconnecting, avenues to the realization of large-scale quantum algorithms: improvement of the hardware, and reduction of resource requirements demanded by algorithm components. In focusing on the latter, one crucial subroutine to many sought-after applications is the quantum adder. A variety of different implementations exist with idiosyncratic pros and cons. One of these, the Draper quantum Fourier adder, offers the lowest qubit count of any adder, but requires a substantial number of gates as well as extremely fine rotations. In this work we present a modification of the Draper adder which eliminates small-angle rotations to highly coarse levels, matched with some strategic corrections. This reduces hardware requirements without sacrificing the qubit saving. We show that the inherited loss of fidelity is directly given by the rate of carry and borrow bits in the computation. We derive formulas to predict this, complemented by complete gate-level matrix product state simulations of the circuit. Moreover, we analytically describe the effects of possible stochastic control error. We present an in-depth analysis of this approach in the context of Shor's algorithm, focusing on the factoring of RSA-2048. Surprisingly, we find that each of the $7\ifmmode\times\else\texttimes\fi{}{10}^{7}$ quantum Fourier transforms may be truncated down to $\ensuremath{\pi}/64$, with additive rotations left only slightly finer. This result is much more efficient than previously realized. We quantify savings in terms of both logical resources and raw magic states, demonstrating that phase adders can be competitive with Toffoli-based constructions.