Quantum regularized least squares solver with parameter estimate

Abstract

For ill-conditioned least squares problems, regularization techniques such as Tikhonov regularization are the key ingredients to obtain meaningful solutions, and the determination of the proper regularization parameter is the most difficult step. This paper focuses on the choice of regularization parameter on a quantum computer. We combine the classical L-curve or Hanke–Raus rule with the HHL algorithm and quantum amplitude estimation that compute the regularized solution and the corresponding residual and their norms. When a series of regularization parameters are tested, we then apply Grover’s search algorithm to find the best one that gives the meaningful solution. This yields a quadratic speedup in the number of regularization parameters.