文章基本信息

标题：Speed improvement of the quantum factorization algorithm of P. Shor by upgrade its classical part
其他标题：Speed improvement of the quantum factorization algorithm of P. Shor by upgrade its classical part
本地全文：下载
作者：Larissa Cherckesova ; Olga Safaryan ; Pavel Razumov 等
期刊名称：E3S Web of Conferences
印刷版ISSN：2267-1242
电子版ISSN：2267-1242
出版年度：2020
卷号：224
页码：1016
DOI：10.1051/e3sconf/202022401016
出版社：EDP Sciences
摘要：This report discusses Shor’s quantum factorization algorithm and ρ–Pollard’s factorization algorithm. Shor’s quantum factorization algorithm consists of classical and quantum parts. In the classical part, it is proposed to use Euclidean algorithm, to find the greatest common divisor (GCD), but now exist large number of modern algorithms for finding GCD. Results of calculations of 8 algorithms were considered, among which algorithm with lowest execution rate of task was identified, which allowed the quantum algorithm as whole to work faster, which in turn provides greater potential for practical application of Shor’s quantum algorithm. Standard quantum Shor’s algorithm was upgraded by replacing the binary algorithm with iterative shift algorithm, canceling random number generation operation, using additive chain algorithm for raising to power. Both Shor’s algorithms (standard and upgraded) are distinguished by their high performance, which proves much faster and insignificant increase in time in implementation of data processing. In addition, it was possible to modernize Shor’s quantum algorithm in such way that its efficiency turned out to be higher than standard algorithm because classical part received an improvement, which allows an increase in speed by 12%.