arXiv:1812.09934

Quantum Regularized Least Squares Solver with Parameter Estimate

Changpeng Shao, Hua Xiang

Published Dec 24, 2018• 1 citation

Abstract

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.

DOI: 10.48550/arxiv.1812.09934

Related papers

QVaR: a Quantum Variational Regularization method for Linear Inverse Problems

Siiri Rautio, Hjørdis Schlüter, Andreas Hauptmann +1 more

We present a tailored framework for solving regularized linear inverse problems using quantum optimization methods. By discretizing the solution space and encoding data fidelity and regularization terms into quadratic unconstrained binary optimization (QUBO) models, we formulate both Tikhonov- and sparsity-promoting regularized inverse problems within a unified quantum optimization framework. We further introduce a notion of quantum sensitivity that characterizes the effect of perturbations arising from approximate quantum evolution and discretization. We derive bounds relating these perturbations to stability properties of the underlying inverse problem, thereby establishing a theoretical connection between quantum solution variability and classical notions of ill-posedness. The framework is extended to variational inverse problems through wavelet-based representations and complemented by reduced-order modeling strategies in both parameter and Hamiltonian spaces to mitigate current hardware limitations. Numerical experiments on simulated and physical quantum hardware indicate that the resulting low-energy solution distributions retain information about the underlying inverse problem, while also revealing the limitations imposed by finite-time evolution, discretization, and hardware noise.

arXiv:2606.21392Jun 19, 20260 citations

Quantum Regularized Least Squares

Shantanav Chakraborty, Aditya Morolia, Anurudh Peduri

Linear regression is a widely used technique to fit linear models and finds widespread applications across different areas such as machine learning and statistics. In most real-world scenarios, however, linear regression problems are often ill-posed or the underlying model suffers from o v e r f i t t i n g , leading to erroneous or trivial solutions. This is often dealt with by adding extra constraints, known as regularization. In this paper, we use the frameworks of block-encoding and quantum singular value transformation (QSVT) to design the first quantum algorithms for quantum least squares with general ℓ 2 -regularization. These include regularized versions of quantum ordinary least squares, quantum weighted least squares, and quantum generalized least squares. Our quantum algorithms substantially improve upon prior results on quantum ridge regression (polynomial improvement in the condition number and an exponential improvement in accuracy), which is a particular case of our result.To this end, we assume approximate block-encodings of the underlying matrices as input and use robust QSVT algorithms for various linear algebra operations. In particular, we develop a variable-time quantum algorithm for matrix inversion using QSVT, where we use quantum eigenvalue discrimination as a subroutine instead of gapped phase estimation. This ensures that substantially fewer ancilla qubits are required for this procedure than prior results. Owing to the generality of the block-encoding framework, our algorithms are applicable to a variety of input models and can also be seen as improved and generalized versions of prior results on standard (non-regularized) quantum least squares algorithms.

arXiv:2206.13143QuantumApr 27, 202322 citations

Quantum algorithms and the finite element method

Ashley Montanaro, Sam Pallister

The finite element method is used to approximately solve boundary value problems for differential equations. The method discretizes the parameter space and finds an approximate solution by solving a large system of linear equations. Here we investigate the extent to which the finite element method can be accelerated using an efficient quantum algorithm for solving linear equations. We consider the representative general question of approximately computing a linear functional of the solution to a boundary value problem and compare the quantum algorithm's theoretical performance with that of a standard classical algorithm---the conjugate gradient method. Prior work claimed that the quantum algorithm could be exponentially faster but did not determine the overall classical and quantum run times required to achieve a predetermined solution accuracy. Taking this into account, we find that the quantum algorithm can achieve a polynomial speedup, the extent of which grows with the dimension of the partial differential equation. In addition, we give evidence that no improvement of the quantum algorithm can lead to a superpolynomial speedup when the dimension is fixed and the solution satisfies certain smoothness properties.

arXiv:1512.05903Physical Review AMar 17, 2016192 citations

Quantum-enhanced Regression Analysis Using State-of-the-art QLSAs and QIPMs

Mohammadhossein Mohammadisiahroudi, Zeguan Wu, Brandon Augustino +2 more

Quantum computing has the potential to speed up machine learning methods. One major direction is using quantum linear algebra to solve linear system problems or optimization problems in the machine learning area. Quantum approaches in the literature for different types of least squares problems demonstrate speedups w.r.t. dimension but have disadvantages w.r.t. precision and condition number. In this paper, we discuss how an iterative refinement scheme can deliver an accurate solution without the excessive cost of Quantum Linear System Algorithms (QLSAs). In addition, we propose an adaptive regularization approach that can mitigate the effect of condition number on solution time. In the second part of this paper, we investigate how state-of-the-art Quantum Interior Point Methods (QIPMs) can solve more sophisticated regression problems such as Lasso regression and support vector machine problems, which can be reformulated as quadratic optimization problems.

IEEE/ACM Symposium on Edge Computing (SEC)Dec 1, 20225 citations

Quantum Linear System Algorithm for General Matrices in System Identification

Kai Li, Ming Zhang, Xiaowen Liu +4 more

Solving linear systems of equations is one of the most common and basic problems in classical identification systems. Given a coefficient matrix A and a vector b, the ultimate task is to find the solution x such that Ax=b. Based on the technique of the singular value estimation, the paper proposes a modified quantum scheme to obtain the quantum state |x⟩ corresponding to the solution of the linear system of equations in O(κ2rpolylog(mn)/ϵ) time for a general m×n dimensional A, which is superior to existing quantum algorithms, where κ is the condition number, r is the rank of matrix A and ϵ is the precision parameter. Meanwhile, we also design a quantum circuit for the homogeneous linear equations and achieve an exponential improvement. The coefficient matrix A in our scheme is a sparsity-independent and non-square matrix, which can be applied in more general situations. Our research provides a universal quantum linear system solver and can enrich the research scope of quantum computation.

EntropyJun 28, 20223 citations

Quantum Algorithms for Matrix Problems and Machine Learning

Sathyawageeswar Subramanian

This dissertation presents a study of quantum algorithms for problems that can be posed as matrix function tasks. In Chapter 1 we demonstrate a simple unifying framework for implementing of smooth functions of matrices on a quantum computer. This framework captures a variety of problems that can be solved by evaluating properties of some function of a matrix, and we identify speedups over classical algorithms for some problem classes. The analysis combines ideas from the classical theory of function approximation with the quantum algorithmic primitive of implementing linear combinations of unitary operators. In Chapter 2 we continue this study by looking at the role of sparsity of input matrices in constructing efficient quantum algorithms. We show that classically pre-processing an input matrix by spectral sparsification can be profitable for quantum Hamiltonian simulation algorithms, without compromising the simulation error or complexity. Such preprocessing incurs a one time cost linear in the size of the matrix, but can be exploited to exponentially speed up subsequent subroutines such as inversion. In Chapter 3, we give an application of this theory of matrix functions to the problem of estimating the Renyi entropy of an unknown quantum state. We combine matrix function techniques with mixed state quantum computation in the one-clean qubit model, and are able to bound of the expected runtime of our algorithm in terms of the unknown target quantity. In addition to the theme of analysing the complexity of our algorithms, we also identify instances that are of practical relevance, leading us to some problems of machine learning. In Chapter 4 we investigate kernel based learning methods using random features. We work with the QRAM input model suitable for big data, and show how matrix functions and the quantum Fourier transform can be used to devise a quantum algorithm for sampling random features that are optimised for given input data and choice of kernel. We obtain a potential exponential speedup over the best known classical algorithm even without explicit assumptions of sparsity or low rank. Finally in Chapter 5 we consider the technique of beamsearch decoding used in natural language processing. We work in the query model, and show how quantum search with advice can be used to construct a quantum search decoder that can find the optimal parse (which may for instance be a best translation, or text-to-speech transcript) at least quadratically faster than the best known classical algorithms, and obtain super-quadratic speedups in the expected runtime.

Jul 24, 20200 citations