Quantum Regularized Least Squares Solver with Parameter Estimate
Provides a quantum solution for regularized least squares problems, benefiting inverse problem solvers in scientific computing.
Proposed a quantum algorithm for Tikhonov regularization parameter selection and solving ill-conditioned linear equations, achieving quadratic speedup in parameter count and exponential speedup in problem dimension.
In this paper we propose a quantum algorithm to determine the Tikhonov regularization parameter and solve the ill-conditioned linear equations, for example, arising from the finite element discretization of linear or nonlinear inverse problems. For regularized least squares problem with a fixed regularization parameter, we use the HHL algorithm and work on an extended matrix with smaller condition number. For the determination of the regularization parameter, we combine the classical L-curve and GCV function, and design quantum algorithms to compute the norms of regularized solution and the corresponding residual in parallel and locate the best regularization parameter by Grover's search. The quantum algorithm can achieve a quadratic speedup in the number of regularization parameters and an exponential speedup in the dimension of problem size.