Quantum Kernels

The quantum version of SVM was initially proposed by Rebentrost et al. (2014), but this formulation requires the input data to be provided in coherent superposition states. Therefore, when the data are generated on a classical computer, the efficient application of this approach becomes impractical. 

A different approach was proposed by Havlíček et al. (2019), where the data are provided purely classically, while the feature space is mapped by the quantum state $ \Phi: \mathbb{R}^n \rightarrow \vert \Phi(\vec{x}) \rangle \langle \Phi(\vec{x}) \vert $.

A commonly used feature map is ZZFeatureMap, this is a module of qiskit library described by the following equation: \begin{equation*} \mathcal{U}_{\Phi(\vec{x})} = \left[ \exp\left(i \sum_{1 \le j <k \le n} \phi_{\{j,k\}}(\vec{x})\, Z_j \otimes Z_k\right) \exp\left(i \sum_{j=1}^n \phi_{\{j\}}(\vec{x})\, Z_j \right)  H^{\otimes n} \right]^d \end{equation*} Here, $Z$ denotes the Pauli-$Z$ operator, $n$ denotes the number of qubits (corresponding to the number of features), $d$ is the number of repetitions, and $\phi_S(\vec{x})$ is defined as: \begin{equation*} \phi_{S}(\vec{x}) = \begin{cases} x_i, & S = \{i\} \\ (\pi - x_i) (\pi - x_j), & S = \{i, j\} \end{cases} \end{equation*} The feature map is implemented by the following circuit:

This circuit involves a non-linear mapping of the input features. The encoding process works as follows: 

• Initial State: The process begins by preparing all qubits in the initial state $ \vert 0^{\otimes n} \rangle $, followed by the application of Hadamard gates to create a uniform superposition.
• Single-Qubit Rotations: The classical data points are encoded into the rotation angles of single-qubit phase gates.
• Two-Qubit Entanglement: Entangling layers with rotation gates are applied between specified pairs of qubits to introduce two-qubit interactions.

With these ingredients, we can construct the quantum kernel as shown in the following equation: \begin{equation*} K(\vec{x}, \vec{y}) = \lvert \langle \Phi(\vec{x}) \vert \Phi(\vec{y}) \rangle \rvert^2  = \lvert \langle 0^{\otimes n} \vert \mathcal{U}_{\Phi(\vec{x})}^\dagger \mathcal{U}_{\Phi(\vec{y})} \vert 0^{\otimes n} \rangle  \rvert^2 \end{equation*} where $ \mathcal{U}_{\Phi(\vec{x})}^\dagger $ denotes the Hermitian adjoint of $ \mathcal{U}_{\Phi(\vec{x})}$. 

How can we compute this kernel?

The right-hand side of the kernel expression \begin{equation*}\mathcal{U}_{\Phi(\vec{x})}^\dagger \mathcal{U}_{\Phi(\vec{y})} \vert 0^{\otimes n} \rangle \end{equation*} can be constructed as a quantum circuit by initializing the qubits in the zero state $\vert 0^{\otimes n} \rangle$, followed by the application of the gates $\mathcal{U}_{\Phi(\vec{y})}$ and $\mathcal{U}_{\Phi(\vec{x})}^\dagger$.

The left factor $\langle 0^{\otimes n} \vert$ corresponds to projecting onto the state $\vert 0^{\otimes n} \rangle$, and the modulus squared $\lvert  \, \cdot  \, \rvert^2$ yields the probability associated with this outcome. 

Therefore, to compute the kernel, it is sufficient to implement the circuit $\mathcal{U}_{\Phi(\vec{x})}^\dagger \mathcal{U}_{\Phi(\vec{y})} \vert 0^{\otimes n} \rangle $, measure all the qubits, and estimate the probability of obtaining the state $\vert 0^{\otimes n} \rangle$.