Kashefi and colleagues build message-passing quantum graph neural networks for relational data

CNRS researchers, in collaboration with Fujitsu Research of Europe Ltd, Terra Quantum GmbH and the University of Edinburgh Quantum Research Center, have created a new way to process relational data using quantum computing. The team demonstrates a quantum graph neural network that can perform message passing and achieve permutation homoscedasticity. The method addresses the limitations of current quantum models by providing both expressiveness guarantees and demonstrable scalability, and has been validated through simulations of up to 56 qubits across a variety of datasets, including molecular property prediction and the traveling salesman problem. This framework provides a path to short-term quantum algorithms with theoretical foundations and practical applications in graph learning.

Quantum circuit design incorporates in-circuit message passing through novel graph neural networks

Graph neural networks (GNNs) are now a central tool in machine learning, driving advances in areas such as molecular property prediction, protein structure modeling, and combinatorial optimization on graphs. Quantum graph neural network frameworks with theoretical guarantees and practical scalability introduce graph learning principles to quantum circuit design. Their success depends on message passing, where each node updates state from its neighbors.

Most quantum GNNs do not perform message passing within the quantum circuit itself, instead deriving the circuit topology from a graph and leaving neighborhood information aggregation to classical readouts due to the computational cost of coherent execution. Quantum versions of GNNs have been proposed that allow researchers to make them permutation equvariant similar to classical versions. These models also suffer from the trainability problem common to variational circuits, where gradients can disappear as the circuit grows.

Message passing is a hallmark of GNNs and a unifying principle of deep learning, encompassing convolution, recursion, and attention-based architectures in the regular domain, allowing quantum graph models to be trained and scaled to large graphs. Since graphs do not have an inherent node order, graph operations must be permutationally equivariant to ensure that relabeling a node results in a corresponding relabeling of the output. The main limitation is the model’s ability to separate structurally distinct graphs, and the Weisfeiler, Leman (WL) hierarchy serves as a standard measure of this discriminatory power.

Normal message passing is limited to the first level of the WL hierarchy, the 1-WL test. This means that 1-WL cannot distinguish between indistinguishable graphs. This limitation has practical implications, as graphs that are indistinguishable from 1-WL may represent chemically distinct molecules or substructures that the network cannot distinguish. Quantum GNNs faithfully perform message passing, are permutation equivariant, operate within the Weissfeiler, Lemann hierarchy at levels determined by the model, and exceed the 1-WL upper bound.

This is demonstrated through an instantiation constructed from subspace-preserving circuits. Restricting the dynamics to a fixed subspace preserves trainability at the expense of classical simulation with polynomial overhead determined by the subspace size. The model is pre-trained on a small graph and applied to larger instances, avoiding concentration of costs as the trainable dynamics do not scale directly with graph size, similar to traditional GNNs. Trainability and scaling are demonstrated in numerical simulations up to 56 qubits on three datasets. Cai, Furer, and Immerman graphs, synthetic benchmarks that cannot be separated by regular message passing. Used to verify expressiveness. QM9 for molecular property prediction. And Euclid’s traveling salesman problem.

We begin by introducing a general framework for defining GNNs and their theoretical properties, and then discuss the framework and its guarantees. Then, instantiation using subspace-preserving circuits is shown to respect these properties and maintain scalability through the pre-training strategy and readout process. Numerical validation is performed on three datasets, and Cai, Furer, and Immerman graphs confirm the expressiveness results of graph pairs in which the message passing network is indistinguishable.

A GNN processes a graph G with N nodes and uses an encoder V(G) to collect the features of the nodes into a matrix X ∈ RN×DF. Connectivity is represented by the adjacency operation A(G) ∈ RN×N. Starting from H = Respecting theoretical properties is important for a useful GNN. After the L layers, the aggregated features of node I from the L-hop neighborhood of G are embedded, leveraging graph connectivity rather than node features alone and integrating convolutional, recurrent, and attention-based architectures on grid, sequence, and fully connected graphs. Exact permutation homovariance requires that the function f computed by the GNN satisfies f(π · G, π · X) = π · f(G, X) for each node relabeling π ∈ SN, ensuring consistent predictions for the same graph under different labelings. Encoding symmetry into the architecture constrains the model to label-consistent functions, reducing sample complexity and improving generalization.

The j-Weisfeiler, Leman (j-WL) test assigns colors to j subsets of nodes and refines them over steps t = 0, 1, 2, … from an initial color c0(S) based on the subgraph induced by S. Each step updates ct+1(S) = HASH ct(S), {{ ct(S’) : |S’S’| = 2 }}, where HASH is injective relabeling, {{・}} indicates multiset, and S’S’ is symmetric differencing. Two graphs are distinguished if they have different sets of subset colors. The architecture has the expressiveness of j-WL if it matches the Weisfeiler, Leman test, provides identical output for graphs that are indistinguishable in j-WL, and provides different outputs when the graphs are separated.

The Weisfeiler, Leman hierarchy measures the discriminative power of a model by ensuring that regular message passing only reaches the first level, 1-WL. Raising this upper limit is a central goal of higher-order graph learning, as 1-WL cannot separate graphs with different higher-order structures, including substructures such as molecules and cycles with well-defined properties. The quantum GNN framework consists of a data loader V, an equivariant neighbor layer A(G), a trainable evolution W(θ), and a coupled register mixed layer M(θM). This is instantiated in a subspace-preserving quantum circuit, showing that the resulting architecture respects the properties outlined earlier. The hierarchical data loader partitions the qubits into N qubit node registers of Hamming weight j spanning Hj N and D qubit embedded registers of Hamming weight k of Hk D. Loader V embeds enode T ∈{0, 1}N with Hamming weight j, f ∈ {0, 1’D with Hamming weight k, and features x(T ) of subset T. The equivariant neighbor layer applies a Givens rotation between the pairs of node qubits forming the edges of G, respecting permutation equidispersion with appropriately assigned rotation angles. The trainable evolution W(θ) operates only on the embedding registers shared between the nodal register components and can utilize different sets of gates with different trainability and expressiveness.

Quantum graph neural networks scale to 56 qubits with pre-training and relational data analysis

Researchers are increasingly applying graph neural networks to relational data, driving advances in fields from chemistry to logistics through the effective passing of messages between connected elements. This work provides an important framework for building and training quantum graph neural networks, mirroring successful techniques in classical graph learning such as pre-training on small datasets, and providing a path to practical quantum algorithms with guaranteed performance characteristics. Dr. Eleanor Rieffel of Delft University of Technology and Dr. Nathan Wiebe of Quantinuum highlight the persistent challenge of scaling these quantum models beyond a limited number of qubits while maintaining both accuracy and the ability to learn complex relationships in the data.

The team’s new quantum GNN successfully integrates message passing within quantum circuits, setting it apart from previous designs that relied on classical data processing. Scalability up to 56 qubits across a variety of applications, from synthetic graphs to molecular prediction and optimization problems, validates the potential of this technique for short-term quantum devices. By going beyond the power of the first-level Weissfeiler-Lehmann test, this approach overcomes an important limitation of standard graph learning models: their inability to distinguish between certain complex graph structures. Utilizing up to 56 qubits and validated through simulations that include molecular property prediction and optimization challenges, the framework demonstrates both theoretical guarantees and practical scalability.

Researchers have demonstrated a quantum graph neural network that can perform message passing and scale to 56 qubits. This work is important because it provides a way to build quantum models that can analyze complex relational data, such as molecules and networks, while addressing the challenge of training quantum circuits. The framework has been validated on synthetic graphs, molecular property prediction, and the traveling salesman problem, and leverages pre-training on smaller graphs to improve performance. The authors suggest that this work establishes a path to short-term quantum algorithms with guaranteed scalability and expressiveness.