|Article title||SOFTWARE DEVELOPMENT OF QUANTUM OPTIMIZATION ALGORITHM FOR SOLUTION OF THE TRAVELING SALESMAN PROBLEM|
|Authors||S. M. Gushanskiy, V. N. Pukhovsky, V. S. Potapov|
|Section||SECTION II. MODELING AND ALGORITHMS OF INFORMATION PROCESSING|
|Month, Year||07, 2018 @en|
|Abstract||Recently, there has been a rapid increase interest in quantum computers. Their work is based on the use of quantum mechanical phenomena such as superposition and entanglement to convert input data into output, which can actually provide effective performance by 3 – 4 orders of magnitude higher than any modern computing device, which will solve the above and others tasks in natural and accelerated time scale. This article is devoted to solving the problem of research and development of methods for the functioning of quantum algorithms and models of quantum computing devices. The quantum algorithm implemented in the work allows to solve the traveling salesman problem with different dimensions, demonstrates the capabilities of quantum information theory in interpreting classical problems. The famous traveling problem of a traveling salesman is an important category of optimization problems that occurs in various fields of science and technology. The study of optimization problems motivates the development of advanced methods that are more suitable for modern practical problems. The relevance of these studies lies in the mathematical and software modeling and implementation of a quantum algorithm for solving classes of problems of a classical nature. What will be another step forward in the research of the elementary theoretical base of a quantum computing device and, as a result, the practical, physical implementation of this device. The scientific novelty of this area is primarily expressed in the constant updating and addition of the field of quantum research in a number of areas, and computer simulation of quantum physical phenomena and features is poorly covered in the world. The aim of the work is a computer simulation of a quantum algorithm for solving the traveling salesman problem using the phase estimation method, which allows us to estimate our own phase of a unitary gate that has gained access to a quantum state in proportion to its own vector.|
|Keywords||Modeling; quantum algorithm; qubit; model of a quantum computer; entanglement; superposition; quantum operator; complexity of the algorithm.|
|References||1. Kvantovaya kriptografiya [Quantum cryptography], Vikipediya [Wikipedia]. Updated: 09.12.2016. Available at: http://ru.wikipedia.org/?oldid=82377595 (accessed 07 March 2017).
2. Trubitsyn A.A. Raschet traektorii dvizheniya material'noy tochki v dvumernom (osesimmetrichnom) konservativnom pole [Calculation of the trajectory of a material point in a two-dimensional (axisymmetric) conservative field], Zhurnal vychislitel'noy matematiki i matematicheskoy fiziki. [Journal of computational mathematics and mathematical physics]. 30:7 (1990), 1113-1115; U.S.S.R. Comput. Math. Math. Phys., 30:4 (1990), 107-109.
3. Arthur Trew (Ed.), Greg Wilson (Ed.). Past, Present, Parallel: A Survey of Available Parallel Computer Systems. Springer, 1991, 392 p. ISBN 9783540196648.
4. Quantum phase estimation algorithm. (2016, Nov 03). In Wikipedia, The Free Encyclopedia. Retrieved 05:15, July 27, 2016, from https://en.wikipedia.org/ w/index.php?Title=Quantum_phase_estimation_algorithm&oldid=731732789.
5. Richard G. Milner A Short History of Spin, Contribution to the XVth International Workshop on Polarized Sources, Targets, and Polarimetry. Charlottesville, Virginia, USA, September
9-13, 2013. arXiv:1311.5016.
6. Gushanskiy S.M., Potapov V.S. Metodika razrabotki i postroeniya kvantovyh algoritmov [Methods of development and construction of quantum algorithms], Informatizatsiya i svyaz' [Informatization and communication], 2017, No. 3, pp. 101-104.
7. Gushanskiy S.M. Polenov M.Yu., Potapov V.S. Realizatsiya komp'yuternogo modelirovaniya sistemy s chastitsey v odnomernom i dvuhmernom prostranstve na kvantovom urovne [Implementation of computer simulation system with a particle in one-dimensional and two-dimensional space on a quantum level] Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2017, No. 3 (188), pp. 223-233.
8. Hales S. Hallgren. An improved quantum Fourier transform algorithm and applications, Proceedings of the 41st Annual Symposium on Foundations of Computer Science. November
12–14, 2000, pp. 515.
9. Potapov V., Gushanskiy S., Polenov M. The Methodology of Implementation and Simulation of Quantum Algorithms and Processes, 2017 11th International Conference on Application of Information and Communication Technologies (AICT). Institute of Electrical and Electronics Engineers, 2017, pp. 437-441.
10. Lukin M.D. Attractive photons in a quantum nonlinear medium, Ofer Firstenberg, Nature. October 2013, Vol. 502.
11. Nil'sen M., CHang I. Kvantovye vychisleniya i kvantovaya informatsiya = Quantum Computation and Quantum Information [Quantum computing and quantum information = Quantum Compu-tation and Quantum Information]. Moscow: Mir, 2006.
12. Quantum programming. (2016, Nov 03). In Wikipedia, The Free Encyclopedia. Retrieved 17:50, September 20, 2016, from https://en.wikipedia.org/w/index. php?title=Quantum_ programming&oldid=740376291.
13. Wikipedia contributors. (2018, November 27). IBM Q Experience. In Wikipedia, The Free Encyclopedia. Retrieved 17:28, January 31, 2019, from https://en.wikipedia.org/w /index.php?title=IBM_Q_Experience&oldid=87087480.
14. Quantum mechanics. (2017, March 29). In Wikipedia, The Free Encyclopedia. Retrieved 15:50, March 30, 2017. Available at: https://en.wikipedia.org/w/index. php?title=Quantum_ mechanics&oldid=772744105.
15. Boneh D., Zhandry M. Quantum-secure message authentication codes, In Proceedings of Eurocrypt, 2013, pp. 592-608.
16. Chris Ferrie. Quantum Physics for Babies. Brdbk edition. Sourcebooks Jabberwocky, 2017-05-02, pp. 23-24. – ISBN 9781492656227.
17. Wilde M. From Classical to Quantum Shannon Theory, arXiv:1106.1445.
18. Guzik V.F., Gushanskiy S.M., Potapov V.S. Kolichestvennye harakteristiki stepeni zaputannosti [Quantitative characteristics of the degree of confusion], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2016, No. 3 (176), pp. 76-86.
19. Potapov V., Gushansky S., Guzik V., Polenov M. Architecture and Software Implementation of a Quantum Computer Model, Advances in Intelligent Systems and Computing. Springer Verlag, 2016, Vol. 465, pp. 59-68.
20. Tomas H. Kormen, CHarl'z I. Leyzerson, Ronal'd L. Rivest, Klifford Shtayn. Algoritmy: postroenie i analiz = Introduction to Algorithms [Algorithms: construction and analysis = Introduction to Algorithms]. 2nd ed. Moscow: Vil'yams, 2006, pp. 1296. ISBN 0-07-013151-1.
21. Optimizatsiya [Optimization], Vikipediya [Wikipedia]. [2018 – 2018]. Updated: 10.08.2018. Available at: https://ru.wikipedia.org/?oldid=94448419 (accessed 10 August 2018).
22. Bennett С.H., Shor P.W., Smolin J.A., Thapliyal A.V. Entanglement-assisted Capacity of a Quantum Channel and the Reverse Shannon Theorem, IEEE Transactions on Information Theory, 48, 2637. 2002.
23. Kleppner D., Kolenkow R. An Introduction to Mechanics (Second ed.). Cambridge: Cambridge University Press, 2014, 49 p.
24. Potapov V.S., Gushanskiy S.M. Kvantovye tipy oshibok i metody ih ustraneniya, zavisimost' oshibki ot mery i chistoty zaputannosti [Quantum types of errors and their rectification, the dependence of the error of the measure and purity of entanglement], Sb. trudov XIV Vserossiyskoy nauchnoy konferentsii molodyh uchenyh, aspirantov i studentov ITSAiU-2016 [Proceedings of the XIV all-Russian scientific conference of young scientists, postgraduates and students of Itsau-2016]. Rostov-on-Don: Izd-vo YuFU, 2016, Vol. 3, pp. 123-129.