Quantum Data Fitting Algorithm for Non-sparse Matrices

Guangxi Li, Youle Wang, Yu Luo, Yuan Feng

Abstract

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(\kappa^2\sqrt{N}\mathrm{polylog}(N)/(\epsilon\log\kappa))$ for an $N\times N$ dimensional Hermitian matrix $\bm{F}$, where $\kappa$ denotes the condition number of $\bm{F}$ and $\epsilon$ 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 $\kappa$.

Introduction

Data fitting, particularly through least squares regression, is a fundamental task in machine learning and statistical modeling. However, classical approaches face significant computational challenges as datasets grow in size and density. While previous quantum algorithms, such as the HHL algorithm, offered potential speedups, they typically required the input data matrices to be sparse. In practice, many real-world datasets are dense, rendering these sparsity-dependent algorithms less effective. Furthermore, simple least squares methods are prone to over-fitting, necessitating the use of regularization techniques like ridge regression.

This paper introduces a Quantum Data Fitting (QDF) algorithm specifically designed to handle non-sparse Hermitian matrices efficiently while incorporating regularization to ensure model stability and generalization.

Methodology

The proposed QDF algorithm leverages several key innovations to overcome the limitations of previous quantum linear solvers.

Quantum Singular Value Estimation (QSVE)

Instead of relying on standard Phase Estimation, which is better suited for sparse matrices, the algorithm utilizes Quantum Singular Value Estimation (QSVE). This subroutine interacts with data stored in a classical binary tree structure, allowing the quantum system to access dense data with a complexity that depends on the Frobenius norm rather than the number of non-zero entries.

Sign Recovery via Spectral Shifting

A common challenge in "dense" quantum algorithms is the loss of eigenvalue signs during magnitude estimation. The authors resolve this using a "shift" trick: they analyze a modified matrix $\hat{F} = F + \|F\| I$, where $\|F\|$ is the spectral norm. This shift ensures all eigenvalues are non-negative. After the quantum computation, the shift is subtracted to recover the original eigenvalues with their correct signs. This approach simplifies the data loading process, requiring only one data structure instead of two.

Integrated Regularization

The algorithm directly implements ridge regression by incorporating a regularization parameter $\gamma$ into the quantum circuit's rotation step. This is achieved through a filter function $h(\lambda)$ that suppresses the influence of small eigenvalues, which are often associated with noise.

The behavior of the filter function $|h|$ across different eigenvalues $|\lambda|$ for small, median, and large regularization parameters $\gamma$.

As shown in the figure, the regularization parameter $\gamma$ controls the shape of the filter function, effectively balancing the fit to the data against the complexity of the model to prevent over-fitting.

Complexity and Performance

The primary advantage of this algorithm is its sparsity-independent runtime. The total complexity is $O\left(\frac{\kappa^2 \sqrt{N} \text{polylog}(N)}{\epsilon \log \kappa}\right)$, where $N$ is the matrix dimension, $\kappa$ is the condition number, and $\epsilon$ is the desired precision.

Compared to classical ridge regression, which typically scales as $O(N^2)$ or $O(N^3)$, the quantum algorithm provides a polynomial speedup of $O(\sqrt{N})$. This makes it highly scalable for large-scale data fitting tasks. Additionally, the dependence on the condition number $\kappa$ is strictly less than quadratic, ensuring stability even for ill-conditioned problems.

Conclusion

The proposed QDF algorithm represents a significant step toward practical quantum machine learning for dense datasets. By combining QSVE with an efficient sign-recovery method and integrated regularization, it achieves a robust polynomial speedup over classical methods. Future work may explore the possibility of achieving logarithmic scaling ($O(\log N)$) for non-sparse matrices and addressing the classical pre-processing bottleneck involved in building the required data structures.

Summary updated

Abstract

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 $κ$.
BibTeX
@misc{li2019quantum,
  author = {Guangxi Li and Youle Wang and Yu Luo and Yuan Feng},
  title = {{Quantum Data Fitting Algorithm for Non-sparse Matrices}},
  year = {2019},
  eprint = {1907.06949},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1907.06949},
}
Figure