Quantum Data Fitting Algorithm for Non-sparse Matrices
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$.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Benign Overfitting with Quantum Kernels
Quantum kernels quantify similarity between data points by measuring the inner product between quantum states, computed through quantum circuit measurements. By embedding data into quantum systems, quantum kernel feature…
A Structured Sparse Neural Network and Its Matrix Calculations Algorithm
Gradient descent optimizations and backpropagation are the most common methods for training neural networks, but they are computationally expensive for real time applications, need high memory resources, and are difficul…
Representing Additive Gaussian Processes by Sparse Matrices
Among generalized additive models, additive Mat\'ern Gaussian Processes (GPs) are one of the most popular for scalable high-dimensional problems. Thanks to their additive structure and stochastic differential equation re…
Additive modelsBayesian OptimizationGaussian ProcessesA Hybrid Quantum-Classical Algorithm for Robust Fitting
Fitting geometric models onto outlier contaminated data is provably intractable. Many computer vision systems rely on random sampling heuristics to solve robust fitting, which do not provide optimality guarantees and err…
Robust Dequantization of the Quantum Singular value Transformation and Quantum Machine Learning Algorithms
Several quantum algorithms for linear algebra problems, and in particular quantum machine learning problems, have been "dequantized" in the past few years. These dequantization results typically hold when classical algor…
Quantum Machine LearningRecommendation Systems