Received 17.02.2023; Revised 18.03.2023; Accepted 25.04.2023

Published 28.04.2023; First Online 23.05.2023

https://doi.org/10.34229/2707-451X.23.1.2

Previous  |  FULL TEXT (in Ukrainian)  |  Next

 

MSC 11A51

A Research of the Influence of Quantum Annealing Parameters on the Quality of the Solution of the Number Factorization Problem

Vyacheslav Korolyov ,   Oleksandr Khodzinskyi ^*

V.M. Glushkov institute of cybernetics of the NAS of Ukraine, Kyiv

^* Correspondence: This email address is being protected from spambots. You need JavaScript enabled to view it.

 

Introduction. Modern information security systems use methods of asymmetric cryptography to transfer encryption keys, which are based on the high computational complexity of factorization of large numbers. Quantum computers (QCs) theoretically make it possible to accelerate the solution of the problem of factorization of numbers in comparison with classical computers and pose a potential threat to information security systems. However, real QCs have a limited number of connections between them and problems with preserving a stable low temperature, which reduces the probability of detecting a global minimum.

The joint use of QCs with classical computers based on hybrid cloud services is advisable when the search for the optimal solution by direct methods is a complex problem both in the theoretical sense and in the sense of the required amount of calculations for tasks with specific data.

The article proposes a method for improving the accuracy of solving the factorization problem based on multiple minimum search by the method of hardware reverse quantum annealing with a variation of its parameters. The results of numerical experiments for two different QC processors and a hybrid quantum-classical computer by D-Wave are presented, it is shown that the maximum number that can be factorized exclusively by direct annealing is 143, and with a combination of direct and reverse annealing 255.

The purpose. Examination of the influence of the parameters of quantum annealing and the corresponding solutions for the adiabatic CC, developed by D-Wave, on the quality of the solution of the factorization problem. To give recommendations for improving the accuracy of solving the factorization problem and increasing the statistical frequency of the appearance of correct pairs of multipliers.

 Results. Numerical experiments have shown that for the problem of factorization of numbers, the successive application of direct and reverse annealing makes it possible to improve the probability of obtaining the correct pair of multipliers and to more than double the statistical frequency of its occurrence.

Quantum annealing modes: pause and quenching reduce the probability of obtaining the correct solution and worsen the statistical frequency of the appearance of correct pairs of multipliers.

Conclusions. The use of direct and reverse annealing makes it possible to increase the probability of obtaining the correct solution of the factorization problem for the adiabatic QC of D-Wave. Increasing the calculation time of the problem is justified, since it allows increasing the probability of a correct solution. The use of hybrid quantum-classical computing and cloud services allows factorization for numbers with a bit depth of up to twenty-two bits.

 

Keywords: quantum annealing, factorization of natural numbers, asymmetric shifts, hardening, reverse annealing, combinatorial optimization.

 

Cite as: Korolyov V., Khodzinskyi O. A Research of the Influence of Quantum Annealing Parameters on the Quality of the Solution of the Number Factorization Problem. Cybernetics and Computer Technologies. 2023. 1. P. 13–22. (in Ukrainian) https://doi.org/10.34229/2707-451X.23.1.2

 

References

           1.     Moguel E., Rojo J., Valencia D. et al. Quantum service-oriented computing: current landscape and challenges. Software Qual J. 2022. https://doi.org/10.1007/s11219-022-09589-y

           2.     Wang Y., Liu H. Quantum Computing in a Statistical Context. Annual Review of Statistics and Its Application. 2022. Vol. 9:1. P. 479–504. https://doi.org/10.1146/annurev-statistics-042720-024040

           3.     Gill S.S., Kumar A., Singh H.  Quantum computing: A taxonomy, systematic review and future directions. Software: Practice and Experience. 2022. 52 (1). P. 66–114. https://doi.org/10.1002/spe.3039

           4.     Korolyov V., Khodzinskyi O. Solving Combinatorial Optimization Problems on Quantum Computers. Cybernetics and Computer Technologies. 2020. 2. P. 5–13. (in Ukrainian) https://doi.org/10.34229/2707-451X.20.2.1

           5.     What is Quantum Annealing? https://docs.dwavesys.com/docs/latest/c_gs_2.html (accessed: 08.09.2022)

           6.     QPU Solver Datasheet https://docs.dwavesys.com/docs/latest/doc_qpu.html (accessed: 08.09.2022)

           7.     Anschuetz E., Olson J., Aspuru-Guzik A., Cao Y. Variational Quantum Factoring. In: Feld, S., Linnhoff-Popien, C. (eds) Quantum Technology and Optimization Problems. QTOP 2019. (Lecture Notes in Computer Science). Vol. 11413. Springer, Cham. https://doi.org/10.1007/978-3-030-14082-3_7

           8.     Variational Quantum Factoring. https://github.com/mstechly/vqf (accessed: 08.09.2022)

           9.     D-Wave Examples. Factoring. https://github.com/dwave-examples/factoring (accessed: 08.09.2022)

       10.     Li Z.K., Dattani N.S., Chen X., Liu X. High-fidelity Adiabatic Quantum Computation Using the Intrinsic Hamiltonian of a Spin System: Application to the Experimental Factorization of 291311. Quantum Physics. 2017. P. 1–6. https://doi.org/10.48550/arXiv.1706.08061

       11.     Jiang S., Britt K.A., McCaskey A.J. et al. Quantum Annealing for Prime Factorization. Scientific Report. 2018. 8. 17667. P. 1–9. https://doi.org/10.1038/s41598-018-36058-z

       12.     Gidney C. Factoring with N+2 Clean Qubits and N-1 Dirty Qubits. Quantum Physics. 2018. P. 1–14. https://doi.org/10.48550/arXiv.1706.07884

       13.     Kieu T.D. A factorisation algorithm in Adiabatic Quantum Computation. Journal of Physics Communications. 3. 17667. 2019. https://doi.org/10.1088/2399-6528/ab060d

       14.     Baonan W., Feng H., Haonan Y., Chao W. Prime Factorization Algorithm Based on Parameter Optimization of Ising Model. Scientific Report. 2020. 10. 7106. P. 1–10. https://doi.org/10.1038/s41598-020-62802-5

       15.     Peng W., Wang B., Hu F. et al. Factoring larger integers with fewer qubits via quantum annealing with optimized parameters. Science China Physics, Mechanics, Astronomy. 2019. 62 (6). 60311. https://doi.org/10.1007/s11433-018-9307-1

       16.     Warren R. H. Factoring on a Quantum Annealing Computer. Quantum Information and Computation. 2019. 19 (3–4). P. 252–261. https://doi.org/10.26421/qic19.3-4-5

       17.     Wang B., Yang X., Zhang D. Research on Quantum Annealing Integer Factorization Based on Different Columns. Frontier Physics. 2022. 10. 914578. https://doi.org/10.3389/fphy.2022.914578

       18.     Factoring with Reverse Annealing. https://github.com/novice108/factorQuant/blob/main/factorRVS.py (accessed: 19.01.2023)

       19.     Korolyov V., Ogurtsov M., Khodzinsky A. Multilevel Identification Friend or Foe of Objects and Analysis of the Applicability of Post-Quantum Cryptographic Algorithms for Information Security. Cybernetics and Computer Technologies. 2020. 3. P. 74–84. (in Ukrainian) https://doi.org/10.34229/2707-451X.20.3.7

 

 

ISSN 2707-451X (Online)

ISSN 2707-4501 (Print)

Previous  |  FULL TEXT (in Ukrainian)  |  Next