Quantum Kernels

A quantum kernel measures similarity between data points as the overlap of the quantum states they are encoded into, estimated by running a circuit many times.

Similarity as state overlap

Given a feature map x -> |phi(x)>, the quantum kernel is k(x, x') = ||^2. This is the fidelity between the two encoded states, a number between 0 and 1. It is a legitimate positive semi-definite kernel, so it plugs directly into any kernel method.

How to estimate an entry

The standard method is the overlap or compute-uncompute circuit. Prepare |0...0>, apply U(x), then apply the inverse feature map U(x')-dagger, and measure. The probability of observing the all-zeros bitstring equals ||^2. Because measurement is probabilistic, each entry requires many shots; the estimate has statistical error that shrinks as one over the square root of the number of shots.

# Overlap test for one kernel entry (schematic)
def kernel_entry(x, xp, shots):
    prepare_zero_state()
    apply(U, x)          # U(x)|0>
    apply_inverse(U, xp) # U(x')^dagger U(x)|0>
    counts = measure_all(shots)
    return counts['0'*n_qubits] / shots  # estimate of |<phi(x)|phi(x')>|^2

The exponential concentration problem

As qubit count and circuit depth grow, quantum states tend to become nearly orthogonal, so off-diagonal kernel entries concentrate near zero. The Gram matrix approaches the identity, meaning every point is similar only to itself. A model trained on such a matrix memorizes and generalizes poorly. This exponential concentration is a central obstacle for kernel-based QML and mirrors the barren plateau phenomenon in variational methods.

Bandwidth and mitigation

• Kernel bandwidth: scaling the input features by a small factor keeps encoded states from spreading too far apart, restoring informative off-diagonal entries.
• Shallow, structured maps: reduce concentration and keep the kernel classically hard only where the structure demands it.
• Projected kernels: measure reduced observables rather than full-state overlap to fight concentration.

When quantum kernels can help

A quantum kernel is worthwhile only if it is both a good similarity measure for the task and hard to compute classically. Constructed problems, such as those based on discrete logarithm structure, admit provable separations. For generic real-world tabular data, classical kernels remain strong baselines and must be beaten empirically before any claim of advantage.