Quantum modular multiplier via binary-exponent-based recombination

Shor’s factoring algorithm contains controlled modular exponentiation which can be further reduced as a series of controlled modular multipliers with constant. For the controlled modular multiplier with constant, this paper proposes a binary-exponent-based recombination (BER) protocol which could su...

Full description

Saved in:
Bibliographic Details
Published in:Quantum information processing 2022-11, Vol.21 (12), Article 391
Main Authors: He, Yongcheng, Zhao, Changhao, Dai, Genting, He, Kaiyong, Geng, Xiao, Liu, Jianshe, Chen, Wei
Format: Article
Language:English
Subjects:
Data Structures and Information Theory
Mathematical Physics
Physics
Physics and Astronomy
Quantum Computing
Quantum Information Technology
Quantum Physics
Spintronics
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Shor’s factoring algorithm contains controlled modular exponentiation which can be further reduced as a series of controlled modular multipliers with constant. For the controlled modular multiplier with constant, this paper proposes a binary-exponent-based recombination (BER) protocol which could substantially reduce the number of addends. Based on the BER protocol, BER algorithms are constructed by the topdown hierarchy of controlled modular exponentiation, controlled modular multiplier with constant, controlled modular adder and plain adders. A complexity analysis reveals that BER algorithm reduces the number of plain adders in the controlled modular exponentiation by an average of about 42% compared with Vedral–Barenco–Ekert algorithm, thus significantly decreasing the depth and total Toffoli gates of the quantum circuits. The BER protocol can be widely used in various controlled modular multipliers as a promising ingredient of quantum factoring algorithm.
ISSN:1573-1332
1573-1332
DOI:10.1007/s11128-022-03736-x