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:1711.02491

Targeted Fibonacci Exponentiation

Burton S. Kaliski

Published Nov 5, 2017• 3 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.1711.02491

Related papers

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

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.

Quantum Information and Computation•May 1, 2012•83 citations

Optimized circuits for windowed modular arithmetic with applications to quantum attacks against RSA

Alessandro Luongo, Varun Narasimhachar, Adithya Sireesh

Windowed arithmetic [Gidney, 2019] is a technique for reducing the cost of quantum arithmetic circuits with space--time tradeoffs using memory queries to precomputed tables. It can reduce the asymptotic cost of modular exponentiation from $O\left(n^3\right)$ to $O\left(n^3/\log^2 n\right)$ operations, resulting in the current state-of-the-art compilations of quantum attacks against modern cryptography. In this work we introduce four optimizations to windowed modular exponentiation. We (1) show how the cost of unlookups can be reduced by $66\%$ asymptotically in the number of bits, (2) illustrate how certain addresses can be bypassed, reducing both circuit depth and the overall lookup cost, (3) demonstrate that multiple lookup--addition operations can be merged into a single, larger lookup at the start of the modular exponentiation circuit, and (4) reduce the depth of the unary conversion for unlookups. On a logical level, this leads to a $3\%$ improvement in Toffoli count and Toffoli depth for modular exponentiation circuits relevant to cryptographic applications. This translates to some improvements on [Gidney and Ekerå, 2021]'s factoring algorithm: for a given number of physical qubits, our improvements show a reduction in the expected runtime from $2\%$ to $6\%$ for factoring $\mathsf{RSA}$-$2048$ integers.

arXiv:2502.17325•Feb 24, 2025•1 citation

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 Θ(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.

•May 1, 2012•80 citations

Optimizing Quantum Circuits for Modular Exponentiation

Rakesh Das, Anupam Chattopadhyay, Hafizur Rahaman

Today's rapid progress in the physical implementation of quantum computers demands scalable synthesis methods to map practical logic designs to quantum architectures. There exist many quantum algorithms which use classical functions with superposition of states. Motivated by recent trends, in this paper, we show the design of quantum circuit to perform modular exponentiation functions using two different approaches. In the design phase, first we generate quantum circuit from a verilog implementation of exponentiation functions using synthesis tools and then apply two different Quantum Error Correction techniques. Finally the circuit is further optimized using the Linear Nearest Neighbor (LNN) Property. We demonstrate the effectiveness of our approach by generating a set of networks for the reversible modular exponentiation function for a set of input values. At the end of the work, we have summarized the obtained results, where a cost analysis over our developed approaches has been made. Experimental results show that depending on the choice of different QECC methods the performance figures can vary by up to 11%, 10%, 8% in T-count, number of qubits, number of gates respectively.

International Conference on VLSI Design•Jan 1, 2019•2 citations

Truncated Modular Exponentiation Operators: A Strategy for Quantum Factoring

Robert Singleton

Modular exponentiation (ME) operators are one of the fundamental components of Shor's algorithm, and the place where most of the quantum resources are deployed. These operators are often referred to as the bottleneck of the algorithm. I propose a method for constructing the ME operators that requires only $3n + 1$ qubits with no ancillary qubits. The method relies upon the simple observation that the work register starts in state $\vert 1 \rangle$. Therefore, we do not have to create an ME operator $U$ that accepts a general input, but rather, one that takes an input from the periodic sequence of states $\vert f(x) \rangle$ for $x \in \{0, 1, \cdots, r-1\}$. Here, the ME function with base $a$ is defined by $f(x) = a^x ~({\textrm mod}~N)$ and has a period of $r$. For an $n$-bit number $N$, the operator $U$ can be partitioned into $r$ levels, where the gates in level $x \in \{0, 1, \cdots, r-1\}$ increment the state $\vert f(x) \rangle = \vert w_{n-1} \cdots w_1 w_0 \rangle$ to the state $\vert f(x+1) \rangle = \vert w_{n-1}^\prime \cdots w_1^\prime w_0^\prime\rangle$. The gates below $x$ do not affect the state $\vert f(x+1) \rangle$. This amounts to transforming an $n$-bit binary number $w_{n-1} \cdots w_1 w_0$ into another binary number $w_{n-1}^\prime \cdots w_1^\prime w_0^\prime$, without altering the previous states, which can be accomplished by a set of formal rules involving multi-control-NOT gates and single-qubit NOT gates. The process of gate construction can therefore be automated, which is essential for factoring larger numbers. The obvious problem with this method is that it is self-defeating: If we knew the operator $U$, then we would know the period $r$ of the ME function, and there would be no need for Shor's algorithm. I show, however, that the ME operators are very forgiving, and truncated approximate forms in which levels have been omitted are able to extract factors just as well as the exact operators. I demonstrate this by factoring the numbers $N = 21, 33, 35, 143, 247$ by using less than half the requisite number of levels in the ME operators. This procedure works because the method of continued fractions only requires an approximate phase value, which suggests that implementing Shor's algorithm might not be as difficult as first suspected. This is the basis for a factorization strategy in which one level at a time is iterated over using an automated script. In this way, we fill the circuits for the ME operators with more and more gates, and the correlations between the various composite operators $U^p$ (where $p$ is a power of two) compensate for the missing levels. Quanta 2024; 13: 47–82.

arXiv:2405.17021•Quanta•Dec 30, 2024•0 citations
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.
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.
Windowed arithmetic [Gidney, 2019] is a technique for reducing the cost of quantum arithmetic circuits with space--time tradeoffs using memory queries to precomputed tables. It can reduce the asymptotic cost of modular exponentiation from O(n3)O\left(n^3\right)O(n3) to O(n3/log⁡2n)O\left(n^3/\log^2 n\right)O(n3/log2n) operations, resulting in the current state-of-the-art compilations of quantum attacks against modern cryptography. In this work we introduce four optimizations to windowed modular exponentiation. We (1) show how the cost of unlookups can be reduced by 66%66\%66% asymptotically in the number of bits, (2) illustrate how certain addresses can be bypassed, reducing both circuit depth and the overall lookup cost, (3) demonstrate that multiple lookup--addition operations can be merged into a single, larger lookup at the start of the modular exponentiation circuit, and (4) reduce the depth of the unary conversion for unlookups. On a logical level, this leads to a 3%3\%3% improvement in Toffoli count and Toffoli depth for modular exponentiation circuits relevant to cryptographic applications. This translates to some improvements on [Gidney and Ekerå, 2021]'s factoring algorithm: for a given number of physical qubits, our improvements show a reduction in the expected runtime from 2%2\%2% to 6%6\%6% for factoring RSA\mathsf{RSA}RSA-204820482048 integers.
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 Θ(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.
Today's rapid progress in the physical implementation of quantum computers demands scalable synthesis methods to map practical logic designs to quantum architectures. There exist many quantum algorithms which use classical functions with superposition of states. Motivated by recent trends, in this paper, we show the design of quantum circuit to perform modular exponentiation functions using two different approaches. In the design phase, first we generate quantum circuit from a verilog implementation of exponentiation functions using synthesis tools and then apply two different Quantum Error Correction techniques. Finally the circuit is further optimized using the Linear Nearest Neighbor (LNN) Property. We demonstrate the effectiveness of our approach by generating a set of networks for the reversible modular exponentiation function for a set of input values. At the end of the work, we have summarized the obtained results, where a cost analysis over our developed approaches has been made. Experimental results show that depending on the choice of different QECC methods the performance figures can vary by up to 11%, 10%, 8% in T-count, number of qubits, number of gates respectively.
Modular exponentiation (ME) operators are one of the fundamental components of Shor's algorithm, and the place where most of the quantum resources are deployed. These operators are often referred to as the bottleneck of the algorithm. I propose a method for constructing the ME operators that requires only 3n+13n + 13n+1 qubits with no ancillary qubits. The method relies upon the simple observation that the work register starts in state ∣1⟩\vert 1 \rangle∣1⟩. Therefore, we do not have to create an ME operator UUU that accepts a general input, but rather, one that takes an input from the periodic sequence of states ∣f(x)⟩\vert f(x) \rangle∣f(x)⟩ for x∈{0,1,⋯ ,r−1}x \in \{0, 1, \cdots, r-1\}x∈{0,1,⋯,r−1}. Here, the ME function with base aaa is defined by f(x)=ax (mod N)f(x) = a^x ~({\textrm mod}~N)f(x)=ax (mod N) and has a period of rrr. For an nnn-bit number NNN, the operator UUU can be partitioned into rrr levels, where the gates in level x∈{0,1,⋯ ,r−1}x \in \{0, 1, \cdots, r-1\}x∈{0,1,⋯,r−1} increment the state ∣f(x)⟩=∣wn−1⋯w1w0⟩\vert f(x) \rangle = \vert w_{n-1} \cdots w_1 w_0 \rangle∣f(x)⟩=∣wn−1​⋯w1​w0​⟩ to the state ∣f(x+1)⟩=∣wn−1′⋯w1′w0′⟩\vert f(x+1) \rangle = \vert w_{n-1}^\prime \cdots w_1^\prime w_0^\prime\rangle∣f(x+1)⟩=∣wn−1′​⋯w1′​w0′​⟩. The gates below xxx do not affect the state ∣f(x+1)⟩\vert f(x+1) \rangle∣f(x+1)⟩. This amounts to transforming an nnn-bit binary number wn−1⋯w1w0w_{n-1} \cdots w_1 w_0wn−1​⋯w1​w0​ into another binary number wn−1′⋯w1′w0′w_{n-1}^\prime \cdots w_1^\prime w_0^\primewn−1′​⋯w1′​w0′​, without altering the previous states, which can be accomplished by a set of formal rules involving multi-control-NOT gates and single-qubit NOT gates. The process of gate construction can therefore be automated, which is essential for factoring larger numbers. The obvious problem with this method is that it is self-defeating: If we knew the operator UUU, then we would know the period rrr of the ME function, and there would be no need for Shor's algorithm. I show, however, that the ME operators are very forgiving, and truncated approximate forms in which levels have been omitted are able to extract factors just as well as the exact operators. I demonstrate this by factoring the numbers N=21,33,35,143,247N = 21, 33, 35, 143, 247N=21,33,35,143,247 by using less than half the requisite number of levels in the ME operators. This procedure works because the method of continued fractions only requires an approximate phase value, which suggests that implementing Shor's algorithm might not be as difficult as first suspected. This is the basis for a factorization strategy in which one level at a time is iterated over using an automated script. In this way, we fill the circuits for the ME operators with more and more gates, and the correlations between the various composite operators UpU^pUp (where ppp is a power of two) compensate for the missing levels. Quanta 2024; 13: 47–82.