Quantum-Inspired Support Vector Machine

Abstract

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.

References in corpus (5)

• Quantum algorithm for solving linear systems of equations
• Hybrid Quantum-Classical Convolutional Neural Networks
• Demonstration of Shor's quantum factoring algorithm using photonic qubits
• Quantum-inspired algorithms in practice
• Experimental Blind Quantum Computing for a Classical Client

Cited by in corpus (14)

• A rigorous and robust quantum speed-up in supervised machine learning
• Sampling-based sublinear low-rank matrix arithmetic framework for dequantizing quantum machine learning
• Quantum-inspired Complex Convolutional Neural Networks
• A brief introduction to quantum algorithms
• Quantum Computing: Vision and Challenges
• A Quantum-Classical Collaborative Training Architecture Based on Quantum State Fidelity
• A Quantum-inspired Algorithm for General Minimum Conical Hull Problems
• Variational Quantum Support Vector Machine based on $\Gamma$ matrix expansion and Variational Universal-Quantum-State Generator
• Quantum-inspired canonical correlation analysis for exponentially large dimensional data
• Parametrized constant-depth quantum neuron
• A quantum-inspired algorithm for approximating statistical leverage scores
• Trustworthy Artificial Intelligence for Cyber Threat Analysis
• Benchmarking of quantum fidelity kernels for Gaussian process regression
• Quantum-Inspired Weight-Constrained Neural Network: Reducing Variable Numbers by 100x Compared to Standard Neural Networks