Quantum Support Vector Machine

Overview

A support vector machine, or SVM, is a classical machine learning method that separates two classes of data by finding the boundary with the widest margin. The quantum support vector machine proposed by Rebentrost, Mohseni, and Lloyd rephrases the training step as a linear algebra problem and solves it with quantum linear algebra, with a runtime that depends only logarithmically on the number and dimension of the training points.

A second family of ideas, from Havlíček and colleagues in 2019, uses a quantum computer to compute the similarity between data points in a feature space that is hard to compute classically, and then passes that kernel to a classical SVM. The two approaches share a name but have different goals and different caveats.

The problem it solves

Classifying data points into categories by finding an optimal separating boundary — one of the most widely used classical machine learning techniques.

History and background

Rebentrost, Mohseni, and Lloyd posted the original proposal in 2013 and published it in Physical Review Letters in 2014. It built on the HHL algorithm and on the quantum principal component analysis of Lloyd and colleagues, and it was one of the first claims of an exponential speedup for a mainstream machine learning method.

In 2018 and 2019, Ewin Tang and coauthors developed classical sampling-based algorithms that matched the quantum speedup for related low-rank problems, which cast doubt on exponential advantage in this setting. In 2019, Havlíček, Córcoles, Temme, Harrow, Kandala, Chow, and Gambetta at IBM published in Nature a demonstration of quantum-enhanced feature spaces on a two-qubit superconducting processor, and Schuld and Killoran described quantum feature maps in the same year. In 2021 Liu, Arunachalam, and Temme proved a rigorous quantum advantage for a learning task based on the discrete logarithm problem, and Huang and coauthors showed that access to data can let classical models compete with quantum ones.

How it works

Uses quantum matrix inversion techniques (related to HHL) to solve the optimization problem underlying support vector machines, assuming the data is already available as an efficiently preparable quantum state.

Training a least-squares SVM boils down to solving a linear system whose matrix is the kernel matrix K of pairwise similarities between training points, plus a regularization term. The solution gives the weights that define the separating boundary. This is a matrix inversion problem of exactly the kind HHL addresses.

If the data points can be loaded as quantum states, then the kernel matrix, which has size N by N for N training points, can be written as a density matrix and exponentiated using density matrix exponentiation, taking a number of operations that depends on the logarithm of N. Quantum phase estimation and a controlled rotation then invert the matrix and produce a state encoding the SVM's weights.

The quantum-kernel approach is different. It maps each data point to a quantum state using a parameterized circuit, which is a feature map, and estimates the inner product between two such states. The kernel entries are computed by repeating a circuit many times, and a classical computer does the optimization. The potential advantage is that the feature space might be too complicated for classical kernels to reproduce.

Step by step

1. Collect the training data and labels, and choose a regularization parameter.
2. Load the training vectors into a quantum state using quantum random access memory, or encode each data point through a feature-map circuit.
3. In the matrix inversion version, build the kernel matrix as a density matrix and apply density matrix exponentiation and quantum phase estimation to invert it.
4. Perform the controlled rotation and measurement as in HHL to obtain a state encoding the solution weights.
5. To classify a new point, use a swap test or inner-product estimation between the new point and the encoded solution.
6. In the quantum-kernel version, estimate each kernel entry by running the feature-map circuits and measuring overlaps, then train a classical SVM on the resulting kernel matrix.

A worked example

Suppose you want to classify a million-dimensional data set with ten million training examples. A classical SVM training scales polynomially in the number of examples, roughly with the square or cube of the data size for exact methods. The quantum algorithm claims a runtime proportional to the logarithm of those numbers, provided the data is available in a quantum memory and the kernel matrix is well conditioned.

On real hardware, the demonstration by Havlíček and colleagues used two qubits to classify a small artificial data set, with the quantum computer estimating kernel entries. It confirmed that the method works, but it did not demonstrate any advantage, since the problem is easy classically.

Complexity and resources

What hardware it needs

• For the matrix inversion version, a fault-tolerant quantum computer with quantum random access memory.
• For the kernel version, a modest number of qubits and high-fidelity gates, enough to compute inner products between feature-mapped states.
• A classical computer to train the SVM on the kernel matrix.

Applications

• Classification tasks in image recognition, bioinformatics, and finance, if quantum data access is available.
• Quantum data classification, where the data is already a quantum state, for example from quantum sensors or simulations.
• Benchmarking quantum feature maps for datasets with specific structure.

Limitations and caveats

• The exponential speedup of the original proposal relies on loading data efficiently into quantum states, which is a major unsolved problem.
• Dequantization results show classical algorithms can match the speedup for low-rank data.
• Quantum kernels can suffer from exponential concentration, which makes kernel values nearly identical and hard to learn from.
• No quantum SVM has beaten a good classical classifier on a practical benchmark.

Common misconceptions

• A quantum SVM is not generally more accurate than a classical SVM. The claimed advantage is in speed under particular assumptions.
• Using a quantum computer to compute a kernel does not guarantee a better model. The kernel must capture structure that classical kernels cannot.
• The original speedup is not preserved if the data must be loaded from a classical database.

How it compares

• Quantum kernel estimation is the modern, hardware-oriented form of the idea.
• Quantum PCA and HHL are the building blocks of the matrix inversion version.
• Classical SVMs and neural networks are extremely well optimized and difficult to beat.

Real-world impact

An influential early quantum machine learning proposal, though subsequent research has emphasized that the 'input problem' of loading classical data into quantum states efficiently undermines much of the theoretical speedup in practice.

Why it matters

The quantum SVM was a flagship proposal of early quantum machine learning, and the dequantization story it prompted taught the field to examine input and output assumptions. The kernel viewpoint that grew from it is now the main framework for thinking about quantum machine learning models.

It is also a good test for readers: whenever a quantum learning claim appears, ask how the data is loaded, what the classical baseline is, and whether the result survives dequantization.

Frequently asked questions

Keep learning

• Related algorithm: Quantum Kernel Estimation
• Related algorithm: HHL Algorithm
• Related algorithm: Quantum Principal Component Analysis
• Related algorithm: SWAP Test

This page is written for educational purposes. Complexity statements describe the best known results at the time of review (September 30, 2026), and research in this area moves quickly, so check recent papers before relying on a specific bound.

← Back to Algorithms Database