Properties of Quantum Kernels

Having established how quantum kernels $k(x, x')$ arise from inner products in quantum feature spaces, let's examine their essential mathematical properties. Just like their classical counterparts, understanding these characteristics is fundamental to effectively using quantum kernels in machine learning algorithms like Support Vector Machines (SVMs). These properties dictate the behavior of the kernel function and influence the geometry of the induced feature space, which in turn affects model performance and trainability.

Relationship between classical data, quantum feature states, their inner product, and the resulting kernel value.

Positive Semi-Definiteness (PSD)

A core requirement for any function to be a valid kernel in the context of SVMs and other kernel methods is that it must be positive semi-definite (PSD). This property ensures that the matrix formed by evaluating the kernel on any set of data points, known as the Gram matrix $K$, has non-negative eigenvalues. Formally, for any dataset $\{x_1, ..., x_N\}$ and any complex coefficients $\{c_1, ..., c_N\}$, the following condition must hold:

$$\sum_{i=1}^{N} \sum_{j=1}^{N} \bar{c}_i K_{ij} c_j \ge 0$$

where $K_{ij} = k(x_i, x_j)$. This condition is intrinsically linked to the existence of an underlying feature map $\phi$ such that $k(x, x') = \langle \phi(x) | \phi(x') \rangle$.

Let's verify this for quantum kernels. If we define the kernel directly as the inner product: $k(x, x') = \langle \phi(x) | \phi(x') \rangle$ where $|\phi(x)\rangle$ is the quantum state corresponding to data point $x$. Then, the sum becomes:

$$\sum_{i,j} \bar{c}_i \langle \phi(x_i) | \phi(x_j) \rangle c_j = \left\langle \sum_i c_i \phi(x_i) \;\middle|\; \sum_j c_j \phi(x_j) \right\rangle = \left\| \sum_i c_i |\phi(x_i)\rangle \right\|^2$$

Since the norm squared of any vector in Hilbert space is non-negative, the condition is satisfied. Thus, kernels defined directly as inner products in Hilbert space are always PSD.

Often in quantum machine learning, the kernel is defined based on the measurement probability or fidelity between the feature states, commonly taking the form: $k(x, x') = |\langle \phi(x) | \phi(x') \rangle|^2$

Is this function still PSD? Yes, it is. Consider the Gram matrix $G$ where $G_{ij} = \langle \phi(x_i) | \phi(x_j) \rangle$. We know $G$ is PSD. The kernel matrix $K$ we are interested in has elements $K_{ij} = |\langle \phi(x_i) | \phi(x_j) \rangle|^2 = G_{ij} \overline{G_{ij}}$. This can be seen as the element-wise product (Hadamard product) of $G$ and its complex conjugate $\bar{G}$. Since $G$ is PSD, $\bar{G}$ is also PSD. The Schur Product Theorem states that the Hadamard product of two PSD matrices is also PSD. Therefore, quantum kernels defined as $k(x, x') = |\langle \phi(x) | \phi(x') \rangle|^2$ are guaranteed to be valid, PSD kernels.

This PSD property is significant because it guarantees that the optimization problem underlying SVMs remains convex, ensuring that we can find a unique global minimum.

Normalization and Boundedness

Quantum kernels, particularly those defined as $k(x, x') = |\langle \phi(x) | \phi(x') \rangle|^2$, often exhibit natural normalization properties stemming from the nature of quantum states. Assuming the quantum feature states $|\phi(x)\rangle$ are normalized states (i.e., $\langle \phi(x) | \phi(x) \rangle = 1$), we have:

• Diagonal Elements: $k(x, x) = |\langle \phi(x) | \phi(x) \rangle|^2 = 1^2 = 1$. The kernel value of a data point with itself is always 1.
• Off-Diagonal Elements: By the Cauchy-Schwarz inequality, $|\langle \phi(x) | \phi(x') \rangle| \le \sqrt{\langle \phi(x) | \phi(x) \rangle} \sqrt{\langle \phi(x') | \phi(x') \rangle} = 1$. Therefore, $0 \le |\langle \phi(x) | \phi(x') \rangle|^2 \le 1$.

So, this common form of the quantum kernel naturally produces values between 0 and 1, where 1 indicates identical feature states (up to a global phase) and values closer to 0 indicate more dissimilar (orthogonal) states. This boundedness can be helpful in practice, preventing numerical issues and providing an intuitive scale for similarity. However, normalization of the input states $|\phi(x)\rangle$ is a prerequisite, which is standard practice in quantum computation.

Universality

In classical machine learning, a kernel is called universal if the corresponding Reproducing Kernel Hilbert Space (RKHS) is dense in the space of continuous functions on the input domain. Practically, this means an SVM with a universal kernel can approximate any arbitrary decision boundary, given enough data. The Gaussian (RBF) kernel is a well-known example of a universal classical kernel.

Can quantum kernels be universal? The answer depends entirely on the expressivity of the quantum feature map $\phi$.

• If the feature map $\phi$ is restricted and can only generate a limited subset of states in the Hilbert space, the resulting kernel might not be universal.
• If the feature map $\phi$ is sufficiently powerful or expressive, meaning it can approximate any unitary transformation or generate states that densely cover the Hilbert space, then the resulting kernel has the potential to be universal.

Research suggests that certain quantum feature maps, especially those involving sufficient entanglement and data re-uploading structures (as discussed in Chapter 2), can indeed lead to universal kernels. Proving universality often involves analyzing the richness of the functions $x \mapsto |\phi(x)\rangle$ and relating it to Fourier analysis or function approximation theory. The ability to generate high-frequency components in the kernel function is often linked to universality. Achieving universality might require feature maps with a number of parameters growing with the size of the dataset or the complexity of the target function.

Dependence on Feature Map Choice

It cannot be stressed enough: The properties and performance of a quantum kernel are entirely determined by the choice of the quantum feature map $\phi$. Different circuits used for encoding $x$ into $|\phi(x)\rangle$ will lead to different kernels. Consider these factors influenced by the feature map design:

• Dimensionality: The number of qubits used determines the nominal dimension of the Hilbert space.
• Entanglement: The amount and structure of entanglement generated by the circuit significantly impact the correlations captured by the inner product.
• Non-linearity: How the parameters derived from $x$ are loaded into the circuit gates introduces non-linear dependencies, shaping the geometry of the feature space. Circuits using data re-uploading can create highly complex, non-linear feature maps.

Therefore, designing or choosing an appropriate feature map is a central task in quantum kernel methods. A feature map that works well for one dataset might perform poorly on another. This connects back strongly to the topics covered in Chapter 2 on encoding strategies and their expressibility.

Computational Challenges and Noise

While mathematically elegant, the practical estimation of quantum kernels $k(x, x') = |\langle \phi(x) | \phi(x') \rangle|^2$ on quantum hardware introduces complications:

• Estimation: We don't get the exact value but an estimate based on repeated measurements (e.g., using the SWAP test or inversion test circuits). This requires a number of circuit executions and measurements, introducing statistical uncertainty.
• Noise: Decoherence, gate errors, and readout errors on current quantum processors will corrupt the computation, leading to biased or noisy estimates of the kernel entries.
• Impact on Properties: Noise and statistical error mean that an empirically estimated kernel matrix might slightly deviate from perfect positive semi-definiteness. This may require mitigation techniques or careful handling in the classical optimization part of the algorithm (e.g., by adding a small value to the diagonal of the estimated kernel matrix).

These practical aspects related to hardware noise and estimation will be discussed in greater detail in Chapter 7.

In summary, quantum kernels inherit the essential PSD property from their definition via inner products in Hilbert space. Their normalization depends on the normalization of feature states, and their potential universality relies on the expressivity of the chosen quantum feature map. The tight coupling between the feature map design and the kernel's properties makes feature map engineering a critical aspect of applying these methods successfully.