Quantum Evolution Kernel for Node-Attributed Graphs

AI summary

Overview

Research area: Quantum machine learning, specifically quantum graph kernels for node-attributed graphs on neutral-atom quantum processors, with an application to handwritten digit recognition.

Technical level: Advanced.

Scope: The paper proposes and simulates a three-level (qutrit) node-feature encoding for Pasqal’s quantum evolution kernel, then compares Wasserstein-distance kernels against Jensen-Shannon, Hellinger, L2, and classical graph baselines on a graph-transformed MNIST dataset.

What This Paper Is About

The paper addresses how to encode both graph structure and continuous node attributes onto neutral-atom quantum hardware in a way that supports graph classification. It extends Pasqal’s Quantum Evolution Kernel by using local Raman laser pulses to store node features in two hyperfine ground states, while Rydberg interactions encode graph topology. The goal is to test whether this richer encoding and a Wasserstein-based kernel can improve digit recognition in a low-data regime compared with classical graph kernels and a graph convolutional network.

Key Contributions

1. A node-level feature encoding scheme for neutral-atom quantum computers that uses three states per atom: the two hyperfine ground states (|g\rangle) and (|h\rangle), plus the Rydberg state (|r\rangle). Node features are written into the (|g\rangle)-(|h\rangle) subspace with local Raman rotations, separately from the graph structure encoded by atom positions and Rydberg interactions.

2. An extension of Pasqal’s Quantum Evolution Kernel that handles multiple continuous node attributes. Since one qubit-like encoding captures at most two real parameters, a graph with (d) node features yields (d/2) distinct quantum states and corresponding measurement distributions.

3. A distribution-based quantum kernel built from excitation and correlation observables, using the Wasserstein distance (W_1) instead of the more common Jensen-Shannon distance, with two aggregation strategies: a weighted sum of per-distribution kernels and a product-form kernel that sums distances before exponentiating.

4. An experimental prototype on graph-transformed MNIST, simulated with Pasqal’s Pulser library, comparing the quantum kernel against Weisfeiler-Lehman kernels and a GCN, including ablation of node-level features and comparison of four distance metrics.

Main Findings

• Wasserstein performs best among tested distances: The Wasserstein-based quantum kernel achieved the highest mean accuracy for all training sizes tested. The sum and product aggregation strategies produced comparable results, so the sum aggregation was used for the classical comparison.

• Jensen-Shannon is slightly worse: The Jensen-Shannon distance performed slightly worse than Wasserstein. Increasing the number of bins to 30, far higher than the typical number of nodes in the graphs, caused a performance drop compared with the 10-bin version.

• Hellinger and L2 are unsuitable here: These distances performed poorly, with accuracy even decreasing as the training set size increased, suggesting they do not capture the separation between the measured distributions in this setting.

• Node features help: The Wasserstein kernel without node-level features outperformed Hellinger and L2 but performed worse than all cases that included local features, supporting the usefulness of the simple feature encoding.

• Classical baselines remain stronger overall: The GCN achieved the highest mean accuracy, as expected. Among Weisfeiler-Lehman kernels, the combined positional-angle variant performed best and slightly exceeded the mean accuracy of the quantum kernel. The quantum kernel matched the positional-only Weisfeiler-Lehman variant and outperformed both the angle-only and featureless Weisfeiler-Lehman kernels.

• Optimal evolution time: Bayesian optimization selected (t = 240.1) ns for the evolution time. Small (t) did not generate sufficient entanglement, while large (t) caused long excitations and oscillations between entangled states, leading to a sharp drop in F1-score.

• Dataset filtering retains about 80%: After enforcing graph-size and embedding-quality constraints, approximately 80% of the dataset was retained: 48,018 of 60,000 training samples and 8,100 of 10,000 test samples. Simulation constraints meant only a small subset was used for training and evaluation.

Methodology in Plain English

The researchers turn each MNIST digit image into a graph: they binarize the image, skeletonize the strokes to one pixel wide, place a node at each pixel, link nearby pixels, merge close nodes, and remove collinear nodes. Four node features are computed: scaled pixel coordinates, the deviation angle between consecutive edges, and the direction of the bisector of those edges.

Each graph is embedded in a neutral-atom register using a force-directed spring layout, subject to device constraints such as a minimum interatomic distance of 4 μm, a graph size (|V| \leq 9), an embedding error MSE (\leq 1.5), and a maximum distance from the center of 50.0 μm. Connected nodes are placed within the Rydberg blockade radius so that the interaction Hamiltonian naturally encodes the graph topology.

Node features are encoded separately with local Raman pulses, which rotate each atom’s (|g\rangle)-(|h\rangle) state by angles derived from the feature values. The features are rescaled to ([0,\pi/2]) so that population is only partially transferred from (|g\rangle) to (|h\rangle); complete transfer would remove a node from the Rydberg laser coupling and could destroy topology information. The Rydberg laser then generates the interaction-driven evolution over a short time (t).

Measurements assign bit 0 to either low-energy state and bit 1 to the Rydberg state, since the hardware cannot directly distinguish all three states. From 500 shots per circuit, the authors build two distribution types for each encoded feature pair: an excitation distribution based on the fraction of atoms in the Rydberg state, and a correlation distribution based on (\langle Z_i Z_j\rangle - \langle Z_i\rangle\langle Z_j\rangle). Both are designed to be size-invariant.

A kernel is defined as (\exp(-\gamma D(P,Q))), where (D) is a distribution distance and (\gamma) is a scale parameter. Because the distributions are one-dimensional, Wasserstein-1 is conditionally negative definite, which guarantees a positive semi-definite kernel. Multiple per-feature kernels are combined by a weighted sum or product. The resulting kernel is used in a support vector classifier with a one-vs-one strategy for multi-class classification, with (\gamma), the regularization term (C), and the weights (\omega_k) tuned by nested cross-validation.

The quantum simulation uses Pasqal’s Pulser library with the pulser.DigitalAnalogDevice virtual device. Comparisons include Weisfeiler-Lehman graph kernels implemented with GraKeL and a GCN implemented with PyTorch Geometric. Models are evaluated across different training set sizes with five random seeds and a fixed balanced test set of 15 samples per class. Edge-feature encoding via interatomic distances is described but not experimentally evaluated.

Why This Matters

The work tests whether neutral-atom quantum hardware can represent node-attributed graphs without collapsing structural and feature information into a single two-level encoding. It provides a concrete, simulated baseline for multi-attribute continuous encoding on analog quantum devices and shows that the choice of distance metric materially affects kernel performance.

Real-world applications suggested by the paper’s framing include:

• Handwritten character and digit recognition, including document digitization and OCR pipelines.
• Molecular property prediction, where atoms are nodes and continuous chemical or geometric attributes are node features.
• Graph classification tasks where node-level measurements or coordinates matter alongside connectivity.
• Low-data classification settings, where quantum kernel methods have shown promise.

Industry relevance centers on neutral-atom quantum computing vendors and users, especially Pasqal’s ecosystem, as well as teams exploring quantum kernels for graph-structured data in the NISQ era. The paper is explicit that demonstrating a strict computational or learning advantage over classical graph methods remains an open challenge.

Future Directions

• Test more refined circuit designs with multiple, more elaborate encoding layers and longer evolution times, which the authors suggest could improve performance beyond the single short evolution layer used here.
• Experimentally evaluate edge-feature encoding through interatomic distances, which is described in the method but not assessed in the reported experiments.
• Address scalability: the paper notes that encoding time scales as (O(|V|)), excitation estimation requires (O(1/\epsilon^2)) shots, correlation estimation requires (O(\log |V|/\epsilon^2)) shots, and classical post-processing of the correlation matrix costs (O(|V|^2)).
• Investigate whether the optimized weights (\omega_k) can be interpreted as feature-relevance scores, potentially guiding which graph features are most useful for classification.
• Establish whether the approach can demonstrate a strict computational or learning advantage over classical graph methods, which the authors identify as an open challenge.

Target Audience

This paper is best suited for quantum machine learning researchers, neutral-atom quantum computing practitioners, and graph machine learning researchers interested in quantum kernels for attributed graphs. It is also relevant to computational scientists working on graph-based character recognition or molecular property prediction who want a technically detailed but prototype-scale assessment of analog quantum graph embeddings. Readers need familiarity with quantum states, Hamiltonians, and kernel methods to follow the methodology comfortably.

Authors’ abstract

We present a novel approach to embed node-attributed graphs onto neutral-atom quantum computers, and propose an application to digit recognition. Our approach extends PASQAL's quantum evolution kernel (QEK) by introducing a node-level feature encoding based on three-level quantum states. To this purpose, we present a prototype showing how the resulting embedding can be leveraged to extract correlation-based information for classification tasks. The entire quantum process is simulated using Pasqal's Pulser library, which inevitably imposes constraints on the size of the experimental datasets. We compare our method with classical baselines to evaluate its potential. We show that, for the digit recognition task, our method achieves a higher mean accuracy than the more commonly used Jensen-Shannon distance-based methods by utilizing the Wasserstein distance.