DEVELOPMENT OF THE QUANTUM ALGORITHM OF SORTING NUMERICAL ELEMENTS
Abstract
Currently, the development of new information technologies does not stand still and is moving forward, creating more and more new both theoretical and practical methods, and means for solving various problems. Standing on the path of progress of all mankind. At all stages of the development of information technology, much attention has been paid and is being paid to the issues of modeling func-tioning specialized computer systems, which allow providing the necessary performance indicators in combination with minimized costs of software resources and energy consumption. The article proposes a quantum algorithm for searching and sorting N elements and reflects the developed modeling system (component) that can solve the problem. 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, such as the features of quantum bandwidth, are rather poorly illuminated in the world. The developed algorithms for various problems of complexity classes can give a significant gain in efficiency in comparison with existing classical ones and provide a solution to a number of complex mathematical (including cryptographic) problems. The aim of the work is to develop a quantum algorithm for sorting numerical elements, which will allow us to analyze the speed and advantage of quantum algorithms along with the classical models of a quantum computer within the framework of the computational process. It also consists in developing the theoretical, algo-rithmic and practical foundations for constructing a modular system for the interaction of information processes and algorithms with an open architecture. The relevance of the study is to build a modular specialized computing system for new information technologies and algorithms, analyze their perfor-mance and computational complexity, implement the theoretical foundations of creating software sys-tems for new quantum-oriented information technologies. It also consists in developing the theoretical, algorithmic and practical foundations for constructing a modular system for the interaction of infor-mation processes and algorithms with an open architecture.
References
2. Potapov V., Gushanskiy S., Guzik V., Polenov M. The Computational Structure of the Quantum Computer Simulator and Its Performance Evaluation, In: Software Engineering Perspectives and Application in Intelligent Systems. Advances in Intelligent Systems and Computing, Vol. 763, pp. 198-207. Springer, 2019.
3. Gushanskiy S.M., Potapov V.S. Razrabotka kvantovogo algoritma sortirovki chislennykh elementov [Development of a quantum algorithm for sorting numerical elements], Tekhnologii razrabotki informatsionnykh sistem TRIS-2019: Mater. konferentsii [Technologies for devel-opment of information systems TRIS-2019: conference Materials], Vol. 2. – Taganrog: Izd-vo YuFU, 2019, pp. 142-146.
4. 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.
5. 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.
6. Potapov V., Gushanskiy S., Polenov M. The Methodology of Implementation and Simulation of Quantum Algorithms and Processes, 11th International Conference on Application of In-formation and Communication Technologies (AICT). Institute of Electrical and Electronics Engineers, 2017, pp. 437-441.
7. Raedt K.D., Michielsen K., De Raedt H., Trieu B., Arnold G., Marcus Richter, Th Lip-pert, Watanabe, H., and Ito, N. Massively parallel quantum computer simulator, Computer Physics Communications, Vol. 176, pp. 121-136.
8. Boixo S., Isakov S.V., Smelyanskiy V.N., Babbush R., Ding N., Jiang Z., Martinis J.M., and Neven H. Characterizing quantum supremacy in near-term devices. arXiv pre-print arXiv:1608.00263.
9. Stierhoff G.C., Davis A.G. A History of the IBM Systems Journal, In: IEEE Annals of the His-tory of Computing, Vol. 20, Issue 1, pp. 29-35.
10. Lipschutz S., Lipson M. Linear Algebra (Schaum’s Outlines). 4th ed. McGraw Hill.
11. Collier David. The Comparative Method. In Ada W. Finifter, ed. Political Sciences: The State of the Discipline II. Washington, DC: American Science Association, pp. 105-119.
12. Vectorization. Available at: https://en.wikipedia.org/w/index.php?title=Vectorization&ldid= 829988201.
13. Williams C.P. Explorations in Quantum Computing, Texts in Computer Science, Chapter 2. Quantum Gates, pp. 51-122. Springer, 2011.
14. Olukotun K. Chip Multiprocessor Architecture – Techniques to Improve Throughput and La-tency. Morgan and Claypool Publishers, 2007.
15. Potapov V., Guzik V., Gushanskiy S., Polenov M. Complexity Estimation of Quantum Algo-rithms Using Entanglement Properties In: Informatics, Geoinformatics and Remote Sensing, Proceedings of 16-th International Multidisciplinary Scientific Geoconference, SGEM 2016, Bulgaria, Vol. 1, pp. 133-140. STEF92 Technology Ltd, 2016.
16. Inverter (logic gate). Available at: https://en.wikipedia.org/w/index.php?title=Inverter_ (log-ic_gate)&oldid=844691629.
17. Fernando G.S.L. Brandão and Michael J. Kastoryano. Finite Correlation Length Implies Effi-cient Preparation of Quantum Thermal States // Commun. Math. Phys. 365, 1 (2019), arXiv:1609.07877.
18. Potapov V., Gushanskiy S., Guzik V., Polenov M. The Computational Structure of the Quantum Computer Simulator and Its Performance Evaluation, In: Software Engineering Perspectives and Application in Intelligent Systems. Advances in Intelligent Systems and Computing, Vol. 763, pp. 198-207. Springer, 2019.
19. 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.
20. Siddhartha Das, George Siopsis, and Christian Weedbrook. Continuous-variable quantum gaussian process regression and quantum singular value decomposition of nonsparse low-rank matrices, Physical Review A, 2018, Vol. 97(2), pp. 022315.
21. Gushanskiy S.M., Potapov V.S. Metodika razrabotki i postroeniya kvantovykh algoritmov [Methods of development and construction of quantum algorithms], Informatizatsiya i svyaz' [Informatization and communication], 2017, No. 3. pp. 101-104.
22. Gushanskiy S.M., Polenov M.Yu., Potapov V.S. Realizatsiya komp'yuternogo modelirovaniya sistemy s chastitsey v odnomernom i dvukhmernom prostranstve na kvantovom urovne [Im-plementation of computer simulation of a system with a particle in one-dimensional and two-dimensional space at the quantum level], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2017, No. 3 (188), pp. 223-233.
23. Jacob Biamonte, Peter Wittek, Nicola Pancotti, Patrick Rebentrost, Nathan Wiebe, and Seth Lloyd. Quantum machine learning, Nature, 2017, Vol. 549 (7671), pp. 195-202.
24. Hales S. Hallgren, An improved quantum Fourier transform algorithm and applications, Pro-ceedings of the 41st Annual Symposium on Foundations of Computer Science. November 12–14, 2000, pp. 515.
25. Mario Motta, Chong Sun, Adrian T K Tan, Matthew J O’rourke, Erika Ye, Austin J Minnich, Fernando G S L Brandão, and Garnet Kin-Lic Chan. Quantum Imaginary Time Evolution, Quantum Lanczos, and Quantum Thermal Averaging. 2019. arXiv:1901.07653v1.
26. 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_ pro-gramming&oldid=740376291.
27. Metod vetvey i granits [Method of branches and borders], Vikipediya [Wikipedia]. [2019–2019]. Update date: 08.05.2019. Available at: https://ru.wikipedia.org/?oldid=99665783 (ac-cessed 08.05.2019).
28. Kombinatornyy poisk [Combinatorial search], Vikipediya [Wikipedia]. [2019–2019]. Update date: 29.03.2019. Available at: https://ru.wikipedia.org/?oldid=98924793 (accessed 29.03.2019).
29. Perebor deliteley [Brute force of divisors], Vikipediya [Wikipedia]. [2018–2018]. Update date: 10.07.2018. Available at: https://ru.wikipedia.org/?oldid=93855464 (accessed 10.07.2018).
