Quantum Data Fitting Algorithm for Non-sparse Matrices
This addresses a key issue in machine learning for quantum computing applications, though it is an incremental extension of prior sparse matrix methods.
The paper tackles the problem of over-fitting in quantum data fitting for non-sparse matrices by introducing a regularization term, achieving a runtime of O(κ²√N polylog(N)/(ε log κ)) with polynomial speedup on matrix dimension and sub-quadratic dependence on condition number.
We propose a quantum data fitting algorithm for non-sparse matrices, which is based on the Quantum Singular Value Estimation (QSVE) subroutine and a novel efficient method for recovering the signs of eigenvalues. Our algorithm generalizes the quantum data fitting algorithm of Wiebe, Braun, and Lloyd for sparse and well-conditioned matrices by adding a regularization term to avoid the over-fitting problem, which is a very important problem in machine learning. As a result, the algorithm achieves a sparsity-independent runtime of $O(κ^2\sqrt{N}\mathrm{polylog}(N)/(ε\logκ))$ for an $N\times N$ dimensional Hermitian matrix $\bm{F}$, where $κ$ denotes the condition number of $\bm{F}$ and $ε$ is the precision parameter. This amounts to a polynomial speedup on the dimension of matrices when compared with the classical data fitting algorithms, and a strictly less than quadratic dependence on $κ$.