Accelerating Shor's factorization algorithm on GPUs

Creative Commons License

Savran I., Demirci M. , Yilmaz A. H.

CANADIAN JOURNAL OF PHYSICS, cilt.96, ss.759-761, 2018 (SCI İndekslerine Giren Dergi) identifier identifier

  • Cilt numarası: 96
  • Basım Tarihi: 2018
  • Doi Numarası: 10.1139/cjp-2017-0768
  • Sayfa Sayıları: ss.759-761


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.5x speedup over single-core algorithm and 20.5x speedup over Liquid.