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:1202.6614 · Quantum Information and Computation

Constant-optimized quantum circuits for modular multiplication and exponentiation

Igor L. Markov, Mehdi Saeedi

Published May 1, 2012• 125 citations
arXivHTMLPDF

Abstract

Reversible circuits for modular multiplication $Cx\%M$ with $x<M$ arise as components of modular exponentiation in Shor's quantum number-factoring algorithm. However, existing generic constructions focus on asymptotic gate count and circuit depth rather than actual values, producing fairly large circuits not optimized for specific $C$ and $M$ values. In this work, we develop such optimizations in a bottom-up fashion, starting with most convenient $C$ values. When zero-initialized ancilla registers are available, we reduce the search for compact circuits to a shortest-path problem. Some of our modular-multiplication circuits are asymptotically smaller than previous constructions, but worst-case bounds and average sizes remain $\Theta(n^2)$. In the context of modular exponentiation, we offer several constant-factor improvements, as well as an improvement by a constant additive term that is significant for few-qubit circuits arising in ongoing laboratory experiments with Shor's algorithm.

DOI
10.26421/qic12.5-6-1

Related papers

Asymptotic yet practical optimization of quantum circuits implementing GF($2^m$) multiplication and division operations

Noureldin Yosri, Dmytro Gavinsky, Dmitri Maslov

We present optimized quantum circuits for GF$(2^m)$ multiplication and division operations, which are essential computing primitives in various quantum algorithms. Our ancilla-free GF multiplication circuit has the gate count complexity of $O(m^{\log_2{3}})$, an improvement over the previous best bound of $O(m^2)$. This was achieved by developing an efficient $O(m)$ circuit for multiplication by the constant polynomial $1+x^{\lceil{m/2}\rceil}$, a key component of Van Hoof's construction. This asymptotic reduction translates to a factor of 100+ improvement of the CNOT gate counts in the implementation of the multiplication by the constant for parameters $m$ of practical importance. For the GF division, we reduce gate count complexity from $O(m^2 \log(m))$ to $O(m^2 \log \log(m)/\log(m))$ by selecting irreducible polynomials that enable efficient implementation of both the constant polynomial multiplication and field squaring operations. We demonstrate practical advantages for cryptographically relevant values of $m$, including reductions in both CNOT and Toffoli gate counts. Additionally, we explore the complexity of implementing square roots of linear reversible unitaries and demonstrate that a root, although itself still a linear reversible transformation, can require asymptotically deeper circuit implementations than the original unitary.

quant-pharXiv:2511.20618•Nov 26, 2025•0 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•32 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.

IEEE Symposium on Computer Arithmetic (ARITH)•Jun 1, 2026•0 citations

Factoring using 2n+2 qubits with Toffoli based modular multiplication

Thomas Häner, Martin Roetteler, Krysta M. Svore

We describe an implementation of Shor’s quantum algorithm to factor n-bit integers using only 2n+2 qubits. In contrast to previous space-optimized implementations, ours features a purely Toffoli based modular multiplication circuit. The circuit depth and the overall gate count are in O(n 3 ) and O(n 3 log n), respectively. We thus achieve the same space and time costs as Takahashi et al. [1], while using a purely classical modular multiplication circuit. As a consequence, our approach evades most of the cost overheads originating from rotation synthesis and enables testing and localization of some faults in both, the logical level circuit and an actual quantum hardware implementation. Our new (in-place) constant-adder, which is used to construct the modular multiplication circuit, uses only dirty ancilla qubits and features a circuit size and depth in O(n log n) and O(n), respectively.

arXiv:1611.07995•Quantum Information and Computation•May 1, 2017•140 citations

Discrete Fourier-transform-based quantum circuit for modular multiplication in Shor's algorithm

Abu Musa Patoary, Amit Vikram, Victor 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•Physical Review A•Feb 25, 2026•1 citation

Fast quantum integer multiplication with zero ancillas

Gregory D. Kahanamoku–Meyer, Norman Y. Yao

The multiplication of superpositions of numbers is a core operation in many quantum algorithms. The standard method for multiplication (both classical and quantum) has a runtime quadratic in the size of the inputs. Quantum circuits with asymptotically fewer gates have been developed, but generally exhibit large overheads, especially in the number of ancilla qubits. In this work, we introduce a new paradigm for sub-quadratic-time quantum multiplication with zero ancilla qubits -- the only qubits involved are the input and output registers themselves. Our algorithm achieves an asymptotic gate count of $\mathcal{O}(n^{1+ε})$ for any $ε> 0$; with practical choices of parameters, we expect scalings as low as $\mathcal{O}(n^{1.3})$. Used as a subroutine in Shor's algorithm, our technique immediately yields a factoring circuit with $\mathcal{O}(n^{2+ε})$ gates and only $2n + \mathcal{O}(\log n)$ qubits; to our knowledge, this is by far the best qubit count of any factoring circuit with a sub-cubic number of gates. Used in Regev's recent factoring algorithm, the gate count is $\mathcal{O}(n^{1.5+ε})$. Finally, we demonstrate that our algorithm has the potential to outperform previous proposals at problem sizes relevant in practice, including yielding the smallest circuits we know of for classically-verifiable quantum advantage.

arXiv:2403.18006•Mar 26, 2024•31 citations
Reversible circuits for modular multiplication Cx%MCx\%MCx%M with x<Mx<Mx<M arise as components of modular exponentiation in Shor's quantum number-factoring algorithm. However, existing generic constructions focus on asymptotic gate count and circuit depth rather than actual values, producing fairly large circuits not optimized for specific CCC and MMM values. In this work, we develop such optimizations in a bottom-up fashion, starting with most convenient CCC values. When zero-initialized ancilla registers are available, we reduce the search for compact circuits to a shortest-path problem. Some of our modular-multiplication circuits are asymptotically smaller than previous constructions, but worst-case bounds and average sizes remain Θ(n2)\Theta(n^2)Θ(n2). In the context of modular exponentiation, we offer several constant-factor improvements, as well as an improvement by a constant additive term that is significant for few-qubit circuits arising in ongoing laboratory experiments with Shor's algorithm.
Asymptotic yet practical optimization of quantum circuits implementing GF(2m2^m2m) multiplication and division operations
We present optimized quantum circuits for GF(2m)(2^m)(2m) multiplication and division operations, which are essential computing primitives in various quantum algorithms. Our ancilla-free GF multiplication circuit has the gate count complexity of O(mlog⁡23)O(m^{\log_2{3}})O(mlog2​3), an improvement over the previous best bound of O(m2)O(m^2)O(m2). This was achieved by developing an efficient O(m)O(m)O(m) circuit for multiplication by the constant polynomial 1+x⌈m/2⌉1+x^{\lceil{m/2}\rceil}1+x⌈m/2⌉, a key component of Van Hoof's construction. This asymptotic reduction translates to a factor of 100+ improvement of the CNOT gate counts in the implementation of the multiplication by the constant for parameters mmm of practical importance. For the GF division, we reduce gate count complexity from O(m2log⁡(m))O(m^2 \log(m))O(m2log(m)) to O(m2log⁡log⁡(m)/log⁡(m))O(m^2 \log \log(m)/\log(m))O(m2loglog(m)/log(m)) by selecting irreducible polynomials that enable efficient implementation of both the constant polynomial multiplication and field squaring operations. We demonstrate practical advantages for cryptographically relevant values of mmm, including reductions in both CNOT and Toffoli gate counts. Additionally, we explore the complexity of implementing square roots of linear reversible unitaries and demonstrate that a root, although itself still a linear reversible transformation, can require asymptotically deeper circuit implementations than the original unitary.
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, 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 describe an implementation of Shor’s quantum algorithm to factor n-bit integers using only 2n+2 qubits. In contrast to previous space-optimized implementations, ours features a purely Toffoli based modular multiplication circuit. The circuit depth and the overall gate count are in O(n 3 ) and O(n 3 log n), respectively. We thus achieve the same space and time costs as Takahashi et al. [1], while using a purely classical modular multiplication circuit. As a consequence, our approach evades most of the cost overheads originating from rotation synthesis and enables testing and localization of some faults in both, the logical level circuit and an actual quantum hardware implementation. Our new (in-place) constant-adder, which is used to construct the modular multiplication circuit, uses only dirty ancilla qubits and features a circuit size and depth in O(n log n) and O(n), respectively.
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.
The multiplication of superpositions of numbers is a core operation in many quantum algorithms. The standard method for multiplication (both classical and quantum) has a runtime quadratic in the size of the inputs. Quantum circuits with asymptotically fewer gates have been developed, but generally exhibit large overheads, especially in the number of ancilla qubits. In this work, we introduce a new paradigm for sub-quadratic-time quantum multiplication with zero ancilla qubits -- the only qubits involved are the input and output registers themselves. Our algorithm achieves an asymptotic gate count of O(n1+ε)\mathcal{O}(n^{1+ε})O(n1+ε) for any ε>0ε> 0ε>0; with practical choices of parameters, we expect scalings as low as O(n1.3)\mathcal{O}(n^{1.3})O(n1.3). Used as a subroutine in Shor's algorithm, our technique immediately yields a factoring circuit with O(n2+ε)\mathcal{O}(n^{2+ε})O(n2+ε) gates and only 2n+O(log⁡n)2n + \mathcal{O}(\log n)2n+O(logn) qubits; to our knowledge, this is by far the best qubit count of any factoring circuit with a sub-cubic number of gates. Used in Regev's recent factoring algorithm, the gate count is O(n1.5+ε)\mathcal{O}(n^{1.5+ε})O(n1.5+ε). Finally, we demonstrate that our algorithm has the potential to outperform previous proposals at problem sizes relevant in practice, including yielding the smallest circuits we know of for classically-verifiable quantum advantage.