01107nas a2200109 4500008004100000245004100041210004100082260001500123520080600138100001800944856003500962 2014 eng d00aQuantum Algorithms for Curve Fitting0 aQuantum Algorithms for Curve Fitting c2014/04/023 aWe present quantum algorithms for estimating the best-fit parameters and the quality of least-square curve fitting. The running times of these algorithms are polynomial in logn, d, κ, ν, χ, 1/Φ and 1/ϵ, where n is the number of data points to be fitted, d is the dimension of feature vectors, κ is the condition number of the design matrix, ν and χ are some parameters reflecting the variances of the design matrix and response vector, Φ is the fit quality, and ϵ is the tolerable error. Different from previous quantum algorithms for these tasks, our algorithms do not require the design matrix to be sparse, and they do completely determine the fitted curve. They are developed by combining phase estimation and the density matrix exponentiation technique for dense Hamiltonian simulation.1 aWang, Guoming uhttp://arxiv.org/abs/1402.0660