This article presents a detailed implementation of Shor’s quantum factoring algorithm, which served as the cornerstone for a pilot project at Jamk University of Applied Sciences. The primary goal was to leverage this significant algorithm to establish and validate a reusable quantum simulation environment on a high-performance computing (HPC) platform. We report the successful factorization of the integer 15, executed on the Finnish CSC’s MAHTI supercomputer using a 9-qubit quantum circuit developed in the Qiskit framework. This work provides a comprehensive overview of the principles behind Shor’s algorithm and a methodical breakdown of its simulation. Furthermore, it documents the practical software challenges faced during the environment’s configuration, focusing on library versioning and dependencies. The purpose of this work is to provide a systematic introduction to implement Shor’s algorithm at computer science or applied mathematics classes in institutions of higher education such as universities of applied sciences. The successful factorization provides an initial validation of the simulation workflow for this benchmark case, while the detailed account of implementing Shor’s algorithm offers a practical guide and valuable insights for future quantum computing initiatives at educational institutions with a focus on computer science or scientific computing.
This article presents a detailed implementation of Shor’s quantum factoring algorithm, which served as the cornerstone for a pilot project at Jamk University of Applied Sciences. The primary goal was to leverage this significant algorithm to establish and validate a reusable quantum simulation environment on a high-performance computing (HPC) platform. We report the successful factorization of the integer 15, executed on the Finnish CSC’s MAHTI supercomputer using a 9-qubit quantum circuit developed in the Qiskit framework. This work provides a comprehensive overview of the principles behind Shor’s algorithm and a methodical breakdown of its simulation. Furthermore, it documents the practical software challenges faced during the environment’s configuration, focusing on library versioning and dependencies. The purpose of this work is to provide a systematic introduction to implement Shor’s algorithm at computer science or applied mathematics classes in institutions of higher education such as universities of applied sciences. The successful factorization provides an initial validation of the simulation workflow for this benchmark case, while the detailed account of implementing Shor’s algorithm offers a practical guide and valuable insights for future quantum computing initiatives at educational institutions with a focus on computer science or scientific computing.
Shor’s algorithm stands as a breakthrough in quantum computing due to its potential to factor large integers exponentially quicker than classical algorithms. However, implementing and evaluating this algorithm on real quantum computer hardware remains exciting due to qubit limitations, gate noise, and hardware constraints. This research presents a comprehensive performance evaluation of Shor’s algorithm using simulated quantum backends provided by Qiskit. A flexible and generic implementation is proposed, allowing dynamic input of integers to be factored, with randomized co-prime selection and automated circuit generation. The algorithm is tested on various semiprime numbers, such as 15, 21, and 35, using IBM’s Aer simulator. A major contribution of this work is the circuit-level analysis conducted both before and after transpilation. Metrics such as gate counts, circuit depth, and simulator runtime are extracted to assess scalability and resource requirements. High-resolution plots of the pre-transpiled circuits are saved to visualize algorithmic complexity, while post-transpilation metrics inform future quantum hardware feasibility. The output measurement distributions are analyzed to estimate periodicity and derive correct factors. The proposed implementation is compared with existing fixed-instance Shor demonstrations to highlight its flexibility and extensibility. Experimental results show consistent success in factor retrieval and provide valuable insight into circuit growth and complexity under realistic constraints. This analysis lays the groundwork for future adaptation to NISQ hardware and contributes to understanding Shor’s algorithm from both computational and architectural perspectives.
Quantum Shor’s algorithm offers an exponential speedup over classical methods for integer factorization, a central problem to modern cryptography, and the implica- tions of Shor’s algorithm in factoring large numbers. The algorithm leverages on quantum parallelism to compute the period of a modular exponentiation function, employ- ing the Inverse Quantum Fourier Transform (IQFT) to extract periodicity, and classical post-processing to derive the factors. This final report of the Quantum Engineer- ing post-graduate course of the Fundacio Polit ́ enica de ` Catalunya, presents the main findings encountered in the implementation and benchmarking of Schor’s algorithm in real IBM quantum computers. To accomplish this, we created a command line tool made in Python, that allows the integration of the circuits implementing the Shor’s algorithm with the overall set of configuration parameters needed to perform the benchmark. In this report, we first provide an overview of the quantum factoring problem, followed by a detailed description of Shor’s algorithm, and its implementation using the Qiskit Python library. The circuit depth and noise effects are analyzed across different backend types, also different values for the optimization level and approximation degrees are configured when performing the circuit transpilation. As mentioned earlier different backend types were utilized for performance comparison, namely backend class with or without a noise model (AerSim), a fake backend class provided by the Qiskit library (fake provider), and the real quantum hardware (IBM Quantum Processing Units in January- June 2025).The study follows by analyzing the different error mitigation techniques: dynamic decoupling, Pauli twirling, the SABRE Optimization (Stochastic Algorithm for Quantum Boolean Optimization and Routing), and any combination of them. Once the optimum configuration is found, the maximum number that can be reasonably factorized with success is explored. Finally, the main conclusions, findings, and possible future research lines are presented, including the factorization of a N ≈ 1000 if appropriate parameters of the algorithm are selected.
Quantum circuit simulation is crucial for algorithm development and cryptanalysis given the limited qubit counts and high noise in today’s quantum hardware. We present a Qiskit MPI framework that accelerates classical simulation of quantum circuits focusing on Shor’s integer factoring algorithm by distributing workloads across high performance computing (HPC) resources. A novel dynamic shot allocation strategy balances simulation tasks across MPI processes, preventing idle CPUs even when the total number of circuit "shots" (independent runs) is not evenly divisible. This load balancing approach, combined with support for hybrid CPU/GPU execution on each node, achieves near linear speedups (e.g. 7.5× on 8 processes and 14× on 16 processes) in simulating Shor’s algorithm circuits. We validate the correctness of our parallel simulator by showing that distributed execution produces identical quantum output distributions as a serial run, thus maintaining fidelity. All experiments are performed with fixed random seeds and provided in open source form for reproducibility. We also discuss compatibility with the emerging Quantum Message Passing Interface (QMPI), which extends MPI to quantum computing contexts. By enabling fast, scalable simulation of cryptographically relevant algorithms like Shor’s on classical clusters, our framework allows researchers to prototype quantum attacks and assess quantum algorithm performance ahead of large scale quantum hardware. We report extensive experiments, including factoring small composite numbers, that demonstrate significant wall clock speedups without loss of accuracy. These results position our approach as a practical tool for scalable quantum algorithm prototyping and cryptanalysis research in the pre-quantum era.
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.
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.
Abstract Quantum computing represents a significant advancement in computational capabilities. Of particular concern is its impact on asymmetric cryptography through, notably, Shor’s algorithm and the more recently developed Regev’s algorithm for factoring composite numbers. We present our implementation of the latter with the aim of exposing experimental phenomena. Our analysis encompasses both quantum simulation results and classical component examples, with particular emphasis on comparative cases between Regev’s and Shor’s algorithms. Our experimental results reveal that Regev’s algorithm outperforms Shor’s algorithm for certain composite numbers in practice. However, we observed significant performance variations across different input values. Despite Regev’s algorithm’s theoretical asymptotic advantage in effectiveness, our implementation exhibited longer execution times than Shor’s algorithm for small-integer factorization in both quantum and classical components. These findings offer insights into the practical challenges and performance characteristics of implementing Regev’s algorithm in realistic quantum computing scenarios.