Ф.К. Алиев1, Е.Г. Букин2, А.В. Корольков3, Е.А. Матвеев4

1 Департамент информационных систем МО РФ (Москва, Россия)

2 Научно-техническое предприятие «Криптософт» (г. Пенза, Россия)

3 ФГБУ ВО Российский технологический университет – МИРЭА (Москва, Россия)

4 Научно-техническое предприятие «Криптософт» (г. Пенза, Россия)

Постановка проблемы. В декабре 2020 г. специалистами из Китая было заявлено [1] о достижении квантового превосходства [2] на основе применения разработанного и построенного ими квантового фотонного компьютера «Цзючжан» для решения задачи отбора проб бозонов из заданного распределения [2, 3]. Данное событие означало достижение существенных результатов в развитии и применении квантовой вычислительной технологии, реализуемой с использованием линейных оптических квантовых компьютеров [2], одним из прототипов которых и является китайский квантовый фотонный компьютер «Цзючжан» [1]. Научная проблема, рассматриваемая в статье, заключается в расширении спектра применений указанной квантовой вычислительной технологии путем разработки и описания способа решения с использованием данной технологии очень важной для практических приложений (в том числе и в области разработки, внедрения и развития систем высокой доступности [4, 5]) задачи вычисления приближенного значения (оценки) перманента квадратной матрицы над полем действительных чисел.

Цель. Разработать и описать способ решения с использованием квантовой фотонной компьютерной технологии задачи оценки перманента квадратной матрицы; указать классы матриц, для которых данный способ вычислительно эффективен.

Результаты. Представлен способ решения с использованием квантовой фотонной компьютерной технологии задачи оценки перманента квадратной матрицы. Обоснована эффективность предложенного способа для оценки перманентов матриц из следующих классов: класс симметрических матриц, собственные значения которых по модулю не превосходят число 1; класс ортогональных матриц; класс дважды стохастических матриц.

Практическая ценность. Результаты, представленные в данной статье, расширяют и существенно усиливают арсенал методов и способов решения задач, возникающих на различных этапах жизненного цикла систем высокой доступности [4, 5].

Алиев Ф.К., Букин Е.Г., Корольков А.В., Матвеев Е.А. Квантовая фотонная компьютерная технология решения сложных вычислительных задач систем высокой доступности // Системы высокой доступности. 2021. Т. 17. № 4. С. 34−54. DOI: https://doi.org/ 10.18127/j20729472-202104-03

1. Han-Sen Zhong, Hui Wang, Yu-Hao Deng et al. Quantum computational advantage using photons. URL: https://science.sciencemag.org/.content/370/6523/1460.full (дата обращения: 25.03.2021).
2. Ааронсон С. Квантовые вычисления со времен Демокрита / Скотт Ааронсон; Пер. с англ. М.: Альпина нон-фикшн. 2018. 494 с.
3. Aaronson S., Arkhipov A. The computational complexity of linear optics. In Proceedings of Annual ACM Symposium on Theory of Computing (2011). Р. 333–342.
4. Синицын И.Н., Шаламов А.С. Новый подход к управлению стоимостью полного жизненного цикла систем высокой доступности // Системы высокой доступности. 2014. № 2. С. 54–60.
5. Соколов И.А., Будзко В.И., Синицын И.Н. Построение информационно-телекоммуникационных систем высокой доступности // Системы высокой доступности. 2005. № 1. С. 6–14.
6. Гэри М., Джонсон Д. Вычислительные машины и трудно решаемые задачи / Пер. с англ. М.: Мир. 1992. 416 с.
7. Дасгупта С., Пападимитриу Х., Вазирани У. Алгоритмы / Пер. с англ. М.: МЦНМО. 2014. 340 с.
8. Скиена С. Алгоритмы. Руководство по разработке / Пер. с англ. СПб.: БХВ – Петербург. 2021. 720 с.
9. Японский суперкомпьютер Fugaku упрочил свое лидерство в списке TOP500. URL: https.//www.ixbt.com/.news/2020/ 11/18/japonskij-superkompjuter-fugaku-uprochil-svoe-liderstvo-v-spiske-top500.html (дата обращения: 25.03.2021).
10. Для системы СИ предложили новые приставки. URL: https://naukatv.ru/news/24915 (дата обращения: 25.03.2021).
11. Troyansky L., Tishby N. Permanent uncertainty: On the quantum evaluation of the determinant and the permanent of a matrix. In Proceedings of PhysComp. 1996.
12. Минк Х. Пераненты / Пер. с англ. М.: Мир. 1982. 213 с.
13. Рыбников К.А. Введение в комбинаторный анализ. М.: Изд-во МГУ. 1985. 312 с.
14. Сачков В.Н. Комбинаторные методы дискретной математики. М.: Наука. 1977. 320 с.
15. Сачков В.Н. Введение в комбинаторные методы дискретной математики. М.: Наука. 1982. 384 с.
16. Сачков В.Н., Тараканов В.Е. Комбинаторика неотрицательных матриц. М.: ТВП. 2000. 448 с.
17. Сачков В.Н. Курс комбинаторного анализа. М.–Ижевск: НИЦ «Регулярная и хаотическая динамика». 2013. 336 с.
18. Эвнин А.Ю. Перманент матрицы и его вычисление // Математическое образование. 2008. № 2(46). С. 45–49.
19. Jerrum M., Sinclair A., Vigoda E. A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries. In Proc. 33rd ACM Symp. Theory of Computing. 2001. Р. 712–721.
20. Ланкастер П. Теория матриц / Пер. с англ. М.: Наука. 1982. 272 с.
21. Нильсен М., Чанг И. Квантовые вычисления и квантовая информация / Пер. с англ. М.: Мир. 2006. 824 с.
22. Савельев Л.Я. Комбинаторика и вероятность. М.: ЛЕНАНД. 2021. 424 с.
23. Просолов В.В. Задачи и теоремы линейной алгебры. М.: МЦНМО. 2015. 576 с.