Attributed-graphs kernel implementation using local detuning of neutral-atoms Rydberg Hamiltonian

1. Problem Statement

Graph-structured data is ubiquitous in fields like chemistry and social networks, but their non-Euclidean nature makes them difficult to process with standard vector-space machine learning methods. While classical graph kernels (e.g., Weisfeiler-Lehman, Random Walk) offer tractable similarity measures, they often struggle with attributed graphs (graphs where nodes and edges have specific labels or features) and can become computationally prohibitive for large datasets.

Recent quantum approaches have shown promise in computing graph kernels via quantum evolution, but existing implementations (specifically the Quantum Evolution Kernel or QEK) have largely focused on unattributed graphs. They typically encode only the graph topology (edges) into the quantum system, ignoring node attributes (e.g., atom types in molecules). Furthermore, most quantum kernels rely on global observables, potentially missing local structural nuances.

The core challenges addressed are:

1. How to effectively embed node attributes (features) into neutral-atom quantum processors.
2. How to design quantum kernels that leverage local observables to capture fine-grained graph structures.
3. How to combine information from multiple time steps to enhance kernel expressiveness without sacrificing performance.

2. Methodology

The authors propose a framework extending the Quantum Feature Kernel paradigm using neutral-atom Quantum Processing Units (QPUs).

A. Graph Embedding via Rydberg Hamiltonian

The method utilizes a neutral-atom Rydberg Hamiltonian to encode graph information:
$$\hat{H}(J, \Omega, \delta) = \frac{1}{2} \sum'_{i,j} J_{ij}\hat{n}_i\hat{n}_j + \hbar \sum_{i=1}^N \left( \frac{\Omega}{2}\hat{\sigma}^x_i - \delta_i\hat{n}_i \right)$$

• Edge Encoding: The coupling strength $J_{ij}$ is determined by the distance between atoms. Connected nodes (edges) are placed at a nearest-neighbor distance ($r_{NN}$) to induce strong coupling, while non-connected nodes are placed further apart to minimize coupling. This effectively maps the graph topology to a unit-disk graph.
• Node Feature Encoding (Novelty): To handle attributed graphs, the authors introduce local detuning ($\delta_i$). Instead of a global detuning (where all $\delta_i$ are equal), they map node attributes (specifically atomic masses in molecular datasets) to the local detuning field:
  $$\delta^G_i = \delta_0 \left( 1 - \frac{m_C}{m_i} \right)$$
  where $m_i$ is the mass of atom $i$ and $m_C$ is the mass of Carbon. This ensures that different atom types (e.g., Oxygen vs. Carbon) evolve differently under the Hamiltonian, encoding node features into the quantum state dynamics.

B. Quantum Feature Extraction

The system evolves from an initial state $|0\rangle$ under the Hamiltonian for a time $t$. The authors extract three types of observables as quantum features:

1. Excitation Probability ($P_k$): Probability of having $k$ excitations (global observable).
2. Site Occupation ($n_i$): Probability of atom $i$ being excited.
3. Correlation Matrix ($C_{ij}$): Joint probability of atoms $i$ and $j$ being excited (local observable).

C. Kernel Construction

Two distinct quantum kernels are proposed and compared:

1. Quantum Evolution Kernel (QEK):

   • Based on the global excitation probability distribution vector $P^G$.
   • Uses the Jensen-Shannon divergence to compute similarity.
   • Extension: The authors extend QEK to use the local-detuning Hamiltonian ($\hat{H}^G_{loc}$) to incorporate node features, denoted as $\kappa^{loc}_{QEK}$.

2. Generalized-Distance Quantum-Correlation (GDQC) Kernel:

   • Inspired by the classical Generalized-Distance Weisfeiler-Lehman (GD-WL) kernel.
   • Based on local observables (the correlation matrix $C_{ij}$) combined with graph distance ($d_G$).
   • Mechanism: It constructs a feature vector by binning pairs of nodes based on two criteria: their graph distance and their quantum correlation value. This creates a high-dimensional feature vector $\chi$ representing the joint distribution of distances and correlations.
   • Advantage: It naturally captures local structural properties and is theoretically proven to be at least as expressive as the GD-WL kernel.

D. Kernel Pooling

To leverage information across the entire time evolution, the authors employ pooling operations on kernels computed at multiple time steps ($t_1, \dots, t_N$):

• Sum Pooling: Linear combination of kernels.
• Product Pooling: Pointwise product of kernels.
  This allows the model to aggregate features from different dynamical regimes, theoretically increasing expressiveness.

3. Key Contributions

1. Node-Feature Embedding Scheme: The first implementation of a quantum feature kernel for attributed graphs on neutral-atom hardware. By mapping atomic masses to local detuning fields, they demonstrate that node features significantly enhance the distinguishability of graphs.
2. GDQC Kernel Proposal: Introduction of a new kernel based on local observables (correlation matrices) and graph distances. Theoretical analysis proves it satisfies kernel properties (positive semi-definiteness) and offers higher expressiveness than global-observable-only approaches.
3. Pooling Strategy: Demonstration that combining kernels from multiple time steps via pooling significantly boosts performance, allowing quantum kernels to surpass classical baselines.
4. Theoretical Expressiveness Proofs: Rigorous proofs showing that:
   • Local detuning makes the kernel strictly more expressive for attributed graphs than global detuning.
   • The GDQC kernel is at least as expressive as the classical GD-WL kernel.
   • Pooling subsets of kernels never reduces expressiveness.

4. Results

The methods were evaluated on two standard molecular benchmark datasets: MUTAG (mutagenicity prediction) and PTC_FM (carcinogenicity prediction).

• Performance vs. Classical Baselines:

  • Both QEK and GDQC kernels performed competitively with state-of-the-art classical kernels (e.g., Random Walk, Weisfeiler-Lehman Optimal Assignment).
  • Without Pooling: Quantum kernels matched or slightly exceeded classical baselines.
  • With Pooling: The performance gap widened. Pooled quantum kernels (specifically $\text{GDQC}^{loc}_{\times}$ and $\text{QEK}^{loc}_{+}$) surpassed the best classical baselines on both datasets.
    • On MUTAG, the best pooled GDQC achieved an F1 score of 90.83%, outperforming the best classical kernel (86.88%).
    • On PTC_FM, the best pooled QEK achieved 69.55%, outperforming the best classical kernel (63.40%).

• Impact of Node Features:

  • Kernels using local detuning (encoding node features) consistently outperformed those using global detuning (ignoring node features).
  • This confirms that embedding node attributes into the Hamiltonian is crucial for handling attributed graphs effectively.

• Expressiveness Analysis:

  • Analysis of the Gram matrix rank showed that local detuning and finer binning (in GDQC) increase the effective dimensionality of the feature space, allowing better separation of non-isomorphic graphs.
  • However, the authors note that higher rank (distinguishability) does not always linearly correlate with higher F1 scores, suggesting a trade-off between expressiveness and generalization.

5. Significance and Conclusion

This work represents a significant step forward in Quantum-Enhanced Graph Machine Learning (QML):

• Bridging the Gap: It successfully transitions quantum graph kernels from unattributed topological analysis to attributed graph analysis, which is essential for real-world applications like drug discovery (where atom types matter).
• Hardware Efficiency: The approach leverages the native capabilities of neutral-atom processors (Rydberg blockade, local addressing) to encode complex graph data without requiring deep quantum circuits or error correction.
• Methodological Innovation: The combination of local observables (GDQC) and temporal pooling provides a robust recipe for maximizing the information extracted from quantum simulations.
• Practical Impact: The results demonstrate that quantum feature kernels can not only match but surpass classical algorithms on specific graph classification tasks when properly engineered with node features and pooling strategies.

The paper concludes that while asymptotic speedups are not yet claimed (due to simulation overheads), the empirical performance gains and the ability to handle attributed graphs make this a viable and promising direction for near-term quantum machine learning applications.