Speed improvement of the quantum factorization algorithm of P. Shor by upgrade its classical part
| Autor: | Larissa V. Cherckesova, Olga Safaryan, Pavel Razumov, Yuriy I. Ivanov, Irina A. Pilipenko, Ivan A. Smirnov |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
lcsh:GE1-350
Computer science Random number generation 02 engineering and technology 021001 nanoscience & nanotechnology 01 natural sciences Euclidean algorithm Computer Science::Emerging Technologies Factorization 0103 physical sciences Greatest common divisor Quantum algorithm Standard algorithms 010307 mathematical physics 0210 nano-technology Algorithm Quantum lcsh:Environmental sciences Energy (signal processing) |
| Zdroj: | E3S Web of Conferences, Vol 224, p 01016 (2020) |
| ISSN: | 2267-1242 |
| DOI: | 10.1051/e3sconf/202022401016 |
| Popis: | 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%. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|