Повышение быстродействия квантового алгоритма факторизации Питера Шора путём усовершенствования его классической части

Современные наукоемкие технологии. 2019. Т. 1. С. 114–118.

Смирнов И. А., Черкесова Л. В., Разумов П. В., Пилипенко И. А., Сафарьян О. А.

The proposed article compares the quantum factorization algorithm of Peter Shor and the factorization algorithm of the ?-John Pollard method. As is well known, the quantum algorithm for factoring Shor consists of classical and quantum parts. In the classical part, it is proposed to use the Euclidean algorithm to find the greatest common divisor of numbers (GCD). However, there are quite a number of algorithms for finding the greatest common divisor of numbers. The authors of this article reviewed the results of calculations of eight algorithms, among which the algorithm with the highest GOD search speed was found. This allows the quantum algorithm as a whole to work faster. In turn, this provides a great potential for the practical application of the quantum Shor algorithm. Thus, the authors modified the standard quantum algorithm of P. Shor by replacing the binary NOD search algorithm with an iterative shift algorithm, canceling the random number generation operation and using the additive chain algorithm for fast exponentiation. The obtained modified Shor’s algorithm is distinguished by higher performance and speed in the implementation of factorization. The effectiveness of this modified algorithm turned out to be, in general, higher than that of the standard Shor algorithm, due to the improvement of its classical part. As a result, the performance of the algorithm increased by 50?%.

Keywords: recursive algorithms, факторизация, qubit, кубит, quantum algorithms, factorization, the greatest common divisor, binary algorithm, iterative algorithm, квантовый алгоритм, наибольший общий делитель, бинарный алгоритм, рекурсивный алгоритм, итерационный алгоритм