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

International Symposium on Mesoscopic Superconductivity and Spintronics (MS+S)

TRADING CLASSICAL FOR QUANTUM COMPUTATION USING INDIRECTION

Rodney Van Meter

Published Aug 1, 2005• 0 citations
Publisher

Abstract

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.

DOI
10.1142/9789812701619_0049

Related papers

Quantum networks for elementary arithmetic operations

Vlatko Vedral, Adriano Barenco, ARTUR K. EKERT

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.

arXiv:quant-ph/9511018•Physical Review A•Jul 1, 1996•811 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

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.

Quantum Information and Computation•May 1, 2014•38 citations

On the Various Ways of Quantum Implementation of the Modular Exponentiation Function for Shor’s Factorization

Jiří Tomčala

Abstract The content of this paper is a detailed analysis of possible ways how to quantum implement a key part of Shor’s factorization algorithm, the modular exponentiation function. This implementation is a bottleneck for performing quantum factorization with polynomial complexity, which would make it possible to factorize really large numbers in a reasonable amount of time. In this paper, not only the general theory is presented, but also the results of successful factorizations of the numbers 247 and 143 using Shor’s algorithm from a quantum computer simulator. An interesting fact is that no ancillary qubits were needed in these factorizations. Based on the content of the paper, the conclusion also suggests possible future work on the development of this modular exponentiation function implementation.

International Journal of Theoretical Physics•Jan 10, 2024•7 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

A discrete Fourier transform based quantum circuit for modular multiplication in Shor's algorithm

Abu Musa Patoary, Amit Vikram, Victor M. Galitski

Shor's algorithm for the prime factorization of numbers provides an exponential speedup over the best known classical algorithms. However, nontrivial practical applications have remained out of reach due to experimental limitations. The bottleneck of the experimental realization of the algorithm is the modular exponentiation operation. In this paper, based on a relation between the modular multiplication operator and generalizations of discrete Fourier transforms, we propose a quantum circuit for modular exponentiation. A distinctive feature of our proposal is that our circuit can be entirely implemented in terms of the standard quantum circuit for the discrete Fourier transform and its variants. The gate-complexity of our proposal is $O(L^3)$ where L is the number of bits required to store the number being factorized. It is possible that such a proposal may provide easier avenues for near-term generic implementations of Shor's algorithm, in contrast to existing realizations which have often explicitly adapted the circuit to the number being factorized.

arXiv:2503.10008•Mar 13, 2025•0 citations
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.
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 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.
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.
Abstract The content of this paper is a detailed analysis of possible ways how to quantum implement a key part of Shor’s factorization algorithm, the modular exponentiation function. This implementation is a bottleneck for performing quantum factorization with polynomial complexity, which would make it possible to factorize really large numbers in a reasonable amount of time. In this paper, not only the general theory is presented, but also the results of successful factorizations of the numbers 247 and 143 using Shor’s algorithm from a quantum computer simulator. An interesting fact is that no ancillary qubits were needed in these factorizations. Based on the content of the paper, the conclusion also suggests possible future work on the development of this modular exponentiation function implementation.
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.
Shor's algorithm for the prime factorization of numbers provides an exponential speedup over the best known classical algorithms. However, nontrivial practical applications have remained out of reach due to experimental limitations. The bottleneck of the experimental realization of the algorithm is the modular exponentiation operation. In this paper, based on a relation between the modular multiplication operator and generalizations of discrete Fourier transforms, we propose a quantum circuit for modular exponentiation. A distinctive feature of our proposal is that our circuit can be entirely implemented in terms of the standard quantum circuit for the discrete Fourier transform and its variants. The gate-complexity of our proposal is O(L3)O(L^3)O(L3) where L is the number of bits required to store the number being factorized. It is possible that such a proposal may provide easier avenues for near-term generic implementations of Shor's algorithm, in contrast to existing realizations which have often explicitly adapted the circuit to the number being factorized.