A fundamental problem in factorization by Shor's algorithm [1] is the implementation of the modular exponentiation function. The period of this function is important for determining the individual factors, so its accurate implementation is for successful factorization critical.The imprecision of current quantum computers requires that any quantum circuits should be as simple as possible. Both in terms of the number of qubits used, the number of quantum gates and the depth of the quantum circuit. Therefore, it is necessary to search for an optimal variant for the implementation of the above-mentioned modular exponentiation function.The standard method is to implement individual arithmetic functions [2] which can be combined to achieve the desired modular exponentiation function. This process, however, creates a very complex quantum circuit, so that its measured result (probability distribution) will be so skewed that it will not be possible to reliably obtain the period of sought.Another way is to create a special quantum circuit for one particular modular exponentiation function [3]. Such a circuit is of course simpler than the circuit created by the above universal implementation, but in practice it only makes sense for testing the functionality of the surrounding quantum circuit for period detection.A very interesting possibility for the implementation of arithmetic functions is to use the direct and inverse quantum Fourier transform [4]. For a quantum computer, these transformations are very easy operations, and this interesting feature can then be used to advantage in these various implementations.This contribution will explore these possible approaches and show their advantages and disadvantages through concrete examples.
We provide a pedagogical presentation of Shor's factoring algorithm, which is a quantum algorithm for factoring very large numbers (of order of hundreds to thousands of bits) in polynomial time. In contrast, all known classical algorithms for the factoring problem take an exponential time to factor such large numbers. Shor's algorithm therefore has profound implication for public-key encryption such as RSA and Diffie–Hellman key exchange. We assume no prior knowledge of Shor's algorithm beyond a basic familiarity with the circuit model of quantum computing. Shor's algorithm contains a number of moving parts, and can be rather daunting at first. The literature is replete with derivations and expositions of Shor's algorithm, but most of them seem to be lacking in essential details, and none of them provide a pedagogical presentation. They require a thicket of appendices and assume a knowledge of quantum algorithms and classical mathematics with which the reader might not be familiar. We therefore start with first principle derivations of the quantum Fourier transform (QFT) and quantum phase estimation (QPE), which are the essential building blocks of Shor's algorithm. We then go on to develop the theory of modular exponentiation (ME) operators, one of the fundamental components of Shor's algorithm, and the place where most of the quantum resources are deployed. We also delve into the number theory that establishes the link between factorization and the period of the modular exponential function. We then apply the QPE algorithm to obtain Shor's factoring algorithm. We also discuss the post-quantum processing and the method of continued fractions, which is used to extract the exact period of the modular exponential function from the approximately measured phase angles of the ME operator. The manuscript then moves on to a series of examples. We first verify the formalism by factoring N=15, the smallest number accessible to Shor's algorithm. We then proceed to factor larger integers, developing a systematic procedure that will find the ME operators for any semi-prime N=p×q (where q and p are prime). Finally, we factor the composite numbers N=21, 33, 35, 143, 247 using the Qiskit simulator. It is observed that the ME operators are somewhat forgiving, and truncated approximate forms are able to extract factors just as well as the exact operators. This is because the method of continued fractions only requires an approximate phase value for its input, which suggests that implementing Shor's algorithm might not be as difficult as first suspected. Quanta 2023; 12: 41–130.
This research and educational poster presents a key part of the Shor's factorization, namely the quantum implementation of the modular exponentiation function. In contrast to other works on a similar topic, where Shor's factorizations of small numbers such as 15, 21 or 35 are presented, an implementation of a modular exponentiation function applicable to the Shor's factorization of the number 247 is presented here. This poster shows one of the simpler ways of constructing a quantum circuit of a modular exponentiation function that allows this factorization. At the bottom of the poster, the measured results are presented and the sought factors are calculated, thus confirming the correct implementation.
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) 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.
This paper discusses and demonstrates the construction of a quantum modular exponentiation circuit in the Qiskit simulator for use in Shor's Algorithm for integer factorization problem (IFP), which is deemed to be able to crack RSA cryptosystems when a large-qubit quantum computer exists. We base our implementation on Vedral, Barenco, and Ekert (VBE) proposal of quantum modular exponentiation, one of the firsts to explicitly provide the aforementioned circuit. Furthermore, we present an example simulation of how to construct a 7xmod 15 circuit in a step-by-step manner, giving clear and detailed information and consideration that currently not provided in the existing literature, and present the whole circuit for use in Shor's Algorithm. Our present simulation shows that the 4-bit VBE quantum modular exponentiation circuit can be constructed, simulated, and measured in Qiskit, while the Shor's Algorithm incorporating this VBE approach itself can be constructed but not yet simulated due to an overly large number of QASM instructions.
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.