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%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.
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
∣1⟩. 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
∣f(x)⟩ for
x∈{0,1,⋯,r−1}. Here, the ME function with base
a is defined by
f(x)=ax (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∈{0,1,⋯,r−1} increment the state
∣f(x)⟩=∣wn−1⋯w1w0⟩ to the state
∣f(x+1)⟩=∣wn−1′⋯w1′w0′⟩. The gates below
x do not affect the state
∣f(x+1)⟩. This amounts to transforming an
n-bit binary number
wn−1⋯w1w0 into another binary number
wn−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
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
Up (where
p 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.