IEEE International Symposium on Parallel and Distributed Processing with Applications (ISPA)

The Quantum Shor Algorithm Simulated on FPGA

Xin Zhang, Yaqian Zhao, Rengang Li, XueLei Li, Zhenhua Guo, Xiaomin Zhu, Gang Dong

Published Dec 1, 2019• 13 citations

Abstract

Shor algorithm is a key milestone in the quantum computing history. It has greatly promoted the development of quantum computing since it is supposed to crack the RSA cryptosystems. Simulation technology is an important strategy in quantum computing research, but the software simulation can only simulate the final result rather than the behavior and hardware structure. This paper proposes a hardware simulation strategy for quantum Shor algorithm. The hardware simulation is closer to the execution process of quantum computation than software simulation. It helps to understand how quantum computer works more concrete, and guide the design of quantum computer more specifically. According to the workflow of quantum computer, this paper divides the Shor algorithm into quantum part and classical part. In our experiment, the quantum part is simulated on FPGA device, and the classical part is executed on CPU host. FPGA device communicates with CPU through PCIe channel, and realizes the modules of quantum register, Hadamard gate, quantum Fourier transform (QFT), quantum measure and so on. Our experiment support 17 qubit simulation in Intel A10 FPGA device, and the execution performance is consistent with our theoretical analysis.

DOI: 10.1109/ispa-bdcloud-sustaincom-socialcom48970.2019.00082

Related papers

Efficient FPGA Emulation of Quantum Fourier Transform

Yu Qian, Mingyu Wang, Jialin Chen +2 more

Quantum computation shows its great advantage on exponential speed-up for some complex algorithms. Compared to software simulation with sequential execution, hardware emulation based on Field Programmable Gate Array (FPGA) can help to realize the intrinsic quantum parallelism. Quantum Fourier Transform (QFT) is the core of several quantum algorithms like Shor's algorithm. This paper proposes a recursive decomposition of QFT-n, which can be emulated with a pipeline architecture based on Intel Stratix IV FPGA device. Although QFT-8 is much more complex than QFT-5, experimental results show that our QFT-8 architecture can reduces 91% DSP blocks and 76% combinational ALUTs at the cost of 11x registers compared with QFT-5 in [4] on average.

China Semiconductor Technology International Conference (CSTIC)Mar 1, 20196 citations

Development and Research of a Quantum Control System for the Computational Process and the Execution of Algorithms

Sergey M. Gushanskiy, Viktor Potapov, Н М Коробейникова

Currently, the theory of quantum computing is actively developing. Despite the fact that a quantum computer has some features, any algorithm designed for a classical computer can be implemented for a quantum one. The relevance of the topic of quantum computers is confirmed by the fact that even now banking systems, cryptography and encryption of information require enormous resources of computing systems, these are just some examples, but the most important and vivid ones that relate to the everyday life of a huge part of the world's population. A hardware computing core has been developed and simulated, which is the main part of an accelerator based on field-programmable gate array with computer aided design Altera Quartus. Considering the obtained time dependence of the number of cycles required for the impact of a single-qubit quantum gate on a quantum register on the number of qubits and parallel arithmetic logic units in the hardware computing core, when simulating quantum computing, a method was developed to determine the increase in hardware performance and ways to improve the performance of an accelerator based on a hardware computing core were developed. based on field-programmable gate array.

International Russian Automation Conference (RusAutoCon)Sep 10, 20230 citations

A Step-by-Step Shor’s Algorithm Walkthrough: From Theory to Implementation

Trung Nguyen, Samuel Petruescu, Shrikant S. Jadhav +1 more

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.

IEEE AccessJan 1, 20260 citations

Mathematical Analysis and Simulation of Shor's Algorithm and the Quantum Fourier Transform

Marcus Ahlström, Peda Dizdarevic, Patrik Henelius

In 1994, Peter Shor presented an algorithm for integer factorization that used exponentiallyless operations than the most efficient known algorithm. His algorithm requiresthe use of a quantum computer, a theoretical computational device using quantum mechanicaleffects not utilized in contemporary computers. In this paper we have analysedthe mathematics behind Shor’s algorithm and the quantum circuits on which it operates.We have also studied the Quantum Fourier Transform, a central component of Shor’sAlgorithm. Furthermore we have written a program in C++ to simulate a quantum circuitperforming Shor’s algorithm and the quantum Fourier transform. We were able tounderstand the critical parts of Shor’s algorithm that contribute with the great increasein efficiency compared to classical algorithms.

Jan 1, 20121 citation

Hardware emulation of Quantum Fourier Transform

Jose F. Rivera-Miranda, Alvaro J. Caicedo-Beltran, Juan D. Valencia-Payan +2 more

The Quantum Fourier Transform (QFT) has an important role in some of the most interesting and useful quantum algorithms, such as those for period finding, order finding, phase estimation and factoring. Most of the research carried out on the QFT has been developed using software simulators, however these do not emulate efficiently the quantum parallelism present in the quantum algorithms. Addressing this problem, this paper presents the hardware design of an emulator for computing the QFT using FPGAs. This emulator was designed considering a modular philosophy and it is expected to be a powerful tool to evaluate quantum algorithms that include a many-qubit QFT.

IEEE Latin American Symposium on Circuits and Systems (LASCAS)Feb 1, 20119 citations

Dynamic MPI Based Simulation of Shor’s Algorithm in Qiskit: Toward Scalable Emulation of Quantum Cryptographic Algorithms

Usha Giri, Fathi Amsaad

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.

IEEE National Aerospace and Electronics Conference (NAECON)Jul 28, 20250 citations