УДК 004.383
КВАНТОВІ ОБЧИСЛЕННЯ: ОГЛЯД ТА АНАЛІЗ
Анотація. Зроблено огляд та аналіз основних понять і положень квантової моделі обчислень,
ефективних квантових алгоритмів, останніх результатів, можливостей та перспектив у побудові масштабованого к
вантового комп’ютера. Розглянуто певний клас алгебраїчних задач у квантовій моделі обчислень, для яких існує
ефективний квантовий алгоритм розв’язку. Проведено детальний аналіз наявних практичних реалізацій квантового комп’ютера.
Показано, що на сьогодні немає достатнього прогресу у побудові масштабованого квантового обчислювального пристрою,
проте більшість дослідників очікують на створення повноцінного квантового комп’ютера впродовж наступних 10–15 років.
Ключові слова: квантова модель обчислень, квантова криптографія, квантовий комп’ютер,
ефективні квантові алгоритми, постквантові криптографічні примітиви.
ПОВНИЙ ТЕКСТ
Савчук Михайло Миколайович,
чл.-кор. НАН України, доктор фіз.-мат. наук, в.о. завідувача кафедри Національного технічного університету України «Київський політехнічний інститут імені Ігоря Сікорського»,
mikhail.savchuk@gmail.com
Фесенко Андрій В’ячеславович,
кандидат фіз.-мат. наук, старший викладач Національного технічного університету України «Київський політехнічний інститут імені Ігоря Сікорського»,
andrey.fesenko@gmail.com
СПИСОК ЛІТЕРАТУРИ
- Bennett C., Brassard G. Quantum cryptography: Public-key distribution and coin tossing. Proc. International Conference on Computers, Systems and Signal Processing (Bangalore, India. 1984). P. 175–179.
- Квантовый компьютер и квантовые вычисления. Ижевск: Ижевская республиканская типография, 1999. 288 с.
- Прескилл Дж. Квантовая информация и квантовые вычисления. Том 1. Москва-Ижевск: НИЦ «Регулярная и хаотическая динамика»; Институт компьютерных исследований, 2008. 464 с.
- Ааронсон С. Квантовые вычисления со времен Демокрита. Москва: Альпина нон-пикшн, 2018. 494 с.
- Савчук М.Н. О работах киевской школы теоретической криптографии. Кибернетика и системный аналіз. 2010. Т. 46, № 3. С. 52–68.
- Nielsen M.A., Chuang I.L. Quantum computation and quantum information. Cambridge: Cambridge University Press,. 2000. 676 p.
- Kitaev A. Quantum computations: algorithms and error correction. Russian Mathematical Surveys. 1997. Vol. 52, N 6. P. 53–112.
- Yao A. Quantum circuit complexity. Proc. 34th Annual Symposium on Foundations of Computer Science. 1993. P. 352–361.
- Boneh R., Lipton R. Quantum cryptanalysis of hidden linear functions. Proc. 15th Annual International Cryptology Conference, (Santa Barbara, California, USA, August 27, 1995). Advances in Cryptology. Crypto’95. Lecture Notes in Computer Science. 1995. Vol. 31. P. 424–437.
- Deutsch D., Jozsa R. Rapid solution of problems by quantum computation. Proc. Royal Society of London, Series A. 1992. N 439. P. 553–558.
- Shor P.W. Algorithms for quantum computation: discrete logs and factoring. Proc. 35th Symposium on the Foundations of Computer Science (20–22 Nov. 1994, Santa Fe, NM, USA), 1994. P. 124–134.
- Shor P.W. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing. 1997. Vol. 26, Iss. 5. P. 1484–1509.
- van Dam W., Hallgren S., Ip L. Quantum algorithms for some hidden shift problems. SIAM Journal on Computing. 2006. Vol. 36, N 3. P. 763–778.
- Фесенко А.В. Уязвимости криптопримитивов на основе задачи поиска сопрягающего элемента и степени в квантовой модели вичислений. Кибернетика и системный аналіз. 2014. Т. 50, № 5. С. 184–186.
- Bian Z., Chudak F., Macready W., Clark L. , Gaitan F. Experimental determination of Ramsey numbers. Physical Review Letters. 2012 Vol. 111, Iss. 13. P. 130505. DOI: https://doi.org/10.1103/PhysRevLett.111.130505. URL: https://arxiv.org/abs/1201.1842
- Cho A. Quantum or not, controversial computer yields no speedup. Science. 2014. Vol. 344, N 6190. P. 1330–1331. DOI: https://doi.org/10.1126/science.344.6190.1330.
- Dattani N.S. , Bryans N. Quantum factorization of 56153 with only 4 qubits. Quantum Physics Archive. arXiv:1411.6758 [quant-ph]. 2014. URL: https//arxiv.org/abs/1411.6758.
