F.K. Aliev1, A.P. Baranov2, A.V. Ivakhin3, A.V. Korolkov4, V.I. Rudskoy5, A.G. Sentsov6

1 Department of Information Systems of the Ministry of Defense of the Russian Federation (Moscow, Russia)
2 JSC «Design Bureau «Korund-M» (Moscow, Russia)
3 JSC «SberTech» (Moscow, Russia)
4 FSBI VO Russian Technological University – MIREA (Moscow, Russia)
5 Technical Committee (TC26) «Cryptography and security mechanisms» (Moscow, Russia)
6 Institute of Nanotechnologies of Microelectronics RAS (Moscow, Russia)
 

Quite a lot of computationally complex problems of practical importance are reduced to the NP-complete 3SAT problem, that is, reduced to a system of equations in 3-form. Therefore, the development of algorithms for solving systems of equations in 3-form is an urgent task. This is on the one hand.

On the other hand, encouraging results have appeared in the field of creation and application of quantum computers. We are talking about the Chinese quantum photonic computers Jiuzhang and Jiuzhang 2.0, which appeared in 2020 and 2021, respectively, as well as the Canadian Borealis quantum photonic computer, which appeared in 2022. It turned out that the problem of estimating (that is, calculating an approximate value) of the permanents of matrices of certain classes is a computational problem, for the solution of which quantum computers can be used, the prototypes of which are the above computers.

Against the background of the above results in the field of creation and application of quantum photonic computers, Alexander Pavlovich Baranov, a full member of the Academy of Cryptography of the Russian Federation, set the problem of developing an algorithm for solving a system of Boolean equations in 3-form based on the use of estimates of matrix permanents. In our article, the short name of this problem is adopted – PAB, according to the first letters of the words: the problem of academician Baranov. A limited version of this problem (for solving joint systems of Boolean equations in 3-form with a unique solution) is called LPAB in the article, after the first letters of the words: the limited problem of academician Baranov.

The article is devoted to the solution of PAB and LPAB. The following main results have been obtained:

a criterion for the inconsistency of a system of Boolean equations in 3-form is formulated, based on checking that the permanent of the matrix defined by this system is equal to zero;

algorithm 1 for solving PAB was developed and presented; algorithm 1 is based on the use of the inconsistency criterion for a system of Boolean equations in 3-form, which uses the equality of the corresponding matrix permanent to zero as a sign of inconsistency;

algorithm 2 for solving LPAB was developed and presented; algorithm 2 is much simpler than algorithm 1; it is possible to achieve such a simplification due to the imposed additional condition for the uniqueness of the solution of the system of Boolean equations in the 3-form; algorithm 2, as well as algorithm 1, assumes the use of the inconsistency criterion for a system of Boolean equations in 3-form based on the inconsistency criterion, which consists in the equality of the corresponding matrix permanent to zero.

Aliev F.K., Baranov A.P., Ivakhin A.V., Korolkov A.V., Rudskoy V.I., Sentsov A.G. Mathematical foundations for the application of quantum photonic computer technology for solving computational problems of high-availability systems. Highly Available Systems. 2023. V. 19. № 1. P. 14−27. DOI: https://doi.org/10.18127/j20729472-202301-02 (in Russian)

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 (data obrashcheniya: 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. Sokolov I.A., Budzko V.I., Sinicyn I.N. Postroenie informacionno-telekommunikacionnyh sistem vysokoj dostupnosti // Sistemy vysokoj dostupnosti. 2005. №1. S. 6–14.
5. Aliev F.K., Korol'kov A.V., Matveev E.A. Kvantovaya fotonnaya komp'yuternaya tekhnologiya resheniya slozhnyh vychislitel'nyh zadach sistem vysokoj dostupnosti // Sistemy vysokoj dostupnosti. 2021. T. 17. № 4. S. 34–54. DOI: https://doi.org/10.18127/j20729472-202104-03
6. Sachkov V.N. Kurs kombinatornogo analiza. M.–Izhevsk: NIC «Regulyarnaya i haoticheskaya dinamika». 2013. 336 s.
7. Valiant L. The complexity of computing the permanent. Theoretical Computer Science, 8: 189–201, 1979.
8. Geri M., Dzhonson D. Vychislitel'nye mashiny i trudnoreshaemye zadachi / Per. s angl. M.: Mir. 1982. 416 s.
9. Gorshkov S.P., Tarasov A.V. Slozhnost' resheniya bulevyh uravnenij: Monografiya. M.: KURS. 2017. 192 s.
10. Kormen T., Lejzerson CH., Rivest R. Algoritmy: postroenie i analiz. M.: MCNMO. 1999. 960 s.
11. Stivens R. Algoritmy. Teoriya i prakticheskoe primenenie. M.: Eksmo. 2020. 544 s.
12. Dasgupta S., Papadimitriu H., Vazirani U. Algoritmy / Per. s angl. M.: MCNMO. 2014. 320 s.
13. Maslennikov O.V., Aliev F.K., Bespalov S.A., Mishin V.E. Vychislitel'nye sistemy voennogo naznacheniya: perspektivy razvitiya v sovremennyh usloviyah // Voennaya mysl'. 2022. № 6. S. 71–78.
14. Maslennikov O.V., Aliev F.K., Bespalov S.A., Mitroshin E.S. O vychislitel'noj slozhnosti sovremennyh voennyh zadach // Voennaya mysl'. 2023. № 2. S. 72–85.