Quantum Support Vector Machine for Big Data Classification

2013/07/01 by Patrick Rebentrost, Masoud Mohseni, Seth Lloyd · 1 voice · 20 citations
Computer Science · #Neural Networks and Applications #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #cs.LG #quant-ph

paper · pdf · doi:10.1103/physrevlett.113.130503

openalex publication_date 2014/09/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Supervised machine learning is the classification of new data based on already classified training examples. In this work, we show that the support vector machine, an optimized binary classifier, can be implemented on a quantum computer, with complexity logarithmic in the size of the vectors and the number of training examples. In cases where classical sampling algorithms require polynomial time, an exponential speedup is obtained. At the core of this quantum big data algorithm is a nonsparse matrix exponentiation technique for efficiently performing a matrix inversion of the training data inner-product (kernel) matrix.

Citations

• On the Relationship Between Continuous- and Discrete-Time Quantum Walk

Cited by

• Benefits of Open Quantum Systems for Quantum Machine Learning
• Quantum Perceptron Revisited: Computational-Statistical Tradeoffs
• Image classification and adversarial robustness analysis based on hybrid quantum–classical convolutional neural network
• Quantum Perceptron Models
• Quantum Algorithms in Cybernetics
• Support Vector Machines on Noisy Intermediate Scale Quantum Computers
• Advances in Quantum Deep Learning: An Overview
• Efficient Quantum Circuits for Accurate State Preparation of Smooth, Differentiable Functions
• Classification with Quantum Machine Learning: A Survey
• Efficient quantum state preparation with Walsh series
• Quantum Computing for Molecular Biology**
• Quantum algorithm for finding the negative curvature direction in non-convex optimization
• Quantum Principal Component Analysis Only Achieves an Exponential Speedup Because of Its State Preparation Assumptions
• K-Means Clustering on Noisy Intermediate Scale Quantum Computers
• A Survey of Quantum Learning Theory
• Quantum Hamiltonian-Based Models and the Variational Quantum Thermalizer Algorithm
• Variational Quantum Circuits in Offline Contextual Bandit Problems
• An introduction to quantum machine learning
• Quantum statistical query learning
• Supervised quantum machine learning models are kernel methods

Discussions

• Quantum Support Vector Machine For Big Feature And Big Data Classification [pdf] [hn, 5 points, 0 comments]

Related

• Fundamental Machine Learning Routines as Quantum Algorithms on a Superconducting Quantum Computer
• Adiabatic Quantum Support Vector Machines
• Quantum Sparse Support Vector Machines
• Machine Learning in the Quantum Age: Quantum vs. Classical Support Vector Machines
• Fully Quantum Classifier