Accelerating Shor's factorization algorithm on GPUs

Creative Commons License

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

CANADIAN JOURNAL OF PHYSICS, vol.96, pp.759-761, 2018 (SCI-Expanded) identifier identifier

  • Publication Type: Article / Article
  • Volume: 96
  • Publication Date: 2018
  • Doi Number: 10.1139/cjp-2017-0768
  • Journal Name: CANADIAN JOURNAL OF PHYSICS
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Page Numbers: pp.759-761
  • Karadeniz Technical University Affiliated: Yes

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