УДК 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.
