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• 8 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.

IEEE Symposium on Computer Arithmetic (ARITH)•Jun 1, 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.

arXiv:1202.6614•Quantum Information and Computation•May 1, 2012•125 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•1 citation

Quantum Algorithms For Iterations Of Fractal Type Functions with Exponential Sums

Q. Ten

Quantum Algorithms are given for iterations of fractal type functions with exponential sums

•Sep 22, 2026•0 citations

FLCT: A Dual-Chart Addressing System for Fibonacci Anyon Braid Words

Kinsey Moore

Every integer encodes a braid. And the vast majority encode two. Zeckendorf's theorem — a standard result in combinatorial number theory — guarantees that every positive integer has a unique decomposition into non-consecutive Fibonacci numbers [1]. Herein we observe that the indices of this decomposition directly specify braid generators over the Fibonacci anyon model. Applying Zeckendorf's theorem independently to both the Fibonacci and Lucas number sets, we construct the Fibonacci-Lucas Coordinate Tube (FLCT), an anyonic coordinate system that maps every integer from 0 to F(445) ≈10^92 — the verified kernel range, exhaustively cross-checked against TQSim and Qrack at every structurally foundational address — to structurally addressable braid words, from which gate classification and phase structure extend naturally via integer arithmetic over the bounding algebra of ℚ(√5). The dual-chart construction itself is unbounded; its theoretical terminus, an attractor-driven singularity derived from the same ℚ(√5) algebra, is the subject of a further companion paper. Each decomposition yields a canonical generator set which then admits further algebraic ordering flexibility under the principles that compose this coordinate system. That reordering methodology, however, will be explored at length in a subsequent paper. This paper develops the Zeckendorf-reachable specialization; the structural ruleset itself applies to the entirety of braidspace, treated in Paper 2 (The Prism), which decomposes the 10^2118-word landscape into 8,010 structurally labeled cells via a mathematical construct called the MDA, or Multiphasic Data Adapter. For any address, the braid generators, phase class, cyclotomic field, superselection sector, gap signature, and other quantum classifications are computable in O(log n) bit-operations from integer arithmetic alone — no simulation, no search. Current compilation paradigms brute-force braid space as featureless terrain, iterating Solovay-Kitaev or Monte Carlo against target unitaries; FLCT sidesteps this approach for the Zeckendorf-reachable subset by exposing the rule-based structure already present. Every classification reduces to a single modular operation. FLCT provides a direct coordinate mapping to the same F- and R-matrices confirmed by recent quantum hardware [2, 3], reproducing these unitaries on conventional classical hardware (a laptop). This is an addressing and classification scheme, not a universal gate-approximation compiler; approximation guarantees for arbitrary targets are outside the scope of this paper.

•Apr 7, 2026•0 citations

Quantum circuit for exponentiation of Hamiltonians: an algorithmic description based on tensor products

Gérard Fleury, Philippe Lacomme

Exponentiation of Hamiltonians refers to a mathematical operation to a Hamiltonian operator, typically in the form e^(-i.t.H), where H is the Hamiltonian and t is a time parameter. This operation is fundamental in quantum mechanics, particularly to evolve quantum systems over time according to the Schrodinger equation. In quantum algorithms, such as Adiabatic methods and QAOA, exponentiation enables efficient simulation of a system dynamics. It involves constructing quantum circuits that approximate this exponential operation. When H=\sum_(p=1)^n H_p , each H_p is defined using the Pauli operator basis, which includes the well-known X, Y, Z and Id gates, i.e., H_p=U_1\otimes U_2\otimes \otimes U_n and U_k\in{Id,X,Y,Z}. In this article, we explore the exponentiation of H_p, specifically e^(-i.t.U_1 \otimes U_2\otimes \otimes U_n ), by introducing an algorithmic approach. We demonstrate a straightforward and efficient method to construct compact circuits that are easy to implement.

arXiv:2501.17780•Jan 29, 2025•1 citation
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.
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.
Every integer encodes a braid. And the vast majority encode two. Zeckendorf's theorem — a standard result in combinatorial number theory — guarantees that every positive integer has a unique decomposition into non-consecutive Fibonacci numbers [1]. Herein we observe that the indices of this decomposition directly specify braid generators over the Fibonacci anyon model. Applying Zeckendorf's theorem independently to both the Fibonacci and Lucas number sets, we construct the Fibonacci-Lucas Coordinate Tube (FLCT), an anyonic coordinate system that maps every integer from 0 to F(445) ≈10^92 — the verified kernel range, exhaustively cross-checked against TQSim and Qrack at every structurally foundational address — to structurally addressable braid words, from which gate classification and phase structure extend naturally via integer arithmetic over the bounding algebra of ℚ(√5). The dual-chart construction itself is unbounded; its theoretical terminus, an attractor-driven singularity derived from the same ℚ(√5) algebra, is the subject of a further companion paper. Each decomposition yields a canonical generator set which then admits further algebraic ordering flexibility under the principles that compose this coordinate system. That reordering methodology, however, will be explored at length in a subsequent paper. This paper develops the Zeckendorf-reachable specialization; the structural ruleset itself applies to the entirety of braidspace, treated in Paper 2 (The Prism), which decomposes the 10^2118-word landscape into 8,010 structurally labeled cells via a mathematical construct called the MDA, or Multiphasic Data Adapter. For any address, the braid generators, phase class, cyclotomic field, superselection sector, gap signature, and other quantum classifications are computable in O(log n) bit-operations from integer arithmetic alone — no simulation, no search. Current compilation paradigms brute-force braid space as featureless terrain, iterating Solovay-Kitaev or Monte Carlo against target unitaries; FLCT sidesteps this approach for the Zeckendorf-reachable subset by exposing the rule-based structure already present. Every classification reduces to a single modular operation. FLCT provides a direct coordinate mapping to the same F- and R-matrices confirmed by recent quantum hardware [2, 3], reproducing these unitaries on conventional classical hardware (a laptop). This is an addressing and classification scheme, not a universal gate-approximation compiler; approximation guarantees for arbitrary targets are outside the scope of this paper.
Exponentiation of Hamiltonians refers to a mathematical operation to a Hamiltonian operator, typically in the form e^(-i.t.H), where H is the Hamiltonian and t is a time parameter. This operation is fundamental in quantum mechanics, particularly to evolve quantum systems over time according to the Schrodinger equation. In quantum algorithms, such as Adiabatic methods and QAOA, exponentiation enables efficient simulation of a system dynamics. It involves constructing quantum circuits that approximate this exponential operation. When H=\sum_(p=1)^n H_p , each H_p is defined using the Pauli operator basis, which includes the well-known X, Y, Z and Id gates, i.e., H_p=U_1\otimes U_2\otimes \otimes U_n and U_k\in{Id,X,Y,Z}. In this article, we explore the exponentiation of H_p, specifically e^(-i.t.U_1 \otimes U_2\otimes \otimes U_n ), by introducing an algorithmic approach. We demonstrate a straightforward and efficient method to construct compact circuits that are easy to implement.