Quantum Support Vector Machine

Two distinct approaches to quantum classification: fast kernel evaluation and linear-system-based training.

Two flavors

The term quantum support vector machine (QSVM) covers two quite different ideas. The first uses a quantum computer only to evaluate a kernel, a similarity measure between data points, then hands that kernel to a classical SVM. The second, the least-squares QSVM, casts training as a linear system solved with the HHL algorithm.

Quantum kernel method

Map each classical input x to a quantum state |phi(x)> using a feature map circuit. The kernel K(x,x') = ||^2 is estimated on hardware, for example with a swap test or an overlap circuit. If the feature map produces states that are hard to simulate classically, the resulting kernel may separate data that no efficient classical kernel can. The classical SVM then finds the maximum-margin hyperplane in this quantum feature space.

Kernel workflow

• Encode data via a parameterized feature-map circuit.
• Estimate pairwise overlaps to fill the kernel matrix.
• Train a standard SVM on the kernel matrix classically.
• Classify new points by their kernel similarities to support vectors.

Least-squares QSVM

Reformulating the soft-margin SVM as a least-squares problem yields a system of linear equations. Encoding the data in amplitudes and applying HHL solves for the hyperplane parameters in time polylogarithmic in the number of features and samples, under strong input assumptions (efficient state preparation, well-conditioned matrix). The output is a quantum state encoding the classifier.

Where the advantage lives

The kernel approach is near-term friendly and its power rests on kernels that are classically intractable yet useful. The HHL approach offers dramatic asymptotic speedups but inherits HHL's caveats: conditioning, readout, and data loading. In both cases, demonstrating advantage on real datasets remains an active research question rather than a settled result.