Quantum Information & Computation
Volume 25, Issue 2
RESEARCH ARTICLE Open access

Quantum Algorithms for Calculating Determinant and Inverse of Matrix and Solving Linear Algebraic Systems

Alexander I. Zenchuk, Georgii A. Bochkin, Wentao Qi, Asutosh Kumar, Junde Wu

Author affiliations
  • Alexander I. Zenchuk1
  • Georgii A. Bochkin1
  • Wentao Qi2
  • Asutosh Kumar3
  • Junde Wu4
  1. Federal Research Center of Problems of Chemical Physics and Medicinal Chemistry RAS, Chernogolovka, Moscow, Russia
  2. Institute of Quantum Computing and Computer Theory, School of Computer Science and Engineering, Sun Yat-sen University, Guangzhou, China
  3. Department of Physics, KSS College, Lakhisarai, India; P.G. Department of Physics, Munger University, Munger, India
  4. School of Mathematical Sciences, Zhejiang University, Hangzhou, China

pp. 195-215 · 10.2478/qic-2025-0010

Read PDF View on Reference Global
On this page

Abstract

We propose quantum algorithms, purely quantum in nature, for calculating the determinant and inverse of an (N – 1) × (N – 1) matrix (depth is O(N2 log N)) which is a simple modification of the algorithm for calculating the determinant of an N × N matrix (depth is O(N log2 N)). The basic idea is to encode each row of the matrix into a pure state of some quantum system. In addition, we use the representation of the elements of the inverse matrix in terms of algebraic complements. This algorithm together with that for matrix multiplication proposed earlier yields the algorithm for solving systems of linear algebraic equations (depth is O(N log2 N)). Measurement of the ancilla state with output 1 (probability is 2− O(N log N)) removes the garbage acquired during calculation. Appropriate circuits for all three algorithms are presented and have the same estimation O(N log N) for the space (number of qubits in the circuit).
Open accessCC BY-NC-ND 4.0

Keywords

  • quantum algorithm
  • quantum circuit
  • determinant and inverse of matrix
  • linear algebraic systems
  • depth of algorithm
  • quantum measurement

Suggested citation

Alexander I. Zenchuk, Georgii A. Bochkin, Wentao Qi, Asutosh Kumar, Junde Wu (2025). Quantum Algorithms for Calculating Determinant and Inverse of Matrix and Solving Linear Algebraic Systems. Quantum Information & Computation, 25(2), 195-215. https://doi.org/10.2478/qic-2025-0010

Download BibTeX

References (48)

  1. P. W. Shor (1994). “Algorithms for quantum computation: discrete logarithms and factoring”, in Proceedings 35th Annual Symposium on Foundations of Computer Science, Santa Fe, NM, pp. 124–134DOI: 10.1109/SFCS.1994.365700Google Scholar
  2. P. W. Shor (1997). “Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer”. SIAM J. Comput. 26, 5.DOI: 10.1137/S0097539795293172Google Scholar
  3. D. Deutsch (1985). “Quantum theory, the Church-turing principle and the universal quantum computer”. Proc. R. Soc. Lond. A 400, 97.DOI: 10.1098/rspa.1985.0070Google Scholar
  4. L. Grover (1996). “A fast quantum mechanical algorithm for database search, STOC”, in 96: Proceedings 28th Annual ACM Symposium on the Theory of Computation. New York: ACM Press.DOI: 10.1145/237814.237866Google Scholar
  5. D. Coppersmith (2002). “An approximate Fourier transform useful in quantum factoring”. IBM Research Report, RC 19642.Google Scholar
  6. Y. S. Weinstein, M. A. Pravia, E. M. Fortunato, S. Lloyd, and D. G. Cory (2001). “Implementation of the quantum Fourier transform”. Phys. Rev. Lett. 86, 1889.DOI: 10.1103/PhysRevLett.86.1889Google Scholar
  7. M. A. Nielsen and I. L. Chuang (2000). Quantum Computation and Quantum Information. Cambridge: Cambridge University Press.Google Scholar
  8. H. Wang, L. Wu, Y. Liu, and F. Nori (2010). “Measurement-based quantum phase estimation algorithm for finding eigenvalues of non-unitary matrices”. Phys. Rev. A. 82, 062303.DOI: 10.1103/PhysRevA.82.062303Google Scholar
  9. A. W. Harrow, A. Hassidim, and S. Lloyd (2009). “Quantum algorithm for linear systems of equations”. Phys. Rev. Lett. 103, 150502DOI: 10.1103/PhysRevLett.103.150502Google Scholar
  10. B. D. Clader, B. C. Jacobs, and C. R. Sprouse (2013). “Preconditioned quantum linear system algorithm”. Phys. Rev. Lett. 110, 250504.DOI: 10.1103/PhysRevLett.110.250504Google Scholar
  11. J. Biamonte, P. Wittek, N. Pancotti, P. Rebentrost, N. Wiebe, and S. Lloyd (2017). “Quantum machine learning”. Nature 549, 195.DOI: 10.1038/nature23474Google Scholar
  12. L. Wossnig, Z. Zhao, and A. Prakash (2018). “Quantum linear system algorithm for dense matrices”. Phys. Rev. Lett. 120, 050502.DOI: 10.1103/PhysRevLett.120.050502Google Scholar
  13. X. D. Cai, C. Weedbrook, Z. E. Su, M. C. Chen, M. Gu, M. J. Zhu, L. Li, N. L. Liu, C. Y. Lu, and J. W. Pan (2013). “Experimental quantum computing to solve systems of linear equations”. Phys. Rev. Lett. 110, 230501.DOI: 10.1103/PhysRevLett.110.230501Google Scholar
  14. J. W. Pan, Y. Cao, X. Yao, Z. Li, C. Ju, H. Chen, X. Peng, S. Kais, and J. Du (2014). “Experimental realization of quantum algorithm for solving linear systems of equations”. Phys. Rev. A. 89, 022313.DOI: 10.1103/PhysRevA.89.022313Google Scholar
  15. S. Barz, I. Kassal, M. Ringbauer, Y. O. Lipp, B. Dakić, A. Aspuru-Guzik, and P. Walther (2014). “A two-qubit photonic quantum processor and its application to solving systems of linear equations”. Sci. Rep. 4, 6115.DOI: 10.1038/srep06115Google Scholar
  16. Y. Zheng, C. Song, M. C. Chen, B. Xia, W. Liu, Q. Guo, L. Zhang, D. Xu, H. Deng, K. Huang, Y. Wu, Z. Yan, D. Zheng, L. Lu, J. W. Pan, H. Wang, C. Y. Lu, and X. Zhu (2017). “Solving systems of linear equations with a superconducting quantum processor”. Phys. Rev. Lett. 118, 210504.DOI: 10.1103/PhysRevLett.118.210504Google Scholar
  17. A. T.-Shma (2013). “Inverting well conditioned matrices in quantum logspace”, in Proceedings of the Forty-fifth Annual ACM Symposium on Theory of Computing, STOC’13. New York, pp. 881–890.DOI: 10.1145/2488608.2488720Google Scholar
  18. D. Aharonov and A. T.-Shma (2007). “Adiabatic quantum state generation”. SIAM Journal on Computing 37(1), 47.DOI: 10.1137/060648829Google Scholar
  19. G. Brassard, P. Hoyer, M. Mosca, and A. Tapp (2002). “Quantum amplitude amplification and estimation”. Contemp. Math. 305, 53–74.DOI: 10.1090/conm/305/05215Google Scholar
  20. A. M. Childs, R. Kothari, and R. D. Somma (2017). “Quantum algorithm for systems of linear equations with exponentially improved dependence on precision”. SIAM J. Comput. 46, 1920–1950.DOI: 10.1137/16M1087072Google Scholar
  21. A. Gilyén, Y. Su, G. H. Low, and N. Wiebe (2019). “Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics”, in STOC 2019: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pp. 193–204.DOI: 10.1145/3313276.3316366Google Scholar
  22. G. H. Low and I. L. Chuang (2017). “Optimal Hamiltonian simulation by quantum signal processing”. Phys. Rev. Lett. 118, 010501.DOI: 10.1103/PhysRevLett.118.010501Google Scholar
  23. G. H. Low, T. J. Yoder, and I. L. Chuang (2016). “Methodology of resonant equiangular composite quantum gates”. Phys. Rev. X 6, 041067.DOI: 10.1103/PhysRevX.6.041067Google Scholar
  24. D. An and L. Lin (2022). “Quantum linear system solver based on time-optimal adiabatic quantum computing and quantum approximate optimization algorithm”. ACM Trans. Quantum Comput. 3(2), Article 5, 1–28.DOI: 10.1145/3498331Google Scholar
  25. S. Jansen, M.-B. Ruskai, and R. Seiler (2007). “Bounds for the adiabatic approximation with applications to quantum computation”. J. Math. Phys. 48(10), 102111.DOI: 10.1063/1.2798382Google Scholar
  26. Y. Subaşı, R. D. Somma, and D. Orsucci (2019). “Quantum algorithms for systems of linear equations inspired by adiabatic quantum computing”. Phys. Rev. Lett. 122, 060504.DOI: 10.1103/PhysRevLett.122.060504Google Scholar
  27. T. Albash and D. A. Lidar (2018). “Adiabatic quantum computation”. Rev. Mod. Phys. 90, 015002.DOI: 10.1103/RevModPhys.90.015002Google Scholar
  28. Y. Tong, D. An, N. Wiebe, and L. Lin (2021). “Fast inversion, preconditioned quantum linear system solvers, fast Green’s function computation, and fast evaluation of matrix functions”. Phys. Rev. A 104, 032422.DOI: 10.1103/PhysRevA.104.032422Google Scholar
  29. S. Aaronson (2015). “Read the fine print”. Nature Phys. 11, 291–293.DOI: 10.1038/nphys3272Google Scholar
  30. P. Rebentrost„ M. Mohseni, and S. Lloyd (2014). “Quantum support vector machine for big data classification”. Phys. Rev. Lett. 113, 130503.DOI: 10.1103/PhysRevLett.113.130503Google Scholar
  31. N. Wiebe, D. Braun, and S. Lloyd (2012). “Quantum algorithm for data fitting”. Phys. Rev. Lett. 109, 050505.DOI: 10.1103/PhysRevLett.109.050505Google Scholar
  32. M. Schuld, I. Sinayskiy, and F. Petruccione (2016). “Prediction by linear regression on a quantum computer”. Phys. Rev. A 94, 022342.DOI: 10.1103/PhysRevA.94.022342Google Scholar
  33. G. Wang (2017). “Quantum algorithm for linear regression”. Phys. Rev. A 96, 012335.DOI: 10.1103/PhysRevA.96.012335Google Scholar
  34. F. L. Gall, “Robust dequantization of the quantum singular value transformation and quantum machine learning algorithms,” arXiv:2304.04932 [quant-ph].Google Scholar
  35. D. W. Berry (2014). “High-order quantum algorithm for solving linear differential equations”. J. Phys. A: Math. Theor. 47(10) 105301.DOI: 10.1088/1751-8113/47/10/105301Google Scholar
  36. J.-P. Liu, H. Kolden, H. K. Krovi, N. F. Loureiro, K. Trivisa, and A. M. Childs (2021). “Efficient quantum algorithm for dissipative nonlinear differential equations”. PNAS 118(35), e2026805118.DOI: 10.1073/pnas.2026805118Google Scholar
  37. J. M. Martyn, Z. M. Rossi, A. K. Tan, I. L. Chuang (2021). “A grand unification of quantum algorithms”. PRX Quantum 2, 040203DOI: 10.1103/PRXQuantum.2.040203Google Scholar
  38. I. Novikau, I. Joseph (2024). “Estimating QSVT angles for matrix inversion with large condition numbers”. arXiv:2408.15453v2 [quant-ph]DOI: 10.2139/ssrn.4973413Google Scholar
  39. L. Zhao, Z. Zhao, P. Rebentrost, and J. Fitzsimons (2021). “Compiling basic linear algebra subroutines for quantum computers”. Quantum Mach. Intell. 3, 21.DOI: 10.1007/s42484-021-00048-8Google Scholar
  40. S. I. Doronin, E. B. Fel’dman, and A. I. Zenchuk (2020). “Solving systems of linear algebraic equations via unitary transformations on quantum processor of IBM quantum experience”. Quantum Inf. Process 19, 68.DOI: 10.1007/s11128-019-2570-5Google Scholar
  41. H. Li, N. Jiang, Z. Wang, J. Wang, and R. Zhou (2021). “Quantum matrix multiplier”. Int. J. Theor. Phys. 60, 2037–2048.DOI: 10.1007/s10773-021-04816-xGoogle Scholar
  42. R. Kothari and A. Nayak (2015). “Quantum algorithms for matrix multiplication and product verification”, in: M.-Y. Kao (eds), Encyclopedia of Algorithms, Berlin, Heidelberg: Springer.DOI: 10.1007/978-3-642-27848-8_303-2Google Scholar
  43. W. Qi, A. I. Zenchuk, A. Kumar, and J. Wu (2024). “Quantum algorithms for matrix operations and linear systems of equations”. Commun. Theor. Phys. 76, 035103.DOI: 10.1088/1572-9494/ad2366Google Scholar
  44. A. I. Zenchuk, W. Qi, A. Kumar, and J. Wu (2024). “Matrix manipulations via unitary transformations and ancilla-state measurements”. Quantum Inf. Comp. 24(13,14),1099–110.DOI: 10.26421/QIC24.13-14-2Google Scholar
  45. S. J. Berkowitz (1984). “On computing the determinant in small parallel time using a small number of processors”. Inf. Process. Lett. 18(3), 147–150.DOI: 10.1016/0020-0190(84)90018-8Google Scholar
  46. E. Boix-Adserá, L. Eldar, S. Mehraban, “Approximating the determinant of well-conditioned matrices by shallow circuits”. arXiv:1912.03824 [cs.DS].Google Scholar
  47. A. Yu. Kitaev, A. H. Shen, M. N. Vyalyi (2002). “Classical and quantum computation” in Graduate Studies in Mathematics, V.47, Providence, RI: American Mathematical Society.DOI: 10.1090/gsm/047Google Scholar
  48. E. B. Fel’dman, A. I. Zenchuk, W. Qi, and J. Wu, “Remarks on controlled measurement and quantum algorithm for calculating Hermitian conjugate”, arXiv:2501.16028v1.Google Scholar