Linear Regression is a widely used optimization problem with many practical applications. Adiabatic Quantum Computers are excellent at solving such optimization problems. Current quantum-based solutions allow for datasets having only a small number of features (maximum 32). We have come up with a novel approach that allows for a greater number of features for Linear Regression. We have found that our approach works for a large number of features, ranging from 64 to 128. We obtained a reasonably similar MSE (Mean Squared Error) to that of sklearn’s standard Linear Regression class, with a difference that lies between 0.01 and 0.03.
Linear Regression is a widely used optimization problem with many practical applications. Adiabatic Quantum Computers are excellent at solving such optimization problems. Current quantum-based solutions allow for datasets having only a small number of features (maximum 32). We have come up with a novel approach that allows for a greater number of features for Linear Regression. We have found that our approach works for a large number of features, ranging from 64 to 128. We obtained a reasonably similar MSE (Mean Squared Error) to that of sklearn’s standard Linear Regression class, with a difference that lies between 0.01 and 0.03.
The recent availability of quantum annealers as cloud-based services has enabled new ways to handle machine learning problems, and several relevant algorithms have been adapted to run on these devices. In a recent work, linear regression was formulated as a quadratic binary optimization problem that can be solved via quantum annealing. Although this approach promises a computational time advantage for large datasets, the quality of the solution is limited by the necessary use of a precision vector, used to approximate the real-numbered regression coefficients in the quantum formulation. In this work, we focus on the practical challenge of improving the precision vector encoding: instead of setting an array of generic values equal for all coefficients, we allow each one to be expressed by its specific precision, which is tuned with a simple adaptive algorithm. This approach is evaluated on synthetic datasets of increasing size, and linear regression is solved using the D-Wave Advantage quantum annealer, as well as classical solvers. To the best of our knowledge, this is the largest dataset ever evaluated for linear regression on a quantum annealer. The results show that our formulation is able to deliver improved solution quality in all instances, and could better exploit the potential of current quantum devices.
A major challenge in machine learning is the computational expense of training these models. Model training can be viewed as a form of optimization used to fit a machine learning model to a set of data, which can take up significant amount of time on classical computers. Adiabatic quantum computers have been shown to excel at solving optimization problems, and therefore, we believe, present a promising alternative to improve machine learning training times. In this paper, we present an adiabatic quantum computing approach for training a linear regression model. In order to do this, we formulate the regression problem as a quadratic unconstrained binary optimization (QUBO) problem. We analyze our quantum approach theoretically, test it on the D-Wave adiabatic quantum computer and compare its performance to a classical approach that uses the Scikit-learn library in Python. Our analysis shows that the quantum approach attains up to [Formula: see text] speedup over the classical approach on larger datasets, and performs at par with the classical approach on the regression error metric. The quantum approach used the D-Wave 2000Q adiabatic quantum computer, whereas the classical approach used a desktop workstation with an 8-core Intel i9 processor. As such, the results obtained in this work must be interpreted within the context of the specific hardware and software implementations of these machines.
Linear regression is a basic and widely used methodology in data analysis. It is known that some quantum algorithms efficiently perform least-squares linear regression of an exponentially large dataset. However, if we obtain values of the regression coefficients as classical data, the complexity of the existing quantum algorithms can be larger than the classical method. This is because it depends strongly on the tolerance error $\ensuremath{\epsilon}$: the best one among the existing proposals is $O({\ensuremath{\epsilon}}^{\ensuremath{-}2})$. In this paper, we propose a quantum algorithm for linear regression, which has a complexity of $O({\ensuremath{\epsilon}}^{\ensuremath{-}1})$ and keeps a logarithmic dependence on the number of data points ND. In this method, we overcome bottleneck parts in the calculation, which take the form of the sum over data points and therefore have a complexity proportional to ND, using quantum amplitude estimation, and other parts classically. Additionally, we generalize our method to some class of convex optimization problems.
Machine learning model training, which ultimately optimizes a model’s cost function is usually a time- consuming and computationally intensive process on classical computers. This has been more intense due to the in- creased demand for large-scale data analysis, requiring unconventional computing paradigms like quantum computing to enhance training efficiency. Adiabatic quantum computers have excelled at solving optimization problems, which require the quadratic unconstrained binary optimization (QUBO) format of the problem of interest. In this study, the squared error minimization in the multiple linear regression model is reformulated as a QUBO problem enabling it to be solved using D-wave adiabatic quantum computers. Same formulation was used to obtain a solution using gate-based algorithms such as quantum approximate optimization algorithm (QAOA) and sampling variational quantum eigensolver (VQE) im- plemented via IBM Qiskit. The results obtained through these approaches in the context of runtime and mean squared error(MSE) were analyzed and compared to the classical approaches. Our experimental results indicate a runtime ad- vantage in the D-wave annealing approach over the classical Scikit learn regression approach. The time advantage can be observed when N>524288 compared to Sklearn Linear Regression and when N>65536 compared to Sklearn SGDRegressor. Support vector machine induced neural networks, where the margin-based entropy loss is converted into a QUBO with Lagrangian approach is also focused in this study concerning the applicability for nonlinear models.
We present a quantum algorithm for fitting a linear regression model to a given data set using the least-squares approach. Differently from previous algorithms which yield a quantum state encoding the optimal parameters, our algorithm outputs these numbers in the classical form. So by running it once, one completely determines the fitted model and then can use it to make predictions on new data at little cost. Moreover, our algorithm works in the standard oracle model, and can handle data sets with nonsparse design matrices. It runs in time $\text{poly}({log}_{2}(N),d,\ensuremath{\kappa},1/\ensuremath{\epsilon})$, where N is the size of the data set, d is the number of adjustable parameters, $\ensuremath{\kappa}$ is the condition number of the design matrix, and $\ensuremath{\epsilon}$ is the desired precision in the output. We also show that the polynomial dependence on d and $\ensuremath{\kappa}$ is necessary. Thus, our algorithm cannot be significantly improved. Furthermore, we also give a quantum algorithm that estimates the quality of the least-squares fit (without computing its parameters explicitly). This algorithm runs faster than the one for finding this fit, and can be used to check whether the given data set qualifies for linear regression in the first place.
Abstract Linear regression is one of the most important and common analytical methods in mathematical statistics. The letter studies a general model of linear regression problem based on least squares method, and investigates the impact of quantum algorithms on the time complexity of solving linear regression problem when quantum algorithms can be implemented on quantum computers. With the help of the general model of linear regression problem in terms of least squares method, we propose a novel simplified quantum scheme for solving linear regression equation based on the sparsity-independent quantum singular value estimation algorithm. For a linear regression equation with dimension n, our scheme can reduce the time complexity from O(Nn 2) to O ( N log N ) when both the condition number κ of related matrices and the reciprocal of precision ∈ are small in size O(play logN), where m is the dimension of the input u and N is the number of samples.