Extended Quantum Computing Patterns

Use a quantum routine to estimate a kernel for a classical SVM.

A support vector machine (SVM) must be found to classify a set of data points \(\{x_i\}\subseteq \mathcal{R}^d\) according to their labels. Therefore, a hyperplane must be found that (i) separates the data points of the different classes and (ii) maintains a maximal distance to the data points. A large margin between the hyperplane and the data points ensures that unseen data points are classified correctly with a high probability. The given data set is not guaranteed to be linearly separable, and thus, it may not be possible to find such a separating hyperplane in the original space. If this is the case, a hyperplane in a higher dimensional feature space to which the data points are mapped (implicitly) can be used instead.

–

To find a separating hyperplane, a quantum computer is used to estimate the kernel function \(K(x,x')=|\left<\phi(x)|\phi(x')\right>|^2\): A pair of data points \((x,x')\) is encoded into the Hilbert Space according to a quantum feature map \(\phi\) (see solution sketch). This allows to use, e.g., a SWAP test routine to estimate the inner product \(\left<\phi(x)|\phi(x')\right>\) of the two points (Schuld and Killoran) The result can then be used to compute the kernel function for this pair of data points, based on which the SVM is optimized on a classical computer.

Pattern sketch, taken from: Weigold, Manuela; Barzen, Johanna; Leymann, Frank; and Vietz, Daniel: Patterns For Hybrid Quantum Algorithms. In: Proceedings of the 15th Symposium and Summer School on Service-Oriented Computing (SummerSOC 2021).

Both the training as well as the classification is efficient, given that the evaluation of the inner products can be done in an efficient manner. The main advantage of this setup is that the quantum computer has the potential to compute inner products in a feature space that cannot be evaluated efficiently on a classical computer. Still, a key open question regarding this setup remains how to choose a feature map for a given data set.

–

This pattern is a refinement of the Quantum-Classic Split. Here, the quantum computer is only used to estimate a single function, while the rest of the computations are left to the classical computer.

The solution above was first proposed in (Havlíček et al. 2019) where it was also demonstrated in an experiment involving two qubits. Independently, the same solution was developed in (Schuld and Killoran 2019) which additionally presents a feature map targeted for quantum devices based on continuous-variable qubits. Another proof-of-principle demonstration was conducted by (Bartkiewicz et al. 2020) using photonic qubits. This approach was also further investigated in (Ghobadi, Oberoi and Zahedinejad 2019). In our QHAna project (Barzen 2021), we also provide an implementation of this pattern along with a user interface to select one of various quantum feature maps.