🤖 machine learning

Quantum Evolution Kernel for Node-Attributed Graphs

This paper proposes a novel quantum evolution kernel for node-attributed graphs that utilizes three-level quantum state encoding and Wasserstein distance to achieve higher accuracy in digit recognition tasks compared to classical Jensen-Shannon distance-based methods, all simulated on neutral-atom quantum computers using Pasqal's Pulser library.

Original authors: Manuel Padovani, Alessandra Di Pierro, Claudia Daffara

Published 2026-10-28

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Manuel Padovani, Alessandra Di Pierro, Claudia Daffara

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Computers have long been experts at recognizing patterns in data, from sorting photos of cats to reading handwritten notes. For decades, the most successful tools for this task have relied on classical mathematics, treating information as fixed lists of numbers or simple connections. However, a new frontier is opening in the field of machine learning, where scientists are beginning to use the strange laws of quantum mechanics to process information in ways that were previously impossible. In this realm, data is not just calculated; it is evolved. Instead of simply crunching numbers, researchers can guide a system through a series of physical changes, allowing the data to interact with itself in a way that reveals hidden relationships. This approach is particularly promising for analyzing complex shapes and networks, known as graphs, which appear everywhere from social networks to chemical molecules. The challenge has been finding a way to feed these complex, multi-faceted graphs into quantum machines without losing the subtle details that make them unique.

A team of researchers at the University of Verona has taken a significant step toward solving this problem by developing a new method to translate graphs into the language of neutral-atom quantum computers. These machines use individual atoms, held in place by lasers, to represent data points. The researchers focused on a specific type of graph where each point, or node, carries its own set of characteristics, such as the color of a pixel in a drawing or the chemical properties of an atom in a molecule. Their goal was to create a system that could not only see the shape of the graph but also understand the unique features attached to each part of it. To do this, they designed a process that maps the structure of a graph onto the physical positions of atoms and then encodes the specific details of each node into the internal energy states of those atoms.

The core of their innovation lies in how they handle these internal states. Traditional methods often treat atoms as simple switches that are either on or off. The Verona team, however, utilized a more complex three-level system. They used lasers to gently nudge the atoms into a middle state, distinct from both their resting state and their highly excited state. This allowed them to encode two different pieces of information for every single node simultaneously. One part of the system captured the overall shape of the graph by arranging the atoms in a specific pattern, while the other part used the internal energy levels to store the unique features of each node. This separation meant that the computer could process the structure and the details independently, preserving the richness of the original data.

To test their idea, the researchers turned to a classic problem: recognizing handwritten digits. They took images of numbers from a standard dataset and converted them into graphs, where every pixel became a node and the connections between them formed the lines of the digit. They then fed these graphs into a simulation of a neutral-atom quantum computer. The system evolved the atoms for a brief moment, allowing them to interact and entangle, before the researchers measured the final state. Instead of looking for a single answer, they analyzed the statistical patterns of the results, creating a unique "fingerprint" for each digit. They then compared these fingerprints to see how similar or different the digits were from one another.

The researchers discovered that the way they measured the difference between these fingerprints mattered greatly. They tested several mathematical ways to compare the patterns, including methods that had been popular in previous studies. They found that a specific approach, known as the Wasserstein distance, was far superior for their data. This method is particularly good at measuring how much "work" it would take to transform one pattern into another, capturing the subtle geometric shifts that other methods missed. When they used this distance measure, their quantum system achieved a higher average accuracy in recognizing the digits than the older, more common methods.

The study also highlighted the importance of the extra information attached to the nodes. When the researchers removed the specific features of the nodes and relied only on the shape of the graph, the system's performance dropped. This confirmed that their method of encoding local details into the atoms' internal states was essential for the task. While the quantum system did not yet outperform the most advanced classical computer programs designed for this specific job, it performed on par with some of the best traditional graph-matching tools. This is a notable result because the quantum system was running on a simulation with strict limits on the number of atoms it could handle, yet it still managed to extract meaningful patterns from the data.

The researchers were careful to note that their work was a prototype. The entire process was simulated on a classical computer to mimic the behavior of a real quantum device, which means the results are a proof of concept rather than a demonstration of a finished product. They also found that the system was sensitive to the timing of the laser pulses; if the atoms were allowed to evolve for too long, the signal became noisy and the accuracy suffered. By finding the precise moment to stop the evolution, they maximized the clarity of the information. The study suggests that as real quantum hardware improves and can handle larger numbers of atoms, this approach could become a powerful tool for analyzing complex data structures.

Ultimately, this work demonstrates that it is possible to map the rich, multi-layered information of real-world graphs onto the delicate states of quantum atoms. By combining the physical arrangement of atoms with their internal energy levels, and by using a smart way to compare the resulting patterns, the researchers have shown a viable path forward for quantum graph learning. The findings suggest that in the future, these machines could offer a new way to understand complex systems, from recognizing handwriting to predicting the behavior of new materials, by seeing the data not just as numbers, but as evolving physical forms.

Technical Summary: Quantum Evolution Kernel for Node-Attributed Graphs

Problem Statement

Graph machine learning is a critical field for representing real-world problems, yet classical methods face significant limitations. Traditional graph kernels (e.g., Weisfeiler-Lehman) often ignore continuous node features, while Graph Convolutional Networks (GCNs) are theoretically bounded by the 1-WL isomorphism test, suffer from over-smoothing, and incur high computational costs as graph size increases. Furthermore, incorporating multiple continuous node attributes into analog quantum graph kernels remains a largely unexplored challenge. This paper addresses the need for a quantum paradigm capable of encoding both graph structure and continuous node-level features on neutral-atom quantum processors, specifically targeting the low-data regime where quantum kernels have shown promise.

Methodology

The proposed approach extends the Quantum Evolution Kernel (QEK) framework to handle node-attributed graphs using Pasqal's neutral-atom quantum processors. The methodology involves three primary stages:

1. Physical Encoding and Hamiltonian

The system utilizes neutral atoms with three relevant states: two low-energy hyperfine ground states ( $|g\rangle$ and $|h\rangle$ ) and a high-energy Rydberg state ( $|r\rangle$ ).

Graph Structure: Encoded via the spatial positioning of atoms. Connected nodes are placed within a Rydberg blockade radius ( $R_b$ ) to enable interactions via the van der Waals force ( $1/R^6$ ), while unconnected nodes are placed beyond this radius.
Node Features: Unlike previous works that used only Rydberg lasers, this method introduces local Raman laser pulses to couple the $|g\rangle$ and $|h\rangle$ states. This creates a three-level (qutrit) system per atom. Node feature vectors are normalized and mapped to rotation angles ( $\theta_1, \theta_2$ ) on the Bloch sphere, effectively modulating the population transfer between $|g\rangle$ and $|h\rangle$ .
Evolution: The system evolves under a Hamiltonian comprising local rotations ( $U_{local}$ ) and global Rydberg interactions ( $U_{int}$ ). The final state $|\Psi(t)\rangle$ is a result of these successive layers.

2. Measurement and Distribution Extraction

Since hardware cannot directly distinguish all three states, measurements are performed in the ground-Rydberg basis (bit 0 for $|g\rangle$ or $|h\rangle$ , bit 1 for $|r\rangle$ ).

Occupation Distribution: Derived from the Hamming weight of bit strings (fraction of excited atoms).
Correlation Distribution: Derived from two-point correlations $\langle Z_i Z_j \rangle - \langle Z_i \rangle \langle Z_j \rangle$ .
Scale Invariance: These distributions are aggregated to create size-invariant graph representations.

3. Kernel Construction

The paper defines a quantum kernel based on the distance between probability distributions derived from the measurements.

Distance Metric: The authors employ the Wasserstein distance ( $W_1$ ) (Earth Mover's Distance) rather than the commonly used Jensen-Shannon (JS) distance. $W_1$ preserves geometric information and avoids discretization losses associated with binning, though it has higher time complexity.
Kernel Formulation: The kernel is defined as $K(P, Q) = \exp(-\gamma D(P, Q))$ . Two aggregation strategies are tested: a weighted sum of individual kernels and a product of summed distances.
Classification: The resulting kernel is fed into a Support Vector Classifier (SVC) with a one-vs-one strategy for multi-class classification.

Experimental Setup

Dataset: A subset of the MNIST handwritten digit dataset was converted into graphs. Images underwent binarization, skeletonization, and graph refinement (merging close nodes, removing collinear nodes).
Constraints: Due to simulation limits using Pasqal's Pulser library, graphs were filtered to have $|V| \le 9$ nodes.
Features: Four node-level features were encoded: pixel coordinates (scaled), deviation angle of consecutive edges, and bisector direction.
Baselines: The method was compared against classical Weisfeiler-Lehman (WL) graph kernels (with various feature configurations) and a Graph Convolutional Network (GCN).

Key Results

Distance Metric Efficacy: The Wasserstein distance achieved the highest mean accuracy across all training set sizes compared to Jensen-Shannon, Hellinger, and L2 distances. The JS distance performed slightly worse, and performance degraded when increasing bin counts, suggesting $W_1$ 's ability to handle continuous distributions without binning is superior for this task.
Feature Importance: The quantum kernel with node-level features outperformed the version without them, confirming that local information enhances classification.
Comparison with Classical Baselines:
- The GCN achieved the highest overall accuracy, as expected for deep learning models.
- The Quantum Kernel (using Wasserstein) performed comparably to the positional-only WL kernel and outperformed the angle-only and featureless WL kernels.
- However, the quantum kernel did not surpass the combined positional-angle WL kernel or the GCN in mean accuracy.

Significance and Claims

The paper claims to demonstrate the architectural feasibility of encoding multi-attribute continuous features on analog neutral-atom hardware. Its primary contributions are:

Novel Encoding: Introducing a three-level system per atom via Raman lasers to separate node feature encoding from topological encoding, enriching the local Hilbert space.
Metric Selection: Establishing that the Wasserstein distance is more effective than the Jensen-Shannon metric for graph kernels based on quantum measurement distributions in this context.
Prototype Validation: Showing that even with a simple circuit and short evolution times, the method can extract correlation-based information useful for classification tasks.

The authors remain modest regarding the current performance, noting that the simple circuit design and short evolution times prevented the method from surpassing state-of-the-art classical kernels or GCNs. They posit that more refined designs with elaborate encodings and longer evolution times could improve performance. The work serves as a baseline for future large-scale implementations, highlighting that while the encoding scales linearly with graph size on real hardware, managing classical post-processing costs for correlation matrices remains a critical challenge for scalability.