Open AccessQuantum Algorithms for Solving Linear Regression Equation
Author(s) -
Kai Li,
Dai Hirata,
Jing Feng,
Mingxin Gao,
Binghan Xue,
Pu Wang,
Ming Zhang
Publication year - 2021
Publication title -
journal of physics. conference series
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.21
H-Index - 85
eISSN - 1742-6596
pISSN - 1742-6588
DOI - 10.1088/1742-6596/1738/1/012063
Subject(s) - linear regression , algorithm , dimension (graph theory) , mathematics , regression analysis , statistics , computer science , combinatorics
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 log N ), where m is the dimension of the input u and N is the number of samples.