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

On Quantum Solvers for Linear Algebraic Systems

Papagiannis Nikos, Vavalis Manolis

Author affiliations
  • Papagiannis Nikos1
  • Vavalis Manolis2
  1. Computer Science Department, Purdue University, West Lafayette, USA
  2. Department of Electrical and Computing Engineering, University of Thessaly, Pedion Areos, Volos, Greece

pp. 640-667 · 10.2478/qic-2025-0035

Read PDF View on Reference Global
On this page

Abstract

Solving large-scale linear systems is an integral part of many scientific disciplines. Classical linear solvers have a polynomial time complexity and it seems impossible to further improve their performance. This fact has directed scientific research to the study of corresponding quantum algorithms, which promise even exponential acceleration compared to existing methods. In this paper, we present and analyze some of the most important related results. In particular, we present the HHL and WZP algorithms based on the eigen-decomposition of a matrix, the row and column iteration methods, as well as two hybrid algorithms that require the cooperation of a classical and a quantum computer, namely an algorithm that uses random walks and the VQLS algorithm. The latter is also examined from an experimental standpoint using the Qiskit open-source framework and a suitable quantum circuit is proposed which can enhance its performance.
Open accessCC BY-NC-ND 4.0

Keywords

  • quantum computing
  • linear systems
  • HHL
  • WZP
  • row and column iteration methods
  • random walks
  • VQLS
  • Qiskit

Suggested citation

Papagiannis Nikos, Vavalis Manolis (2025). On Quantum Solvers for Linear Algebraic Systems. Quantum Information & Computation, 25(6), 640-667. https://doi.org/10.2478/qic-2025-0035

Download BibTeX

References (52)

  1. Ray LaPierre (2021). Shor algorithm. Introduction to Quantum Computing, pages 177–192.DOI: 10.1007/978-3-030-69318-3_13Google Scholar
  2. McKinsey & Company. Quantum technology monitor. Technical report, April 2023.Google Scholar
  3. John von Neumann and H. H. Goldstine (1947). Numerical inverting of matrices of high order. Bulletin of the American Mathematical Society, 53(11):1021–1099.DOI: 10.1090/S0002-9904-1947-08909-6Google Scholar
  4. Alan Turing (1948). Rounding-off erros in matrix processes. The Quarterly Journal of Mechanics and Applied Mathematics, 1(1):287–308.DOI: 10.1093/qjmam/1.1.287Google Scholar
  5. G. A. Hedayat (1993). Numerical linear algebra and computer architecture: An evolving interaction. Technical Report UMCS-93-1-5, University of Manchester.Google Scholar
  6. Jack Dongarra (2002). Performance of various computers using standard linear equations software. Computer Architecture News, 20, 11.DOI: 10.1145/141868.141871Google Scholar
  7. Jessie Henderson, John Kath, John Golden, Allon Percus and Daniel O’Malley (2024). Addressing quantum’s “fine print” with efficient state preparation and information extraction for quantum algorithms and geologic fracture networks. Scientific Reports, 14, 02.DOI: 10.1038/s41598-024-52759-0Google Scholar
  8. John Golden, Daniel O’Malley and H. Viswanathan (2022). Quantum computing and preconditioners for hydrological linear systems. Scientific Reports, 12, 12.DOI: 10.1038/s41598-022-25727-9Google Scholar
  9. Mauro E. S. Morales, Lirandё Pira, Philipp Schleich, Kelvin Koor, Pedro C. S. Costa, Dong An, Alán Aspuru-Guzik et al. (2025). Quantum linear system solvers: A survey of algorithms and applications.DOI: 10.1103/x6gh-d8ghGoogle Scholar
  10. Eleanor Rieffel and Wolfgang Polak (2000). An introduction to quantum computing for non-physicists. ACM Computing Surveys (CSUR), 32(3):300–335.DOI: 10.1145/367701.367709Google Scholar
  11. Michael A. Nielsen and Isaac L. Chuang (2010). Quantum Computation and Quantum Information: 10th Anniversary Edition. Cambridge University Press.Google Scholar
  12. Richard Cleve, Artur Ekert, Chiara Macchiavello and Michele Mosca (1998). Quantum algorithms revisited. Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences, 454(1969):339–354.DOI: 10.1098/rspa.1998.0164Google Scholar
  13. Aram W. Harrow, Avinatan Hassidim and Seth Lloyd (2009). Quantum algorithm for solving linear systems of equations. Phys. Rev. Lett., 15(103).DOI: 10.1103/PhysRevLett.103.150502Google Scholar
  14. Lov Grover and Terry Rudolph (2002). Creating superpositions that correspond to efficiently integrable probability distributions. arXivpreprint quant-ph/0208112.Google Scholar
  15. Gerhard Hegerfeldt and Dirk Sondermann (1996). Conditional hamiltonian and reset operator in the quantum jump approach. Quantum and Semiclassical Optics: Journal of the European Optical Society Part B, 8(1):121.DOI: 10.1088/1355-5111/8/1/010Google Scholar
  16. X-D Cai, Christian Weedbrook, Z-E Su, M-C Chen, Mile Gu, M-J Zhu, Li Li, Nai-Le Liu, Chao-Yang Lu and Jian-Wei Pan (2013). Experimental quantum computing to solve systems of linear equations. Physical review letters, 110(23):230501.DOI: 10.1103/PhysRevLett.110.230501Google Scholar
  17. Leonard Wossnig, Zhikuan Zhao and Anupam Prakash (2018). Quantum linear system algorithm for dense matrices. Physical review letters, 120(5):050502.DOI: 10.1103/PhysRevLett.120.050502Google Scholar
  18. Iordanis Kerenidis and Anupam Prakash (2016). Quantum recommendation systems. arXiv preprint arXiv:1603.08675.Google Scholar
  19. Mario Szegedy (2004). Quantum speed-up of markov chain based algorithms. In 45th Annual IEEE symposium on foundations of computer science, pages 32–41. IEEE, 2004.DOI: 10.1109/FOCS.2004.53Google Scholar
  20. Changpeng Shao and Hua Xiang (2020). Row and column iteration methods to solve linear systems on a quantum computer. Physical Review A, 101(2):022322.DOI: 10.1103/PhysRevA.101.022322Google Scholar
  21. Yoshiyuki Saito, Xinwei Lee, Dongsheng Cai and Nobuyoshi Asai (2021). An iterative improvement method for hhl algorithm for solving linear system of equations. arXiv preprint arXiv:2108.07744.Google Scholar
  22. Debasish Roy and Sambo Raj Chandra (2024). Quantum iterative algorithm for linear systems of equation. In Science and Information Conference, pages 560–575. Springer, 2024.DOI: 10.1007/978-3-031-62281-6_38Google Scholar
  23. Vittorio Giovannetti, Seth Lloyd and Lorenzo Maccone (2008). Quantum random access memory. Physical review letters, 100(16):160501.DOI: 10.1103/PhysRevLett.100.160501Google Scholar
  24. Carlos Bravo-Prieto, Ryan LaRose, M. Cerezo, Yigit Subasi, Lukasz Cincio and Patrick J. Coles (2023). Variational Quantum Linear Solver. Quantum, 7:1188.DOI: 10.22331/q-2023-11-22-1188Google Scholar
  25. George Forsythe and Richard Leibler (1950). Matrix inversion by a monte carlo method. Mathematics of Computation, 4(31):127–129.DOI: 10.1090/S0025-5718-1950-0038138-XGoogle Scholar
  26. IT Dimov, TT Dimov and TV Gurov (1998). A new iterative monte carlo approach for inverse matrix problem. Journal of Computational and Applied Mathematics, 92(1):15–35.DOI: 10.1016/S0377-0427(98)00043-0Google Scholar
  27. Chih-Chieh Chen, Shiue-Yuan Shiau, Ming-Feng Wu and Yuh-Renn Wu (2019). Hybrid classical-quantum linear solver using noisy intermediate-scale quantum machines. Scientific reports, 9(1):16251.DOI: 10.1038/s41598-019-52275-6Google Scholar
  28. Richard Hamming (1950). Error detecting and error correcting codes. The Bell system technical journal, 29(2):147–160.DOI: 10.1002/j.1538-7305.1950.tb00463.xGoogle Scholar
  29. The variational quantum linear solver. https://learn.qiskit.org/course/ch-applications/the-variational-quantumlinear-solver. Accessed: 2023-06-14.Google Scholar
  30. Pauli Virtanen, Ralf Gommers, Travis E Oliphant, Matt Haberland, Tyler Reddy, David Cournapeau et al. (2020). Scipy 1.0: fundamental algorithms for scientific computing in python. Nature methods, 17(3):261–272.DOI: 10.1038/s41592-020-0772-5Google Scholar
  31. Per-Gunnar Martinsson and Joel Tropp (2020). Randomized numerical linear algebra: Foundations and algorithms. Acta Numerica, 29:403–572.DOI: 10.1017/S0962492920000021Google Scholar
  32. Do Diep, Do Giang and Phan Phu (2018). Application of Quantum Gauss-Jordan Elimination Code to Quantum Secret Sharing Code. International Journal of Theoretical Physics, 57.DOI: 10.1007/s10773-017-3617-yGoogle Scholar
  33. Koji Nagata, Tadao Nakamura, Han Geurdes, J Batle, Ahmed Farouk, Do Diep and Santanu Patro (2018). Efficient Quantum Algorithms of Finding the Roots of a Polynomial Function. International Journal of Theoretical Physics, 57.DOI: 10.1007/s10773-018-3776-5Google Scholar
  34. Stefan Heinrich (2003). From Monte Carlo to quantum computation. Math. Comput. Simul., 62:219–230.DOI: 10.1016/S0378-4754(02)00239-2Google Scholar
  35. Thomas Wong (2022). Introduction to Classical and Quantum Computing. Rooted Grove, Omaha, Nebraska.Google Scholar
  36. Mihir Bhaskar, Stuart Hadfield, Anargyros Papageorgiou and lasonas Petras (2016). Quantum algorithms and circuits for scientific computing. Quantum Information and Computation, 16(3&4):197–236.DOI: 10.26421/QIC16.3-4-2Google Scholar
  37. Stefan Heinrich (2006). Numerical Analysis on a Quantum Computer. In Ivan Lirkov, Svetozar Margenov, and Jerzy Waśniewski, editors, Large-Scale Scientific Computing, pages 28–39, Berlin, Heidelberg, Springer Berlin Heidelberg.DOI: 10.1007/11666806_3Google Scholar
  38. Chi Zhang (2011). Quantum Algorithms and Complexity for Numerical Problems. PhD thesis, Columbia University.Google Scholar
  39. Ngoc Do, Do Diep, Do Giang and Nguyen Minh (2017). Quantum Gauss-Jordan Elimination and Simulation of Accounting Principles on Quantum Computers. ViAsM16.01, 56.DOI: 10.1007/s10773-017-3340-8Google Scholar
  40. Hefeng Wang and Hua Xiang (2019). A quantum eigensolver for symmetric tridiagonal matrices. Quantum Information Processing, 18(3).DOI: 10.1007/s11128-019-2211-zGoogle Scholar
  41. Giacomo Nannicini (2020). An introduction to quantum computing, without the physics. SIAM Review, 62(4).DOI: 10.1137/18M1170650Google Scholar
  42. Siddhartha Srivastava and Veera Sundararaghavan (2019). Box algorithm for the solution of differential equations on a quantum annealer. Physical Review A, 99(5):52355.DOI: 10.1103/PhysRevA.99.052355Google Scholar
  43. Lin Lin (2022). Lecture Notes on Quantum Algorithms for Scientific Computation. arXiv preprint arXiv:1909.05820, 1.Google Scholar
  44. Matthias Möller and Cornelis Vuik (2017). On the Impact of Quantum Computing Technology on Future Developments in High-Performance Scientific Computing. Ethics and Inf. Technol., 19(4):253–269, 12.DOI: 10.1007/s10676-017-9438-0Google Scholar
  45. Guillermo González, Rahul Trivedi and J. Ignacio Cirac (2021). Quantum algorithms for powering stable Hermitian matrices. Physical Review A, 103(6).DOI: 10.1103/PhysRevA.103.062420Google Scholar
  46. Stuart Hadfield (2018). Quantum Algorithms for Scientific Computing and Approximate Optimization. arxiv.org, 5.Google Scholar
  47. Jacob Biamonte, Peter Wittek, Nicola Pancotti, Patrick Rebentrost, Nathan Wiebe and Seth Lloyd (2017). Quantum machine learning, 9.DOI: 10.1038/nature23474Google Scholar
  48. Juan José García Ripoll (2021). Quantum-inspired algorithms for multivariate analysis: From interpolation to partial differential equations. Quantum, 5.DOI: 10.22331/q-2021-04-15-431Google Scholar
  49. Piotr Gawron, Dariusz Kurzyk and Łukasz Pawela (2018). QuantumInformation.jl—A Julia package for numerical computation in quantum information theory. PLoS ONE, 13(12).DOI: 10.1371/journal.pone.0209358Google Scholar
  50. Jules Tilly, Hongxiang Chen, Shuxiang Cao, Dario Picozzi, Kanav Setia, Ying Li, Edward et al. (2022) The variational quantum eigensolver: a review of methods and best practices. Physics Reports, 986:1–128.DOI: 10.1016/j.physrep.2022.08.003Google Scholar
  51. Lin Lin and Yu Tong (2020). Optimal polynomial based quantum eigenstate filtering with application to solving quantum linear systems. Quantum, 4:361.DOI: 10.22331/q-2020-11-11-361Google Scholar
  52. Andrew Childs, Robin Kothari and Rolando Somma (2017). Quantum algorithm for systems of linear equations with exponentially improved dependence on precision. SIAM Journal on Computing, 46(6):1920–1950.DOI: 10.1137/16M1087072Google Scholar