Korva is a scroll of the internet’s best ideas.
Quantum kernels run one map backwards
Lifting data into qubits
Support vector machines lean on a kernel function, which classically comes from a dot product of matrices. Quantum computing already offers a ready-made way to lift data into a higher dimension, because standard circuits map classical data onto qubits and use the angle of each qubit as an additional dimension, with the probability still there.
Entangling embeddings
Other embeddings entangle the qubits as well and use the entanglement space to encode the data in a much higher-dimensional space. The ZZ feature map is one of them, combining entanglement with superposition to represent classical data this way.
Joining the circuits
The kernel then comes almost for free. Take the feature map of one element of the data set, take the reverse feature map of another, and join the two circuits. The larger circuit automatically calculates the kernel function. For certain types of data, papers show this gives a polynomial advantage in training over the classical counterpart.
Why does running one map backwards give a kernel?
Applying one point's feature map and then the inverse of another's makes the qubits return to all zeros with a probability equal to the squared overlap of the two encoded states. That overlap is an inner product in the quantum feature space, which is exactly what a kernel is. Repeating the circuit many times and counting how often all zeros appears estimates it. The method is often called compute-uncompute.
Where did the ZZ feature map come from?
Havlicek and colleagues at IBM introduced it in a 2019 Nature paper titled Supervised learning with quantum-enhanced feature spaces. It encodes each data point with single-qubit rotations and with gates that couple pairs of qubits. They ran a classifier on a superconducting processor with two qubits. They also conjectured that the kernel for such circuits is hard to compute on classical machines.
Why does the support vector machine only need kernel values?
Training a support vector machine solves an optimization problem written entirely in terms of dot products between pairs of training points. Replacing every dot product with a kernel value gives the same problem in the richer feature space. For n training points, the optimizer needs just an n by n table of kernel values, called the Gram matrix. A quantum computer can fill in that table one entry at a time.