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:quant-ph/9511018 · Physical Review A

Quantum networks for elementary arithmetic operations

Vlatko Vedral, Adriano Barenco, ARTUR K. EKERT

Published Jul 1, 1996• 811 citations
arXivHTMLPDF

Abstract

Quantum computers require quantum arithmetic. We provide an explicit construction of quantum networks effecting basic arithmetic operations: from addition to modular exponentiation. Quantum modular exponentiation seems to be the most difficult (time and space consuming) part of Shor's quantum factorizing algorithm. We show that the auxiliary memory required to perform this operation in a reversible way grows linearly with the size of the number to be factorized. \textcopyright{} 1996 The American Physical Society.

DOI
10.1103/physreva.54.147

Related papers

Efficient networks for quantum factoring

David Beckman, Amalavoyal N. Chari, Devabhaktuni Srikrishna +1 more

We consider how to optimize memory use and computation time in operating a quantum computer. In particular, we estimate the number of memory quantum bits (qubits) and the number of operations required to perform factorization, using the algorithm suggested by Shor [in Proceedings of the 35th Annual Symposium on Foundations of Computer Science, edited by S. Goldwasser (IEEE Computer Society, Los Alamitos, CA, 1994), p. 124]. A K-bit number can be factored in time of order ${\mathit{K}}^{3}$ using a machine capable of storing 5K+1 qubits. Evaluation of the modular exponential function (the bottleneck of Shor's algorithm) could be achieved with about 72${\mathit{K}}^{3}$ elementary quantum gates; implementation using a linear ion trap would require about 396${\mathit{K}}^{3}$ laser pulses. A proof-of-principle demonstration of quantum factoring (factorization of 15) could be performed with only 6 trapped ions and 38 laser pulses. Though the ion trap may never be a useful computer, it will be a powerful device for exploring experimentally the properties of entangled quantum states. \textcopyright{} 1996 The American Physical Society.

arXiv:quant-ph/9602016•Physical Review A•Aug 1, 1996•268 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•35 citations

Quantum Algorithms for Exponentiation in a Group

Xavier Bonnetain, Pierrick Gaudry, Medhi Kermaoui

Modular exponentiation, and more generally, exponentiation of a group element, is an elementary operation that is ubiquitous, and its efficiency is critical for many applications in cryptography and computer algebra.In quantum algorithms, the case where the group element is fixed and the exponent is in superposition is well-studied, because it is part of Shor's factoring and discrete logarithm algorithms. The dual case where the exponent is fixed and the group element is in superposition is far less studied, but is also important, as it appears, for instance, in Kuperberg's hidden subgroup algorithm for the cryptanalysis of isogeny-based cryptography.In this work, we propose a generic quantum circuit for the exponentiation in this context. It builds upon reversible squareand-multiply (which is fast, but uses a number of qubits that is linear in the length of the exponent) and the Fibonacci addition chain (which is slower, but uses constant space). Our circuit is parametrizable and provides relevant time-memory trade-offs. In particular, it is well suited in cases where the number of available qubits is moderate, which is a typical situation when the exponentiation is part of a larger quantum computation.While our approach is generic, we focus on two use-cases with distinct cost profiles: modular exponentiation and scalar multiplication of a point on an elliptic curve.

•Jun 28, 2026•0 citations

Fast Quantum Modular Exponentiation Architecture for Shor's Factorization Algorithm

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 generic modular quantum multiplier which is the fundamental block for 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 classical 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•Jul 2, 2012•13 citations

Faster quantum number factoring via circuit synthesis

Igor L. Markov, Mehdi Saeedi

A major obstacle to implementing Shor's quantum number-factoring algorithm is the large size of modular-exponentiation circuits. We reduce this bottleneck by customizing reversible circuits for modular multiplication to individual runs of Shor's algorithm. Our circuit-synthesis procedure exploits spectral properties of multiplication operators and constructs optimized circuits from the traces of the execution of an appropriate greatest-common-divisor algorithm. Empirically, gate counts are reduced by four to five times, and circuit latency is reduced by larger factors.

arXiv:1301.3210•Physical Review A•Jan 14, 2013•34 citations

TRADING CLASSICAL FOR QUANTUM COMPUTATION USING INDIRECTION

Rodney Van Meter

Modular exponentiation is the most expensive portion of Shor’s algorithm. We show that it is possible to reduce the number of quantum modular multiplications necessary by a factor of , at a cost of adding temporary storage space and associated machinery for a table of entries, and performing times as many classical modular multiplications. The storage space may be a quantum-addressable classical memory, or pure quantum memory. With classical computation as much as times as fast as quantum computation, values of from 2 to 30 seem attractive; physically feasible values depend on the implementation of the memory.

International Symposium on Mesoscopic Superconductivity and Spintronics (MS+S)•Aug 1, 2005•0 citations
Quantum computers require quantum arithmetic. We provide an explicit construction of quantum networks effecting basic arithmetic operations: from addition to modular exponentiation. Quantum modular exponentiation seems to be the most difficult (time and space consuming) part of Shor's quantum factorizing algorithm. We show that the auxiliary memory required to perform this operation in a reversible way grows linearly with the size of the number to be factorized. \textcopyright{} 1996 The American Physical Society.
We consider how to optimize memory use and computation time in operating a quantum computer. In particular, we estimate the number of memory quantum bits (qubits) and the number of operations required to perform factorization, using the algorithm suggested by Shor [in Proceedings of the 35th Annual Symposium on Foundations of Computer Science, edited by S. Goldwasser (IEEE Computer Society, Los Alamitos, CA, 1994), p. 124]. A K-bit number can be factored in time of order K3{\mathit{K}}^{3}K3 using a machine capable of storing 5K+1 qubits. Evaluation of the modular exponential function (the bottleneck of Shor's algorithm) could be achieved with about 72K3{\mathit{K}}^{3}K3 elementary quantum gates; implementation using a linear ion trap would require about 396K3{\mathit{K}}^{3}K3 laser pulses. A proof-of-principle demonstration of quantum factoring (factorization of 15) could be performed with only 6 trapped ions and 38 laser pulses. Though the ion trap may never be a useful computer, it will be a powerful device for exploring experimentally the properties of entangled quantum states. \textcopyright{} 1996 The American Physical Society.
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.
Modular exponentiation, and more generally, exponentiation of a group element, is an elementary operation that is ubiquitous, and its efficiency is critical for many applications in cryptography and computer algebra.In quantum algorithms, the case where the group element is fixed and the exponent is in superposition is well-studied, because it is part of Shor's factoring and discrete logarithm algorithms. The dual case where the exponent is fixed and the group element is in superposition is far less studied, but is also important, as it appears, for instance, in Kuperberg's hidden subgroup algorithm for the cryptanalysis of isogeny-based cryptography.In this work, we propose a generic quantum circuit for the exponentiation in this context. It builds upon reversible squareand-multiply (which is fast, but uses a number of qubits that is linear in the length of the exponent) and the Fibonacci addition chain (which is slower, but uses constant space). Our circuit is parametrizable and provides relevant time-memory trade-offs. In particular, it is well suited in cases where the number of available qubits is moderate, which is a typical situation when the exponentiation is part of a larger quantum computation.While our approach is generic, we focus on two use-cases with distinct cost profiles: modular exponentiation and scalar multiplication of a point on an elliptic curve.
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 generic modular quantum multiplier which is the fundamental block for modular exponentiation circuit, the most computational intensive part of Shor's algorithm. The proposed modular exponentiation circuit has a depth of about 2000n22000n^{2}2000n2 and requires 9n+29n+29n+2 qubits, where nnn is the number of bits of the classical number to be factored. The total quantum cost of the proposed design is 1600n31600n^{3}1600n3. The circuit depth can be further decreased by more than three times if the approximate QFT implementation of each adder unit is exploited.
A major obstacle to implementing Shor's quantum number-factoring algorithm is the large size of modular-exponentiation circuits. We reduce this bottleneck by customizing reversible circuits for modular multiplication to individual runs of Shor's algorithm. Our circuit-synthesis procedure exploits spectral properties of multiplication operators and constructs optimized circuits from the traces of the execution of an appropriate greatest-common-divisor algorithm. Empirically, gate counts are reduced by four to five times, and circuit latency is reduced by larger factors.
Modular exponentiation is the most expensive portion of Shor’s algorithm. We show that it is possible to reduce the number of quantum modular multiplications necessary by a factor of , at a cost of adding temporary storage space and associated machinery for a table of entries, and performing times as many classical modular multiplications. The storage space may be a quantum-addressable classical memory, or pure quantum memory. With classical computation as much as times as fast as quantum computation, values of from 2 to 30 seem attractive; physically feasible values depend on the implementation of the memory.