Quantum-Inspired Support Vector Machine
Support vector machine (SVM) is a particularly powerful and flexible supervised learning model that analyzes data for both classification and regression, whose usual algorithm complexity scales polynomially with the dimension of data space and the number of data points. To tackle the big data challenge, a quantum SVM algorithm was proposed, which is claimed to achieve exponential speedup for least squares SVM (LS-SVM). Here, inspired by the quantum SVM algorithm, we present a quantum-inspired classical algorithm for LS-SVM. In our approach, a improved fast sampling technique, namely indirect sampling, is proposed for sampling the kernel matrix and classifying. We first consider the LS-SVM with a linear kernel, and then discuss the generalization of our method to non-linear kernels. Theoretical analysis shows our algorithm can make classification with arbitrary success probability in logarithmic runtime of both the dimension of data space and the number of data points for low rank, low condition number and high dimensional data matrix, matching the runtime of the quantum SVM.
Code (0)
등록된 구현이 없습니다.
Tasks
General ClassificationMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
On Neural Quantum Support Vector Machines
In \cite{simon2023algorithms} we introduced four algorithms for the training of neural support vector machines (NSVMs) and demonstrated their feasibility. In this note we introduce neural quantum support vector machines,…
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 Investigation on Support Vector Clustering for Big Data in Quantum Paradigm
The support vector clustering algorithm is a well-known clustering algorithm based on support vector machines using Gaussian or polynomial kernels. The classical support vector clustering algorithm works well in general,…
ClusteringUniversal expressiveness of variational quantum classifiers and quantum kernels for support vector machines
Machine learning is considered to be one of the most promising applications of quantum computing. Therefore, the search for quantum advantage of the quantum analogues of machine learning models is a key research goal. He…
BIG-bench Machine LearningMachine Learning in the Quantum Age: Quantum vs. Classical Support Vector Machines
This work endeavors to juxtapose the efficacy of machine learning algorithms within classical and quantum computational paradigms. Particularly, by emphasizing on Support Vector Machines (SVM), we scrutinize the classifi…
Hyperparameter OptimizationQuantum Machine Learning