Shor’s factorization algorithm, as one of the most significant achievements in quantum computing, exhibits an exponential speedup compared to the corresponding classical algorithm. In Shor’s factorization algorithm, modular exponentiation is one of the most computationally intensive components, which relies on the modular addition. This work aims to explore novel designs for enhancing the efficiency of quantum modular addition. In particular, we introduce a novel quantum modular addition framework based on carry-save architecture, which facilitates the conversion of multiple 2-addend quantum operations within modular addition into a single 3-addend operation, thereby reducing the computational depth. Compared to the most efficient existing quantum modular addition, our design has achieved an impressive result - a reduction in Toffoli Depth by up to 33.33%, while maintaining comparable Toffoli Count and Qubit Count. Additionally, we propose a refined framework that incorporates constant moduli to further enhance performance. This research underscores the potential of carry-save architecture as a promising technique for accelerating quantum modular arithmetic as well as advancing the development of quantum computing in general.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Quantum Carry-Save Modular Addition with Optimized Depth and Resource Utilization

  • Siyi Wang,
  • Eugene Lim,
  • Xiufan Li,
  • Jerrie Feng,
  • Anupam Chattopadhyay

摘要

Shor’s factorization algorithm, as one of the most significant achievements in quantum computing, exhibits an exponential speedup compared to the corresponding classical algorithm. In Shor’s factorization algorithm, modular exponentiation is one of the most computationally intensive components, which relies on the modular addition. This work aims to explore novel designs for enhancing the efficiency of quantum modular addition. In particular, we introduce a novel quantum modular addition framework based on carry-save architecture, which facilitates the conversion of multiple 2-addend quantum operations within modular addition into a single 3-addend operation, thereby reducing the computational depth. Compared to the most efficient existing quantum modular addition, our design has achieved an impressive result - a reduction in Toffoli Depth by up to 33.33%, while maintaining comparable Toffoli Count and Qubit Count. Additionally, we propose a refined framework that incorporates constant moduli to further enhance performance. This research underscores the potential of carry-save architecture as a promising technique for accelerating quantum modular arithmetic as well as advancing the development of quantum computing in general.