The goal of this paper is to outline a general-purpose scalable implementation of Shor’s period-finding algorithm using fundamental quantum gates, and to act as a blueprint for linear optical implementations of Shor’s algorithm for both general and specific values of N. This offers a broader view of a problem often overlooked in favour of compiled versions of the algorithm.
The goal of this paper is to outline a general-purpose scalable implementation of Shor’s period-finding algorithm using fundamental quantum gates, and to act as a blueprint for linear optical implementations of Shor’s algorithm for both general and specific values of N. This offers a broader view of a problem often overlooked in favour of compiled versions of the algorithm.
We constructed a virtual quantum computer by running a complete, scaling, quantum-gate--by--quantum-gate implementation of Shor's algorithm on a 128-core classical cluster computer. In mode A [quantum period finding (PF) only, supplied with classical results for the modular exponentiation (ME) part of Shor's algorithm], factoring semiprimes up to N=557993 with up to n=39 qubits, we confirm earlier, smaller-n results concerning the performance scaling of Shor's algorithm equipped with a truncated (banded) quantum Fourier transform. Running our virtual quantum computer in mode B (full quantum implementation of ME and PF), we find that a large number of gates may be discarded in a scalable way in both the ME and PF parts of Shor's algorithm in exchange for only a small reduction in performance. We explicitly state the associated scaling laws. Implying significant savings in quantum gates, we suggest that these results are of importance for future experimental and technical large-n implementations of quantum computers.
Quantum computing is inherently abstract and often counterintuitive from the perspective of classical physics. For learners to develop a deeper understanding, it is useful to study a practical example thoroughly, from its mathematical formalism to quantum circuit implementation. Shor's algorithm for period finding, which can then be used for prime factorization, is demonstrated in this paper due to its practical significance. While numerous publications on Shor's algorithm exist, they tend to focus on advanced theoretical analysis, specific implementation details, or narrowly defined research aspects; consequently, they are often not well-suited for educational purposes for beginning and intermediate learners. This paper presents a rigorous step-by-step walkthrough of Shor's algorithm, utilizing the conventional approach, and discusses the construction of the quantum oracle with illustrative numerical examples. This is followed by classical simulations and implementations on actual quantum hardware. The aim is to allow learners with minimal mathematical background to follow and understand the algorithm. Through this process, the paper also attempts to interpret and connect the key underlying quantum computing concepts of superposition, entanglement, interference, quantum oracle, and phase kick-back that are often assumed to be trivial and omitted in research papers, yet are particularly challenging for novice learners to internalize. In the numerical examples, reduced-qubit cases are included. By contrasting the results from the reduced-qubit configurations with the standard ones, learners can better appreciate the key enablers in Shor's algorithm and how the accuracy decreases with a smaller number of qubits. Moreover, reduced-qubit examples (e.g., 5 qubits) are small enough to be implemented in a hardware emulator, such as a low-cost and low-capacity Field Programmable Gate Array (FPGA), which can be used in experimental hardware classes for students to understand how to use an FPGA to simulate quantum circuits.
Recently researchers have been explored quantum phenomena's for computation purpose and demonstrated important computational algorithms such as integer factorization using Shor's algorithm, unsorted date base search using Grover's algorithm, quantum cryptography, teleportation and many more. Many approaches have been investigated for implementing quantum algorithm physically. In this review quantum computer implementation techniques are introduced with an emphasize on linear optics quantum computing.
Although the fundamental principles of quantum computing have been known for decades, it is only within the past few years that practical quantum computers have become available. Since these systems are limited to a small number of qubits, they cannot demonstrate quantum advantage for many practical problems. Accordingly, there has been an effort to develop near term implementations of algorithms purely for research and education. In this paper, we discuss a near term implementation of Shor's Algorithm using the Qiskit language on an IBM Q System One quantum computer. We extend currently available documentation by providing a full circuit diagram for Shor's Algorithm including gates specific to the implementation using Qiskit. We present an implementation capable of factoring small two-digit prime numbers, and discuss the limitations of noise when using real quantum computers vs. simulations.
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.
Nowadays, quantum computing is an important topic since it allows computations to be completed in a small amount of the time. The goal of using quantum computers (QC) is to solve an increasing number of problems that were previously intractable to address with traditional computing. The classical approaches work with bits, which are made up of 0s and 1s, whereas QC uses qubits. Classical computing is limited by storage capacity and speed of calculations, even when parallel computation is conducted on it. Compared to traditional methods, quantum parallelism allows the storage to be reduced exponentially with the potential of a shorter amount of time. Besides, Peter Shor's algorithm can solve the factorization problem used in RSA in polynomial time, whereas in a classical computer, factoring any big integer is intractable. The purpose of this research is to explore and implement quantum computing schemes and how Shor's algorithm can break RSA algorithms.