The Quantum Kernel Trick Formalism

Recall from classical machine learning, particularly algorithms like Support Vector Machines (SVMs), the power of the kernel trick. It allows us to implicitly operate in a high-dimensional feature space without ever needing to compute the coordinates of our data in that space explicitly. Instead, we only need a function, the kernel $k(x, x')$, that calculates the inner product between the mapped data points $\phi(x)$ and $\phi(x')$ in that feature space.

Quantum machine learning uses a similar concept, building upon the quantum feature maps introduced previously. A quantum feature map $U_\phi(x)$ encodes a classical data point $x$ into a quantum state $|\phi(x)\rangle = U_\phi(x)|0...0\rangle$ residing in a Hilbert space $\mathcal{H}$. This Hilbert space can be exponentially large in the number of qubits, serving as our potentially very high-dimensional feature space.

The quantum kernel $k(x, x')$ is defined as a function of the inner product between two quantum feature states, $|\phi(x)\rangle$ and $|\phi(x')\rangle$. A common and practically useful definition is:

$$k(x, x') = |\langle\phi(x)|\phi(x')\rangle|^2$$

Why the squared magnitude? As we'll see, this specific form relates directly to a probability that can be estimated by measuring a quantum circuit, making it suitable for near-term quantum hardware. Other functions of the inner product are possible, but this form is prevalent.

Substituting the definition of the feature states using the unitary $U_\phi$:

$$k(x, x') = |\langle 0...0 | U_\phi(x)^\dagger U_\phi(x') | 0...0 \rangle|^2$$

This equation reveals the essence of the quantum kernel trick:

1. Implicit Mapping: We define a mapping $x \mapsto |\phi(x)\rangle$ into a potentially vast quantum Hilbert space $\mathcal{H}$.
2. Direct Inner Product Calculation: We compute the kernel $k(x, x')$ without explicitly constructing the full state vectors $|\phi(x)\rangle$ and $|\phi(x')\rangle$, which could require exponential classical resources. Instead, we design a quantum circuit whose measurement outcome statistics allow us to estimate the required inner product (or its squared magnitude).

How the Calculation Works

The core idea is to prepare the states $|\phi(x)\rangle$ and $|\phi(x')\rangle$ (or states related to them) within a quantum circuit and then perform operations and measurements that reveal their overlap $\langle\phi(x)|\phi(x')\rangle$.

Consider the unitary transformation $V = U_\phi(x)^\dagger U_\phi(x')$. The inner product we need is the expectation value of this unitary in the initial state $|0...0\rangle$:

$$\langle\phi(x)|\phi(x')\rangle = \langle 0...0 | V | 0...0 \rangle$$

Circuits can be designed to estimate quantities like $|\langle 0...0 | V | 0...0 \rangle|^2$. For example, the "swap test" circuit or related interference-based circuits measure the fidelity between two states, which corresponds to the squared magnitude of their inner product. We apply $U_\phi(x')$ to one register initialized to $|0...0\rangle$, apply $U_\phi(x)$ to another register initialized to $|0...0\rangle$, and then use auxiliary qubits and controlled operations to interfere these states. Measuring the auxiliary qubit yields information about $|\langle\phi(x)|\phi(x')\rangle|^2$.

Flow of the quantum kernel trick. Classical data points $x$ and $x'$ are implicitly mapped to quantum states $|\phi(x)\rangle$ and $|\phi(x')\rangle$ via feature map unitaries $U_\phi$. A quantum circuit directly estimates their overlap, yielding the kernel value $k(x, x')$, bypassing explicit representation in the high-dimensional Hilbert space $\mathcal{H}$.

Relation to Classical Kernel Methods

The beauty of this formalism lies in its compatibility with classical kernel machines. Once we can compute the quantum kernel matrix $K$, where $K_{ij} = k(x_i, x_j)$ for a dataset $\{x_1, ..., x_N\}$, we can feed this matrix directly into classical algorithms like:

• Support Vector Machines (SVM)
• Kernel Ridge Regression
• Gaussian Processes
• Kernel Principal Component Analysis (KPCA)

The classical algorithm performs its optimization or analysis solely based on the kernel matrix $K$, effectively operating in the quantum feature space $\mathcal{H}$ without needing direct access to it. The hypothesis is that quantum feature maps $U_\phi(x)$ might create correlations or structures in $\mathcal{H}$ that are hard to achieve with classical feature maps, potentially leading to better performance on certain datasets.

Mathematical Properties

For $k(x, x')$ to be a valid kernel for many classical algorithms (like SVM), the resulting kernel matrix $K$ must be positive semi-definite (PSD). This means for any vector $c$, the quadratic form $c^T K c \ge 0$.

Fortunately, the commonly used quantum kernel definition $k(x, x') = |\langle\phi(x)|\phi(x')\rangle|^2$ generally leads to a PSD kernel matrix. Let $G$ be the Gram matrix with entries $G_{ij} = \langle\phi(x_i)|\phi(x_j)\rangle$. The Gram matrix is always PSD. The quantum kernel matrix $K$ we defined has entries $K_{ij} = |G_{ij}|^2$. This matrix $K$ is the Hadamard product (element-wise product) of $G$ and its complex conjugate $G^*$. According to the Schur product theorem, the Hadamard product of two PSD matrices is also PSD. Since both $G$ and $G^*$ are PSD, their Hadamard product $K$ is also PSD.

This ensures that we can readily use these quantum kernels within standard kernel method frameworks. The next section will detail the practical methods for actually calculating these kernel matrix entries using quantum circuits and simulators.