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

IEEE Symposium on Computer Arithmetic (ARITH)

Quantum Algorithms for Exponentiation in a Group

Xavier Bonnetain, Pierrick Gaudry, Medhi Kermaoui

Published Jun 1, 2026• 0 citations
Publisher

Abstract

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.

DOI
10.1109/arith69512.2026.00032

Related papers

Constant-optimized quantum circuits for modular multiplication and exponentiation

Igor L. Markov, Mehdi Saeedi

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.

arXiv:1202.6614•Quantum Information and Computation•May 1, 2012•125 citations

Targeted Fibonacci Exponentiation

Burton S. Kaliski

A targeted exponentiation algorithm computes a group exponentiation operation $a^k$ with a reversible circuit in such a way that the initial state of the circuit consists of only the base $a$ and fixed values, and the final state consists of only the exponential $a^k$ and fixed values. Three targeted exponentiation algorithms based on Fibonacci addition chains are considered, offering tradeoffs in terms of the number of working registers and the number of iterations. The approaches also motivate related results on the Fibonacci Zeckendorf array, including a new \emph{modular Hofstadter G problem} and an improvement to Anderson's recent algorithm for locating pairs of adjacent integers in the extended Fibonacci Zeckendorf array. The algorithms have applications in quantum computing.

arXiv:1711.02491•Nov 5, 2017•8 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 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

Optimized quantum implementation of elliptic curve arithmetic over binary fields

Phillip Kaye

Shor's quantum algorithm for discrete logarithms applied to elliptic curve groups forms the basis of a ``quantum attack'' of elliptic curve cryptosystems. To implement this algorithm on a quantum computer requires the efficient implementation of the elliptic curve group operation. Such an implementation requires we be able to compute inverses in the underlying field. In \cite{PZ03}, Proos and Zalka show how to implement the extended Euclidean algorithm to compute inverses in the prime field $\GF(p)$. They employ a number of optimizations to achieve a running time of $O(n^2)$, and a space-requirement of $O(n)$ qubits, where $n$ is the number of bits in the binary representation of $p$ (there are some trade-offs that they make, sacrificing a few extra qubits to reduce running-time). In practice, elliptic curve cryptosystems often use curves over the binary field $\GF(2^m)$. In this paper, I show how to implement the extended Euclidean algorithm for polynomials to compute inverses in $\GF(2^m)$. Working under the assumption that qubits will be an `expensive' resource in realistic implementations, I optimize specifically to reduce the qubit space requirement, while keeping the running-time polynomial. The implementation here differs from that in $\cite{PZ03}$ for $\GF(p)$, and we are able to take advantage of some properties of the binary field $\GF(2^m)$. I also optimize the overall qubit space requirement for computing the group operation for elliptic curves over $\GF(2^m)$ by decomposing the group operation to make it ``piecewise reversible'' (similar to what is done in \cite{PZ03} for curves over $\GF(p)$).

arXiv:quant-ph/0407095•Quantum Information and Computation•Sep 1, 2005•35 citations

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•852 citations
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.
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.
A targeted exponentiation algorithm computes a group exponentiation operation aka^kak with a reversible circuit in such a way that the initial state of the circuit consists of only the base aaa and fixed values, and the final state consists of only the exponential aka^kak and fixed values. Three targeted exponentiation algorithms based on Fibonacci addition chains are considered, offering tradeoffs in terms of the number of working registers and the number of iterations. The approaches also motivate related results on the Fibonacci Zeckendorf array, including a new \emph{modular Hofstadter G problem} and an improvement to Anderson's recent algorithm for locating pairs of adjacent integers in the extended Fibonacci Zeckendorf array. The algorithms have applications in quantum computing.
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.
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.
Shor's quantum algorithm for discrete logarithms applied to elliptic curve groups forms the basis of a ``quantum attack'' of elliptic curve cryptosystems. To implement this algorithm on a quantum computer requires the efficient implementation of the elliptic curve group operation. Such an implementation requires we be able to compute inverses in the underlying field. In \cite{PZ03}, Proos and Zalka show how to implement the extended Euclidean algorithm to compute inverses in the prime field $\GF(p)$. They employ a number of optimizations to achieve a running time of O(n2)O(n^2)O(n2), and a space-requirement of O(n)O(n)O(n) qubits, where nnn is the number of bits in the binary representation of ppp (there are some trade-offs that they make, sacrificing a few extra qubits to reduce running-time). In practice, elliptic curve cryptosystems often use curves over the binary field $\GF(2^m)$. In this paper, I show how to implement the extended Euclidean algorithm for polynomials to compute inverses in $\GF(2^m)$. Working under the assumption that qubits will be an `expensive' resource in realistic implementations, I optimize specifically to reduce the qubit space requirement, while keeping the running-time polynomial. The implementation here differs from that in $\cite{PZ03}$ for $\GF(p)$, and we are able to take advantage of some properties of the binary field $\GF(2^m)$. I also optimize the overall qubit space requirement for computing the group operation for elliptic curves over $\GF(2^m)$ by decomposing the group operation to make it ``piecewise reversible'' (similar to what is done in \cite{PZ03} for curves over $\GF(p)$).
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.