Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1801.01434 · Canadian Journal of Physics

Accelerating Shor’s factorization algorithm on GPUs

I. Savran, M. Demirci, A.H. Yılmaz

Published Feb 26, 2018• 7 citations
arXivHTMLPDF

Abstract

Shor’s quantum algorithm is very important for cryptography, because it can factor large numbers much faster than classical algorithms. In this study, we implement a simulator for Shor’s quantum algorithm on graphic processor units (GPU) and compare our results with Liquid, which is a Microsoft quantum simulation platform, and two classical CPU implementations. We evaluate 10 benchmarks for comparing our GPU implementation with Liquid and single-core implementation. The analysis shows that GPU vector operations are more suitable for Shor’s quantum algorithm. Our GPU kernel function is compute-bound, due to all threads in a block reaching the same element of the state vector. Our implementation has 52.5× speedup over single-core algorithm and 20.5× speedup over Liquid.

DOI
10.1139/cjp-2017-0768

Related papers

An efficient quantum circuit implementation of Shor’s algorithm for GPU accelerated simulation

XinJian Tan, Peng Gao

In this study, we introduce a novel implementation of Shor’s algorithm specifically designed for the Graphics Processing Unit (GPU) acceleration framework. Our focus lies on achieving efficient execution of the modular multiplication circuit through GPU simulation. To seamlessly integrate our design into the PyQPanda library framework, we made necessary modifications, making a deliberate trade-off by sacrificing a small number of quantum resources to leverage the advantages of GPU acceleration. Subsequently, we conducted simulations and rigorously validated the functionality of our circuit using the PyQPanda library, resulting in a significant speedup compared to a central processing unit-only mode.

AIP Advances•Feb 1, 2024•6 citations

Quantum Computer Simulations at Warp Speed: Assessing the Impact of GPU Acceleration

Jennifer Faj, Ivy Bo Peng, Jacob Wahlgren +1 more

Quantum computer simulators are crucial for the development of quantum computing. In this work, we investigate the suitability and performance impact of GPU and multi-GPU systems on a widely used simulation tool - the state vector simulator Qiskit Aer. In particular, we evaluate the performance of both Qiskit's default Nvidia Thrust backend and the recent Nvidia cuQuantum backend on Nvidia A100 GPUs. We provide a benchmark suite of representative quantum applications for characterization. For simulations with a large number of qubits, the two GPU backends can provide up to 14x speedup over the CPU backend, with Nvidia cuQuantum providing further 1.5-3x speedup over the default Thrust backend. Our evaluation on a single GPU identifies the most important functions in Nvidia Thrust and cuQuantum for different quantum applications and their compute and memory bottlenecks. We also evaluate the gate fusion and cache-blocking optimizations on different quantum applications. Finally, we evaluate large-number qubit quantum applications on multi-GPU and identify data movement between host and GPU as the limiting factor for the performance.

arXiv:2307.14860•Jul 27, 2023•2 citations

Efficient In-Situ Quantum Computing Simulation of Shor's and Grover's Algorithms

Anderson Ávila, Renata Reiser, Adenauer Yamin +1 more

Exponential increase and global access to read/write memory states in quantum computing simulation limit both the number of qubits and quantum transformations that can be currently simulated. Although quantum computing simulation is parallel by nature, spatial and temporal complexity are major performance hazards, making this an important application for HPC. A new methodology employing reduction and decomposition optimizations has shown great results, but its GPU implementation could be further improved. In this work, we intend to do a new implementation for in-situ GPU simulation that better explores its resources without requiring further HPC hardware. Shors and Grovers algorithms are simulated and compared to the previous version and to LIQUi|s simulator, showing better results with relative speedups up to 15.5× and 765.76× respectively.

International Symposium on Computer Architecture and High Performance Computing Workshops (SBAC-PADW)•Oct 1, 2017•4 citations

Quantum Emulators: CPU, single GPU and multiple GPUs performance comparison

Mathilde Chenu

Digital quantum computing promises new pathways for problem solving. However, currently available gate-based quantum computers still suffer from short decoherence timings and noisy results. In the meantime, quantum emulators can offer a way to test and refine quantum algorithms. They reproduce classically the behavior of quantum computers at the cost of large memory requirements: the memory needed doubles with each additional qubits emulated. Emulators can be set-up on a large range of machines, from laptops to supercomputers. In this paper, we compare the capabilities of quantum emulators built on the EuroHPC Karolina server using one CPU, one GPU or multiple GPUs in a single node. In terms of the number of qubits emulated, we show that while only 20+ qubits can be emulated using a single CPU, a single GPU brings this number to 30+. We also compare the timing performances, both for randomly generated quantum circuits and for Shor’s factorization algorithm. For randomly generated circuits with same depth and width, the emulators using a GPU and eight GPUs respectively are up to 20 and 180 times faster than the CPU-based emulator. For Shor’s algorithm which can have more than a million gates, the emulators using a GPU and eight GPUs respectively are up to 11 and 20 times faster than the CPU-based emulator. This benchmark of different types of quantum emulators on the Karolina server helps to choose the right parameters and make the most of the Karolina resources for future scientific work involving quantum emulation.

Procedia Computer Science•Jan 1, 2025•2 citations

Improving in situ GPU simulation of quantum computing in the D-GM environment

Anderson Ávila, Renata Reiser, Mauricio Lima Pilla +1 more

Exponential increase and global access to read/write memory states in quantum computing (QC) simulation limit both the number of qubits and quantum transformations which can be currently simulated. Although QC simulation is parallel by nature, spatial and temporal complexity are major performance hazards, making this a nontrivial application for high performance computing. A new methodology employing reduction and decomposition optimizations has shown relevant results, but its GPU implementation could be further improved. In this work, we develop a new kernel for in situ GPU simulation that better explores its resources without requiring further hardware. Shor’s and Grover’s algorithms are simulated up to 25 and 21 qubits respectively and compared to our previous version, to [Formula: see text] simulator and to ProjectQ framework, showing better results with relative speedups up to 4.38×, 3357.76× and 333× respectively.

The International Journal of High Performance Computing Applications•Jan 16, 2019•4 citations

Reduction and Decomposition Optimizations in Quantum Computing Simulation Applied to the Shor’s Algorithm

Anderson Ávila, Renata Reiser, Mauricio Lima Pilla

Due to the expansion of transformations and read/write memory states by tensor products in multidimensional quantum applications, the exponential increase in temporal and spatial complexities constitutes one of the main challenges for quantum computing simulations. Simulation of these systems is important in order to develop and test new quantum algorithms. This work presents reduction and decomposition optimizations for the Distributed Geometric Machine environment. By exploring properties as the sparsity of the Identity operator and partiality of dense unitary transformations, better storage and distribution of quantum information are achieved. The main improvements are implemented by decreasing replication and void elements inherited from quantum operators. In the evaluation of this proposal, Shor’s algorithm considering 2n+3 qubits in the order-finding quantum algorithm was simulated up to 25 qubits over CPU, sequentially and in parallel, and over GPU. Results confirm that temporal complexity is reduced. When comparing our implementations running on the same hardware with LIQUi|i, academic release version, our new simulator was faster and allowed for the simulation of more qubits.

Proceeding Series of the Brazilian Society of Computational and Applied Mathematics•Apr 14, 2017•0 citations
Shor’s quantum algorithm is very important for cryptography, because it can factor large numbers much faster than classical algorithms. In this study, we implement a simulator for Shor’s quantum algorithm on graphic processor units (GPU) and compare our results with Liquid, which is a Microsoft quantum simulation platform, and two classical CPU implementations. We evaluate 10 benchmarks for comparing our GPU implementation with Liquid and single-core implementation. The analysis shows that GPU vector operations are more suitable for Shor’s quantum algorithm. Our GPU kernel function is compute-bound, due to all threads in a block reaching the same element of the state vector. Our implementation has 52.5× speedup over single-core algorithm and 20.5× speedup over Liquid.
In this study, we introduce a novel implementation of Shor’s algorithm specifically designed for the Graphics Processing Unit (GPU) acceleration framework. Our focus lies on achieving efficient execution of the modular multiplication circuit through GPU simulation. To seamlessly integrate our design into the PyQPanda library framework, we made necessary modifications, making a deliberate trade-off by sacrificing a small number of quantum resources to leverage the advantages of GPU acceleration. Subsequently, we conducted simulations and rigorously validated the functionality of our circuit using the PyQPanda library, resulting in a significant speedup compared to a central processing unit-only mode.
Quantum computer simulators are crucial for the development of quantum computing. In this work, we investigate the suitability and performance impact of GPU and multi-GPU systems on a widely used simulation tool - the state vector simulator Qiskit Aer. In particular, we evaluate the performance of both Qiskit's default Nvidia Thrust backend and the recent Nvidia cuQuantum backend on Nvidia A100 GPUs. We provide a benchmark suite of representative quantum applications for characterization. For simulations with a large number of qubits, the two GPU backends can provide up to 14x speedup over the CPU backend, with Nvidia cuQuantum providing further 1.5-3x speedup over the default Thrust backend. Our evaluation on a single GPU identifies the most important functions in Nvidia Thrust and cuQuantum for different quantum applications and their compute and memory bottlenecks. We also evaluate the gate fusion and cache-blocking optimizations on different quantum applications. Finally, we evaluate large-number qubit quantum applications on multi-GPU and identify data movement between host and GPU as the limiting factor for the performance.
Exponential increase and global access to read/write memory states in quantum computing simulation limit both the number of qubits and quantum transformations that can be currently simulated. Although quantum computing simulation is parallel by nature, spatial and temporal complexity are major performance hazards, making this an important application for HPC. A new methodology employing reduction and decomposition optimizations has shown great results, but its GPU implementation could be further improved. In this work, we intend to do a new implementation for in-situ GPU simulation that better explores its resources without requiring further HPC hardware. Shors and Grovers algorithms are simulated and compared to the previous version and to LIQUi|s simulator, showing better results with relative speedups up to 15.5× and 765.76× respectively.
Digital quantum computing promises new pathways for problem solving. However, currently available gate-based quantum computers still suffer from short decoherence timings and noisy results. In the meantime, quantum emulators can offer a way to test and refine quantum algorithms. They reproduce classically the behavior of quantum computers at the cost of large memory requirements: the memory needed doubles with each additional qubits emulated. Emulators can be set-up on a large range of machines, from laptops to supercomputers. In this paper, we compare the capabilities of quantum emulators built on the EuroHPC Karolina server using one CPU, one GPU or multiple GPUs in a single node. In terms of the number of qubits emulated, we show that while only 20+ qubits can be emulated using a single CPU, a single GPU brings this number to 30+. We also compare the timing performances, both for randomly generated quantum circuits and for Shor’s factorization algorithm. For randomly generated circuits with same depth and width, the emulators using a GPU and eight GPUs respectively are up to 20 and 180 times faster than the CPU-based emulator. For Shor’s algorithm which can have more than a million gates, the emulators using a GPU and eight GPUs respectively are up to 11 and 20 times faster than the CPU-based emulator. This benchmark of different types of quantum emulators on the Karolina server helps to choose the right parameters and make the most of the Karolina resources for future scientific work involving quantum emulation.
Exponential increase and global access to read/write memory states in quantum computing (QC) simulation limit both the number of qubits and quantum transformations which can be currently simulated. Although QC simulation is parallel by nature, spatial and temporal complexity are major performance hazards, making this a nontrivial application for high performance computing. A new methodology employing reduction and decomposition optimizations has shown relevant results, but its GPU implementation could be further improved. In this work, we develop a new kernel for in situ GPU simulation that better explores its resources without requiring further hardware. Shor’s and Grover’s algorithms are simulated up to 25 and 21 qubits respectively and compared to our previous version, to [Formula: see text] simulator and to ProjectQ framework, showing better results with relative speedups up to 4.38×, 3357.76× and 333× respectively.
Due to the expansion of transformations and read/write memory states by tensor products in multidimensional quantum applications, the exponential increase in temporal and spatial complexities constitutes one of the main challenges for quantum computing simulations. Simulation of these systems is important in order to develop and test new quantum algorithms. This work presents reduction and decomposition optimizations for the Distributed Geometric Machine environment. By exploring properties as the sparsity of the Identity operator and partiality of dense unitary transformations, better storage and distribution of quantum information are achieved. The main improvements are implemented by decreasing replication and void elements inherited from quantum operators. In the evaluation of this proposal, Shor’s algorithm considering 2n+3 qubits in the order-finding quantum algorithm was simulated up to 25 qubits over CPU, sequentially and in parallel, and over GPU. Results confirm that temporal complexity is reduced. When comparing our implementations running on the same hardware with LIQUi|i, academic release version, our new simulator was faster and allowed for the simulation of more qubits.