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-Expanded) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 96
  • Basım Tarihi: 2018
  • Doi Numarası: 10.1139/cjp-2017-0768
  • Dergi Adı: CANADIAN JOURNAL OF PHYSICS
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Sayfa Sayıları: ss.759-761
  • Karadeniz Teknik Üniversitesi Adresli: Evet

Özet

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.