Higher-Order Polynomial Quantum Feature Maps

While basic quantum feature maps, like those encoding data features into single-qubit rotations, provide a starting point, they often correspond to linear structures in the quantum feature space. Classical machine learning frequently benefits from non-linear transformations of input data, enabling models to capture complex relationships and decision boundaries. Polynomial kernels, for instance, are a standard technique in algorithms like Support Vector Machines (SVMs) to achieve this. They implicitly map data into a higher-dimensional space where features correspond to polynomial combinations of the original inputs, without explicitly calculating these high-dimensional vectors.

Quantum computing offers a way to construct feature maps that naturally generate equivalent, or potentially more powerful, non-linear relationships, including higher-order polynomial interactions between input features. The core idea is to design the quantum circuit $U(x)$, which transforms the initial state $|0\rangle^{\otimes n}$ into the feature state $|\phi(x)\rangle = U(x)|0\rangle^{\otimes n}$, such that the interactions between qubits, modulated by the input data $x$, create entanglement patterns that encode these polynomial terms.

Constructing Polynomial Feature Maps

Consider a classical data point $x = (x_1, x_2, ..., x_d)$. A simple feature map might encode each $x_i$ into the rotation angle of a single qubit. To introduce polynomial terms, we need interactions. This is typically achieved using entangling gates whose rotation angles depend on combinations of input features.

A common structure involves layers of single-qubit rotations and multi-qubit entangling gates. For example, a second-order polynomial feature map might use a circuit structure like this:

1. Initial Layer: Apply Hadamard gates $H$ to all qubits to create a superposition: $H^{\otimes n} |0\rangle^{\otimes n}$.
2. Data Encoding (Linear Terms): Apply single-qubit rotations dependent on individual features, e.g., $R_Z(f_1(x_i))$ on qubit $i$. Here, $f_1$ could be a simple scaling function, like $f_1(x_i) = 2 x_i$.
3. Entangling Layer (Polynomial Terms): Apply two-qubit entangling gates, such as controlled-phase gates or $ZZ$-interaction gates, between pairs of qubits $(i, j)$. The important part is that the angle of rotation for these entanglers depends on a function of the corresponding input features, e.g., $R_{ZZ}(f_2(x_i, x_j))$ acting on qubits $i$ and $j$. A popular choice for $f_2$ that introduces second-order interactions is $f_2(x_i, x_j) = (\pi - x_i)(\pi - x_j)$. This specific form arises in some standard library implementations.
4. Repetitions: Steps 2 and 3 can be repeated multiple times (often called "layers" or "reps") to potentially increase the complexity and expressivity of the feature map.

The resulting quantum state $|\phi(x)\rangle$ lives in the $2^n$-dimensional Hilbert space. The inner product between two such states, $\langle\phi(x')|\phi(x)\rangle$, defines the quantum kernel $k(x, x')$. Because the circuit $U(x)$ includes entangling operations controlled by products of features (like $x_i x_j$ embedded within $f_2(x_i, x_j)$), the resulting kernel $k(x, x')$ will contain polynomial terms of the input features $x$ and $x'$.

For instance, using the $f_2(x_i, x_j) = (\pi - x_i)(\pi - x_j)$ interaction within a $ZZ$ rotation effectively implements an evolution under an operator proportional to $(\pi - x_i)(\pi - x_j) Z_i Z_j$. When calculating the kernel $\langle\phi(x')|\phi(x)\rangle$, terms involving products like $x_i x_j x'_i x'_j$ can emerge, characteristic of a polynomial kernel.

Mathematical Structure and Kernels

Let's consider a simple two-qubit example ($n=2$) with data $x = (x_1, x_2)$. A circuit structure involving $H^{\otimes 2}$, then $R_Z(2x_1)$ on qubit 1 and $R_Z(2x_2)$ on qubit 2, followed by an entangling gate like $e^{-i \theta Z_1 Z_2}$ where $\theta = (\pi - x_1)(\pi - x_2)$, would generate a state $|\phi(x)\rangle$.

The kernel element between $x$ and $x'$ is $k(x, x') = |\langle\phi(x')|\phi(x)\rangle|^2$. Expanding the circuit operations $U(x) = e^{-i \theta Z_1 Z_2} R_Z(2x_2) R_Z(2x_1) H^{\otimes 2}$ and $U(x') = e^{-i \theta' Z_1 Z_2} R_Z(2x'_2) R_Z(2x'_1) H^{\otimes 2}$ with $\theta' = (\pi - x'_1)(\pi - x'_2)$, the calculation of $\langle 00 | U^\dagger(x') U(x) | 00 \rangle$ will involve terms dependent on differences like $(2x_1 - 2x'_1)$ and sums/differences of the interaction terms $\theta, \theta'$. This naturally leads to a kernel function $k(x, x')$ that is polynomial in $x_1, x_2, x'_1, x'_2$.

Specifically, feature maps involving $k$-local interactions (gates acting on $k$ qubits) whose parameters depend on products of up to $k$ features can generate kernels related to degree-$k$ polynomials.

Advantages

• Capturing Non-linearity: The primary advantage is the ability to model non-linear relationships in the data directly through the quantum feature space geometry, potentially leading to better performance on complex classification or regression tasks compared to linear feature maps.
• Hilbert Space Richness: Higher-order interactions can explore more complex entanglement structures within the high-dimensional Hilbert space, offering potentially richer feature representations than classical polynomial kernels of the same degree, although this is an active area of research.

However, there are important considerations:

• Circuit Depth and Qubits: Implementing higher-order interactions often requires deeper circuits or more qubits (if auxiliary qubits are used), increasing susceptibility to noise and decoherence on near-term devices.
• Kernel Concentration: As the number of qubits or circuit depth increases, the resulting kernel matrix might suffer from concentration effects (kernel values becoming exponentially close to each other), potentially hindering the training of kernel-based methods like QSVM. We will examine this phenomenon in detail in Chapter 3.
• Choice of Interaction: The specific choice of the entangling interaction (e.g., $ZZ$, $XX$, controlled gates) and the functional dependence on data features (e.g., $(\pi - x_i)(\pi - x_j)$, $x_i x_j$) significantly impacts the resulting kernel and its properties. Careful design and experimentation are often needed.

Example Circuit Visualization

The following diagram illustrates the structure of a two-layer ($d=2$) second-order polynomial feature map for $n$ qubits and a feature vector $x$.

A representation of a multi-layer quantum feature map designed to introduce polynomial interactions. Each layer applies data-dependent single-qubit rotations ($R_Z$) and multi-qubit entangling interactions ($R_{Z...Z}$) whose parameters $f_1, f_2$ are functions of the input features $x$.

In summary, higher-order polynomial quantum feature maps extend basic encoding strategies by incorporating multi-feature interactions via entangling gates. This allows the quantum state $|\phi(x)\rangle$ to encode non-linear relationships present in the classical data $x$, potentially leading to more expressive feature spaces and improved performance for QML algorithms designed to leverage quantum kernels. The design of these maps involves trade-offs between expressivity, circuit complexity, and resource requirements, which are important considerations for practical implementations.