Ф.К. Алиев1, А.П. Баранов2, А.В. Ивахин3, А.В. Корольков4, В.И. Рудской5, А.Г. Сенцов6

1 Министерство обороны РФ, департамент информационных систем (Москва, Россия)
2 АО «КБ «Корунд-М» (Москва, Россия)
3 АО «СберТех» (Москва, Россия)
4 ФГБУ ВО Российский технологический университет – МИРЭА (Москва, Россия)
5 Технический комитет по стандартизации «криптографическая защита информации» (ТК26) (Москва, Россия)
6 Институт нанотехнологий микроэлектроники Российской академии наук (ИНМЭ РАН) (Москва, Россия)
 

Постановка проблемы. В 2020–2022 гг. появились весьма обнадеживающие результаты в направлении создания фотонных вычислителей, использующих квантовый ресурс суперпозиции. Речь идет о китайских квантовых фотонных компьютерах Цзючжан (Jiuzhang) [1] и Цзючжан-2 (Jiuzhang 2.0) [2], а также о канадском фотонном компьютере Бореалис (Borealis) [3].

Подобные квантовые фотонные компьютеры могут быть использованы для решения сложных вычислительных задач
(в первую очередь задач, возникающих в области разработки, внедрения и развития систем высокой доступности [4]). Было установлено [5], что соответствующая технология решения задач под названием «квантовая фотонная компьютерная технология решения сложных вычислительных задач систем высокой доступности» позволяет применить квантовые компьютеры, подобные указанным выше, для решения очень важной для практических приложений задачи вычисления приближенных значений (оценки) перманентов матриц [6] из некоторых классов матриц над полем действительных чисел. В то же самое время известно, что достаточно много вычислительно сложных задач сводится к задаче решения систем булевых уравнений в 3-форме. Задача решения таких систем булевых уравнений связана с решением NP-полной задачи 3SAT [7–9]. Таким образом, становиться актуальной разработка алгоритмов решения систем булевых уравнений в 3-форме путем оценки перманентов. Эта научная проблема и является предметом рассмотрения в данной статье, так как положительные сдвиги в ее решении расширяют возможности для эффективного применения квантовых компьютеров при решении вычислительно сложных задач. Задача разработки алгоритма для решения систем булевых уравнений в 3-форме путем оценок перманентов (в тексте статьи для этой задачи используется краткое название ЗАБ по первым буквам словосочетания: задача академика Баранова) и ее ограниченный вариант (задача разработки алгоритма для решения совместных систем булевых уравнений в 3-форме с единственным решением, краткое название ОЗАБ по первым буквам словосочетания: ограниченная задача академика Баранова) впервые были сформулированы действительным членом Академии криптографии Российской Федерации Барановым Александром Павловичем.

Цель. Разработать алгоритмы решения ЗАБ и ОЗАБ.

Результаты. Разработаны и представлены алгоритмы решения ЗАБ и ОЗАБ. При этом разработанные алгоритмы основаны на решении задач проверки равенства нулю перманентов матриц, определяемых по системам булевых уравнений в 3-форме.

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

Алиев Ф.К., Баранов А.П., Ивахин А.В., Корольков А.В., Рудской В.И., Сенцов А.Г. Математические основы применения квантовой фотонной компьютерной технологии решения сложных вычислительных задач систем высокой доступности // Системы высокой доступности. 2023. Т. 19. № 1. С. 14–27. DOI: https://doi.org/ 10.18127/j20729472-202301-02

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.01.2023).
2. Han-Sen Zhong et al. Phase Programmable Gaussian Boson Sampling Using Stimulated Squeezed Light. Phys. Rev. Lett. 127/180502 Published 25 October 2021.
3. Lars S. Madsen et al. Quantum computational advantage with a programmable fotonic proceccor. Nature. V. 606, Р. 75–81. (2022). DOI: 10.1038/s41586-022-04725-x
4. Соколов И.А., Будзко В.И., Синицын И.Н. Построение информационно-телекоммуникационных систем высокой доступности // Системы высокой доступности. 2005. №1. С. 6–14.
5. Алиев Ф.К., Корольков А.В., Матвеев Е.А. Квантовая фотонная компьютерная технология решения сложных вычислительных задач систем высокой доступности // Системы высокой доступности. 2021. Т. 17. № 4. С. 34–54. DOI: https://doi.org/10.18127/ j20729472-202104-03
6. Сачков В.Н. Курс комбинаторного анализа. М.–Ижевск: НИЦ «Регулярная и хаотическая динамика». 2013. 336 с.
7. Valiant L. The complexity of computing the permanent. Theoretical Computer Science, 8: 189–201, 1979.
8. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи / Пер. с англ. М.: Мир. 1982. 416 с.
9. Горшков С.П., Тарасов А.В. Сложность решения булевых уравнений: Монография. М.: КУРС. 2017. 192 с.
10. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М.: МЦНМО. 1999. 960 с.
11. Стивенс Р. Алгоритмы. Теория и практическое применение. М.: Эксмо. 2020. 544 с.
12. Дасгупта С., Пападимитриу Х., Вазирани У. Алгоритмы / Пер. с англ. М.: МЦНМО. 2014. 320 с.
13. Масленников О.В., Алиев Ф.К., Беспалов С.А., Мишин В.Е. Вычислительные системы военного назначения: перспективы развития в современных условиях // Военная мысль. 2022. № 6. С. 71–78.
14. Масленников О.В., Алиев Ф.К., Беспалов С.А., Митрошин Е.С. О вычислительной сложности современных военных задач // Военная мысль. 2023. № 2. С. 72–85.