Quantum Kernel Estimation

Overview

A kernel is a function that measures how similar two data points are, and many machine learning methods, including support vector machines, use kernels to separate data that is not linearly separable in its original form. Quantum kernel estimation uses a quantum computer to compute a kernel by mapping each data point into a quantum state and measuring the overlap between the states for two points.

The hope is that quantum states live in a space so large and so structured that kernels built from them capture patterns classical kernels cannot. The challenge, as the field has found, is that this larger space is also harder to use, and no quantum kernel has yet outperformed good classical methods on real data.

The problem it solves

Classical kernel methods struggle with high-dimensional feature spaces. Quantum feature maps can create exponentially large feature spaces that may be classically hard to compute.

History and background

Havlíček and colleagues at IBM and Schuld and Killoran at Xanadu proposed the idea in 2018, and both papers appeared in 2019, the first in Nature under the title Supervised Learning with Quantum-Enhanced Feature Spaces and the second in Physical Review Letters. Havlíček's team implemented the method on a two-qubit superconducting processor and classified small artificial datasets.

Theory developed quickly. Schuld showed in 2021 that many quantum machine learning models can be understood as kernel methods. Liu, Arunachalam, and Temme proved a rigorous quantum advantage for a classification task based on the discrete logarithm problem in 2021. Huang and coauthors showed in the same year that classical models given training data can compete with quantum ones on many tasks. Thanasilp, Wang, Cerezo, and Holmes described exponential concentration of quantum kernels in 2022, which explains why many natural quantum kernels fail to be useful as the number of qubits grows.

How it works

Encodes classical data into quantum states using a parameterized circuit (feature map). Computes the kernel (inner product) between data points by running the circuits on a quantum processor and measuring overlap.

A kernel method never works with the data in its raw form. It works with the matrix of pairwise similarities between all training points. If the similarity function corresponds to an inner product in some feature space, then the learning algorithm effectively operates in that space, without ever writing down the features.

A quantum feature map is a circuit U of x that prepares a quantum state from a data point x. The kernel between two points is the squared overlap between their states. To estimate it, you run the circuit for x, then the inverse of the circuit for z, and measure the probability of returning to the all-zeros state. That probability equals the squared overlap.

The Havlíček feature map applies Hadamard gates, then phase rotations that depend on the data, then Hadamard gates and a second round of data-dependent phases. Circuits of this kind are related to IQP circuits, which are believed hard to simulate classically. If the useful structure in the data lines up with what such a feature map highlights, the quantum kernel could in principle be useful.

Step by step

1. Choose a feature map circuit U of x that encodes a classical data point x into an n-qubit state.
2. For each pair of training points x and z, run the circuit U of x followed by the inverse of U of z on the zero state, and measure all qubits in the computational basis.
3. Estimate the kernel entry as the fraction of measurements that give the all-zeros string, using many shots per pair.
4. Assemble the estimates into a kernel matrix for all pairs of training points, with the number of pairs growing as the square of the data set size.
5. Train a classical kernel machine, such as an SVM, on this kernel matrix to find the decision boundary.
6. To classify a new point, compute its kernel values against the support vectors with the same circuits and apply the trained classifier.

A worked example

For a data set of 100 training points, the kernel matrix has 100 times 99 over 2, about 4,950 independent entries. If each entry needs 1,000 shots to reach a standard error of about 1.5 percent, the total is about five million circuit executions. That is feasible on a cloud device, but it grows quadratically with the training set size.

In the original IBM demonstration, two-dimensional data points were encoded on two qubits, and the classifier achieved high accuracy on a synthetic data set designed to match the feature map. The result showed that the pipeline works, but a classical kernel could also separate that data easily.

Complexity and resources

What hardware it needs

• A quantum processor with enough qubits and fidelity to run the feature-map circuits and their inverses.
• Large numbers of shots, with fast execution, since the number of kernel entries grows quadratically.
• A classical computer to train the kernel machine.

Applications

• Classification and regression with kernel methods, in research studies on synthetic and small real data sets.
• Particle physics event classification and materials property prediction in exploratory projects.
• Studying quantum advantage in learning with specially structured data.
• Quantum data classification, where the inputs are already quantum states.

Limitations and caveats

• No quantum kernel has beaten strong classical methods on practical data.
• Exponential concentration makes many natural feature maps untrainable at scale.
• The quadratic number of circuit evaluations is costly.
• Noise reduces the contrast of the kernel and degrades performance.

Common misconceptions

• Using a quantum computer to compute a kernel does not guarantee a better classifier.
• A larger feature space is not automatically more useful. It must match the structure of the data.
• The quantum part only computes the kernel. Training and prediction are classical.

How it compares

• The quantum support vector machine of Rebentrost and coauthors uses quantum linear algebra to train the SVM, rather than quantum circuits to compute the kernel.
• Classical kernels such as the radial basis function are cheap and effective.
• Variational quantum classifiers train a circuit directly instead of using a fixed feature map.

Real-world impact

Active research area for quantum ML advantage — some datasets with quantum structure show separation from classical kernels, though finding practical datasets remains an open problem.

Why it matters

Quantum kernels gave quantum machine learning a clear and rigorous framework. They pose the central question of the field: is there data for which quantum feature spaces help? The provable separations and the concentration results are the main guides to answering it.

They also show how a model can be tested without waiting for large hardware, because the kernel matrix is a well-defined object that can be compared with classical alternatives.

Frequently asked questions

Keep learning

• Related algorithm: Quantum Support Vector Machine
• Related algorithm: SWAP Test
• Related algorithm: Quantum Anomaly Detection
• Related algorithm: Quantum GAN (QGAN)

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