Quantum Data Fitting Algorithm for Non-sparse Matrices

2019/07/16 by Li, Guangxi, Wang, Youle, Luo, Yu +1
#FOS: Computer and information sciences #FOS: Physical sciences #Machine Learning (cs.LG) #Quantum Physics (quant-ph)

paper · doi:10.48550/arxiv.1907.06949

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(κ²√(N)polylog(N)/(εlogκ)) for an N× N dimensional Hermitian matrix \bmF, where κ denotes the condition number of \bmF 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 κ.

Related

• Robust Dequantization of the Quantum Singular value Transformation and Quantum Machine Learning Algorithms
• A square-root speedup for finding the smallest eigenvalue
• A general quantum matrix exponential dimensionality reduction framework based on block-encoding
• Quantum-inspired low-rank stochastic regression with logarithmic dependence on the dimension
• Quantum Algorithms for Prediction Based on Ridge Regression