Article
Full entry | Fulltext not available
(moving wall
24 months)
Feedback
Keywords:
quantum algorithm; regularization method; Levenberg-Marquardt method; ill-posed problem; HHL quantum algorithm
quantum algorithm; regularization method; Levenberg-Marquardt method; ill-posed problem; HHL quantum algorithm
Summary:
To achieve exponential speed-up with the Harrow-Hassidim-Lloyd (HHL) quantum algorithm, the condition number of the matrix can scale at most poly-logarithmically with its size. This quantum algorithm significantly outperforms the best classical methods for solving well-conditioned linear systems of equations. However, well-conditioning is a stringent requirement that severely limits the range of problems benefiting from exponential speed-up. In this paper, we introduce a regularization method that combines the HHL quantum algorithm with the Levenberg-Marquardt method to mitigate ill-conditioning and enable exponential speed-up. Specifically, the Levenberg-Marquardt method acts as a regularization method, transforming an ill-conditioned linear system of equations into a sequence of well-conditioned linear systems of equations. The HHL quantum algorithm is then applied to solve these systems efficiently. This approach effectively addresses the ill-conditioning issue while preserving the exponential speed-up advantage.
References:
[1] Cao, Y., Daskin, A., Frankel, S., Kais, S.: Quantum circuit design for solving linear systems of equations. Molecular Phys. 110 (2012), 1675-1680. DOI 10.1080/00268976.2012.668289
[2] Cao, Y., Papageorgiou, A., Petras, I., Traub, J., Kais, S.: Quantum algorithm and circuit design solving the Poisson equation. New J. Phys. 15 (2013), Article ID 013021, 29 pages. DOI 10.1088/1367-2630/15/1/013021 | MR 3045573 | Zbl 1451.81163
[3] Clader, B. D., Jacobs, B. C., Sprouse, C. R.: Preconditioned quantum linear system algorithm. Phys. Rev. Lett. 110 (2013), Article ID 250504. DOI 10.1103/PhysRevLett.110.250504
[4] Demmel, J. W.: Applied Numerical Linear Algebra. SIAM, Philadelphia (1997). DOI 10.1137/1.9781611971446 | MR 1463942 | Zbl 0879.65017
[5] Duan, B., Yuan, J., Yu, C.-H., Huang, J., Hsieh, C.-Y.: A survey on HHL algorithm: From theory to application in quantum machine learning. Phys. Lett., A 384 (2020), Article ID 126595, 13 pages. DOI 10.1016/j.physleta.2020.126595 | MR 4105727 | Zbl 1448.81232
[6] Hanke, M.: The regularizing Levenberg-Marquardt scheme is of optimal order. J. Integral Equations Appl. 22 (2010), 259-283. DOI 10.1216/JIE-2010-22-2-259 | MR 2661721 | Zbl 1204.65059
[7] Hansen, P. C.: Rank-Deficient and Discrete Ill-Posed Problems: Numerical Aspects of Linear Inversion. SIAM Monographs on Mathematical Modeling and Computation 4. SIAM, Philadelphia (1998). DOI 10.1137/1.9780898719697 | MR 1486577 | Zbl 0890.65037
[8] Hansen, P. C.: Regularization tools version 4.0 for Matlab 7.3. Numer. Algorithms 46 (2007), 189-194. DOI 10.1007/s11075-007-9136-9 | MR 2358249 | Zbl 1128.65029
[9] Harkins, F., (Ed.): Qiskit textbook: IBM Q HHL code. Available at https://qiskit.org/textbook/ch-applications/hhl_tutorial.html (2023).
[10] Harrow, A. W., Hassidim, A., Lloyd, S.: Quantum algorithm for linear systems of equations. Phys. Rev. Lett. 103 (2009), Article ID 150502, 4 pages. DOI 10.1103/PhysRevLett.103.150502 | MR 2551688
[11] Kelley, C. T.: Iterative Methods for Optimization. Frontiers in Applied Mathematics 18. SIAM, Philadelphia (1999). DOI 10.1137/1.9781611970920 | MR 1678201 | Zbl 0934.90082
[12] Nielsen, M. A., Chuang, I. L.: Quantum Computation and Quantum Information. Cambridge University Press, Cambridge (2000). DOI 10.1017/CBO9780511976667 | MR 1796805 | Zbl 1049.81015
Search
Partner of
