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.
This work generalizes Shor’s algorithm into quasi-Shor algorithms by replacing the modular exponentiation with alternative unitary operations. By using the quantum circuits to generate Bell states as the unitary operations, a specific example called the Bell–Shor algorithm was constructed. The system density matrices in the quantum circuits with four distinct input states were calculated in ideal conditions and illustrated through chromatic graphs to witness the evolution of quantum states in the quantum circuits. For the real part of the density matrices, it was revealed that the number of zero elements dramatically declined to only a few points after the operation of the inverse quantum Fourier transformation. Based on this property, a protocol constituting a pair of error metrics Γa and Γb is proposed for the global benchmarking of universal quantum processors by looking at the locations of the zero entries and normalized average values of non-zero entries. The protocol has polynomial resource requirements with the scale of the quantum processor. The Bell–Shor algorithm is capable of being a feasible setting for the global benchmarking of universal quantum processors.
Let N be a (large) positive integer, let b be an integer satisfying 1< b < N that is relatively prime to N, and let r be the order of b modulo N. Finally, let QC be a quantum computer whose input register has the size specified in Shor's original description of his order-finding algorithm. In this paper, we analyze the probability that a single run of the quantum component of the algorithm yields useful information---a nontrivial divisor of the order sought. We prove that when Shor's algorithm is implemented on QC, then the probability P of obtaining a (nontrivial) divisor of
r exceeds
.7 whenever N \ge 2^{11} and r\ge 40, and we establish that
.7736 is an asymptotic lower bound for
P. When
N is not a power of an odd prime, Gerjuoy has shown that
P exceeds 90 percent for
N and
r sufficiently large. We give easily checked conditions on N and r for this 90 percent threshold to hold, and we establish an asymptotic lower bound for
P of 2\Si(4\pi)/\pi ~0.9499 in this situation. More generally, for any nonnegative integer
q, we show that when QC(q) is a quantum computer whose input register has
q more qubits than does QC, and Shor's algorithm is run on QC(q), then an asymptotic lower bound on P is 2\Si(2^{q+2}\pi)/\pi (if N is not a power of an odd prime). Our arguments are elementary and our lower bounds on P are carefully justified.
Let N be a (large positive integer, let b > 1 be an integer relatively prime to N, and let r be the order of b modulo N. Finally, let QC be a quantum computer whose input register has the size specified in Shor's original description of his order-finding algorithm. We prove that when Shor's algorithm is implemented on QC, then the probability P of obtaining a (nontrivial) divisor of r exceeds 0.7 whenever N exceeds 2^{11}-1 and r exceeds 39, and we establish that 0.7736 is an asymptotic lower bound for P. When N is not a power of an odd prime, Gerjuoy has shown that P exceeds 90 percent for N and r sufficiently large. We give easily checked conditions on N and r for this 90 percent threshold to hold, and we establish an asymptotic lower bound for P of (2/Pi) Si(4Pi), about .9499, in this situation. More generally, for any nonnegative integer q, we show that when QC(q) is a quantum computer whose input register has q more qubits than does QC, and Shor's algorithm is run on QC(q), then an asymptotic lower bound on P is (2/Pi) Si(2^(q+2) Pi) (if N is not a power of an odd prime). Our arguments are elementary and our lower bounds on P are carefully justified.
The security of messages encoded via the widely used RSA public key encryption system rests on the enormous computational effort required to find the prime factors of a large number N using classical (i.e., conventional) computers. In 1994, however, Peter Shor showed that for sufficiently large N a quantum computer would be expected to perform the factoring with much less computational effort. This paper endeavors to explain, in a fashion comprehensible to the non-expert readers of this journal: (i) the RSA encryption protocol; (ii) the various quantum computer manipulations constituting the Shor algorithm; (iii) how the Shor algorithm performs the factoring; and (iv) the precise sense in which a quantum computer employing Shor's algorithm can be said to accomplish the factoring of very large numbers with less computational effort than a classical computer can. It is made apparent that factoring
N generally requires many successive runs of the algorithm. The careful analysis herein reveals, however, that the probability of achieving a successful factorization on a single run is about twice as large as commonly quoted in the literature.
Quantum algorithms for integer factorization represent one of the most prominent applications of quantum computation, with far-reaching implications for modern cryptography. While Shor's algorithm provides a polynomial-time solution in the ideal quantum model, its practical implementation is severely constrained by the limitations of current noisy intermediate-scale quantum (NISQ) hardware. These constraints have motivated the exploration of alternative factoring algorithms with different structural and resource trade-offs.
In this work, we present an experimental study of Regev's quantum factoring algorithm, implemented on real quantum hardware, and compare its behavior with that of Shor's algorithm under analogous conditions. Focusing on the case N = 15, we execute both algorithms on the QMIO quantum computer at the Centro de Supercomputacion de Galicia (CESGA) and contrast the results with one of IBM's open-access quantum computers and ideal simulations. This parallel execution enables a low-level comparison of the two algorithms, highlighting how their respective quantum implementations interact with hardware noise, limited circuit depth, and finite sampling.
Our analysis emphasizes the different ways in which Shor's and Regev's algorithms encode arithmetic structure into quantum states through Fourier sampling in one and higher dimensions, respectively, and how these differences manifest in experimental outcomes. Although neither algorithm demonstrates a practical advantage in the small N regime, the results provide insight into their relative robustness and failure modes on contemporary quantum devices. This study illustrates the value of experimental benchmarking of alternative quantum factoring algorithms as a means of understanding the practical implications of algorithmic design choices in the NISQ era.