Quantum-Inspired Classical Algorithm for Principal Component Regression
This paper presents a sublinear classical algorithm for principal component regression. The algorithm uses quantum-inspired linear algebra, an idea developed by Tang. Using this technique, her algorithm for recommendation systems achieved runtime only polynomially slower than its quantum counterpart. Her work was quickly adapted to solve many other problems in sublinear time complexity. In this work, we developed an algorithm for principal component regression that runs in time polylogarithmic to the number of data points, an exponential speed up over the state-of-the-art algorithm, under the mild assumption that the input is given in some data structure that supports a norm-based sampling procedure. This exponential speed up allows for potential applications in much larger data sets.
Code (0)
등록된 구현이 없습니다.
Tasks
Recommendation SystemsregressionSimilar Papers 제목 키워드 기반
Quantum principal component analysis only achieves an exponential speedup because of its state preparation assumptions
A central roadblock to analyzing quantum algorithms on quantum states is the lack of a comparable input model for classical algorithms. Inspired by recent work of the author [E. Tang, STOC'19], we introduce such a model,…
ClusteringRecommendation SystemsA Quantum-Inspired Ensemble Method and Quantum-Inspired Forest Regressors
We propose a Quantum-Inspired Subspace(QIS) Ensemble Method for generating feature ensembles based on feature selections. We assign each principal component a Fraction Transition Probability as its probability weight bas…
DiversityregressionClassical and Quantum Algorithms for Tensor Principal Component Analysis
We present classical and quantum algorithms based on spectral methods for a problem in tensor principal component analysis. The quantum algorithm achieves a quartic speedup while using exponentially smaller space than th…
Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning
We present an algorithmic framework for quantum-inspired classical algorithms on close-to-low-rank matrices, generalizing the series of results started by Tang's breakthrough quantum-inspired algorithm for recommendation…
BIG-bench Machine LearningClusteringQuantum Machine LearningRecommendation SystemsAn end-to-end trainable hybrid classical-quantum classifier
We introduce a hybrid model combining a quantum-inspired tensor network and a variational quantum circuit to perform supervised learning tasks. This architecture allows for the classical and quantum parts of the model to…
Tensor Networks