F.K. Aliyev1, E.G. Bukin2, A.V. Korolkov3, E.A. Matveev4

1 Department of Information Systems of the Ministry of Defense of the Russian Federation (Moscow, Russia)

2 Cryptosoft Scientific and Technical Enterprise (Penza, Russia)

3 FSBI VO Russian Technological University – MIREA (Moscow, Russia)

4 Cryptosoft Scientific and Technical Enterprise (Penza, Russia)

We consider the problem of calculating the approximate value (estimate) of the permanent of a square matrix over the field of real numbers using a photonic quantum computer that sampling bosons from a given distribution. It is pointed out that it is possible to effectively solve this problem for the following three classes of matrices: symmetric matrices which eigenvalues do not exceed 1 in absolute value; orthogonal matrices; doubly stochastic matrices. For the last two classes, we are talking about evaluating the square of the permanent.

The mathematical basis for solving the problem is the formula, which represents the permanent of the Hermitian matrix as the mathematical expectation of some random variable which values are equal to the products of the powers of the eigenvalues of the Hermitian matrix. And the corresponding probabilities with which these products are accepted as values of a random variable are also completely determined by the same Hermitian matrix. This circumstance allows using the methods of probability theory in order to solve the problem of permanent estimation.

Aliyev F.K., Bukin E.G., Korolkov A.V., Matveev E.A. Quantum photonic computer technology for solving complex computational problems of high availability systems. Highly Available Systems. 2021. V. 17. № 4. P. 34−54. DOI: https://doi.org/10.18127/j20729472-202104-03 (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.03.2021).
2. Aaronson S. Kvantovye vychisleniya so vremen Demokrita. Skott Aaronson; Per. s angl. M.: Al'pina non-fikshn. 2018. 494 s.
3. Aaronson S., Arkhipov A. The computational complexity of linear optics. In Proceedings of Annual ACM Symposium on Theory of Computing (2011). R. 333–342.
4. Sinicyn I.N., SHalamov A.S. Novyj podhod k upravleniyu stoimost'yu polnogo zhiznennogo cikla sistem vysokoj dostupnosti. Sistemy vysokoj dostupnosti. 2014. № 2. S. 54–60.
5. Sokolov I.A., Budzko V.I., Sinicyn I.N. Postroenie informacionno-telekommunikacionnyh sistem vysokoj dostupnosti. Sistemy vysokoj dostupnosti. 2005. № 1. S. 6–14.
6. Geri M., Dzhonson D. Vychislitel'nye mashiny i trudno reshaemye zadachi. Per. s angl. M.: Mir. 1992. 416 s.
7. Dasgupta S., Papadimitriu H., Vazirani U. Algoritmy. Per. s angl. M.: MCNMO. 2014. 340 s.
8. Skiena S. Algoritmy. Rukovodstvo po razrabotke. Per. s angl. SPb.: BHV – Peterburg. 2021. 720 s.
9. YAponskij superkomp'yuter Fugaku uprochil svoe liderstvo v spiske TOP500. URL: https.//www.ixbt.com/.news/2020/ 11/18/japonskijsuperkompjuter-fugaku-uprochil-svoe-liderstvo-v-spiske-top500.html (data obrashcheniya: 25.03.2021).
10. Dlya sistemy SI predlozhili novye pristavki. URL: https://naukatv.ru/news/24915 (data obrashcheniya: 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. Mink H. Peranenty. Per. s angl. M.: Mir. 1982. 213 s.
13. Rybnikov K.A. Vvedenie v kombinatornyj analiz. M.: Izd-vo MGU. 1985. 312 s.
14. Sachkov V.N. Kombinatornye metody diskretnoj matematiki. M.: Nauka. 1977. 320 s.
15. Sachkov V.N. Vvedenie v kombinatornye metody diskretnoj matematiki. M.: Nauka. 1982. 384 s.
16. Sachkov V.N., Tarakanov V.E. Kombinatorika neotricatel'nyh matric. M.: TVP. 2000. 448 s.
17. Sachkov V.N. Kurs kombinatornogo analiza. M.–Izhevsk: NIC «Regulyarnaya i haoticheskaya dinamika». 2013. 336 s.
18. Evnin A.YU. Permanent matricy i ego vychislenie. Matematicheskoe obrazovanie. 2008. № 2(46). S. 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. R. 712–721.
20. Lankaster P. Teoriya matric. Per. s angl. M.: Nauka. 1982. 272 s.
21. Nil'sen M., CHang I. Kvantovye vychisleniya i kvantovaya informaciya. Per. s angl. M.: Mir. 2006. 824 s.
22. Savel'ev L.YA. Kombinatorika i veroyatnost'. M.: LENAND. 2021. 424 s.
23. Prosolov V.V. Zadachi i teoremy linejnoj algebry. M.: MCNMO. 2015. 576 s.