РАЗРАБОТКА КВАНТОВОГО АЛГОРИТМА СОРТИРОВКИ ЧИСЛЕННЫХ ЭЛЕМЕНТОВ

  • С. М. Гушанский Южный Федеральный Университет
  • В.С. Потапов Южный Федеральный Университет
Ключевые слова: Квантовый алгоритм, запутанность, кубит, квантовый гейт, квантовый симулятор

Аннотация

В настоящее время развитие новых информационных технологий не стоит на месте и движется вперед, создавая все новые и новые как теоретические, так и практические методы, и средства для решения различных задач. Стоящих на пути прогресса всего чело-вечества. На всех этапах развития информационных технологий уделялось и уделяется в настоящее время большое внимание вопросам моделирования функционирующих специали-зированных вычислительных систем, позволяющих обеспечивать необходимые показатели по быстродействию в сочетании с минимизированными затратами программных ресурсов и потребляемой энергии. В статье предложен квантовый алгоритм поиска и сортировки N элементов и отражена разработанная моделирующая система (компонент), способная решить задачу. Научная новизна данного направления в первую очередь выражается в по-стоянном обновлении и дополнении поля квантовых исследований по ряду направлений, а компьютерная симуляция квантовых физических явлений и особенностей, таких как осо-бенности квантовой пропускной способности достаточно слабо освещена в мире. Разра-ботанные алгоритмы для различных задач классов сложности могут дать существенный выигрыш по эффективности в сравнении с существующими классическими и обеспечить решение ряда сложных математических (в том числе криптографических) задач. Целью работы является разработка квантового алгоритма сортировки численных элементов, что позволит проанализировать быстродействие и преимущество квантовых алгоритмов наряду с классическими в рамках вычислительного процесса модели квантового вычислите-ля. А также заключается в разработке теоретических, алгоритмических и практических основ построения модульной системы для взаимодействия информационных процессов и алгоритмов с открытой архитектурой. Актуальность исследования заключается в по-строении модульной специализированной вычислительной системы для новых информационных технологий и алгоритмов, анализ их производительности и вычислительной слож-ности, реализации теоретических основ создания программных систем для новых инфор-мационных технологий квантовой направленности. А также заключается в разработке теоретических, алгоритмических и практических основ построения модульной системы для взаимодействия информационных процессов и алгоритмов с открытой архитектурой.

Литература

1. Lachowicz P. Walsh – Hadamard Transform and Tests for Randomness of Financial Return-Series. Available at: http://www.quantatrisk.com/2015/04/07/walsh-hadamard-transform-python-tests-for-randomness-of-financial-return-series/ (2015).
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).
Опубликован
2020-01-23
Выпуск
Раздел
РАЗДЕЛ I. АЛГОРИТМЫ ОБРАБОТКИ ИНФОРМАЦИИ