Kashefi and Colleagues Build Message-Passing Quantum Graph Neural Network for Relational Data

Researchers at CNRS, in collaboration with Fujitsu Research of Europe Ltd, Terra Quantum GmbH, Quantum Research Centre, University of Edinburgh, have created a new method for processing relational data using quantum computing. The team demonstrate a quantum graph neural network capable of performing message passing and achieving permutation equivariance. The method addresses limitations in current quantum models by offering both expressivity guarantees and demonstrable scalability, validated through simulations of up to 56 qubits across diverse datasets including molecular property prediction and the travelling salesperson problem. The framework provides a path towards near-term quantum algorithms with theoretical foundations and practical application in graph learning.

Quantum circuit design incorporates in-circuit message passing via a novel graph neural network

Graph neural networks (GNNs) are now a central tool in machine learning, driving progress in areas such as molecular property prediction, protein structure modelling, and combinatorial optimisation on graphs. A quantum graph neural network framework with theoretical guarantees and practical scalability now brings the principles of graph learning into quantum circuit design. Their success relies on message passing, where each node updates its state from its neighbours.

Most quantum GNNs do not perform message passing within the quantum circuit itself, instead deriving circuit topology from the graph and leaving the aggregation of neighbour information to a classical readout, due to the computational expense of coherent execution. Quantum versions of GNNs have been proposed and researchers can make them permutation equivariant like their classical counterparts. These models also suffer from trainability issues common to variational circuits, where gradients can vanish as the circuit grows.

As message passing is the defining characteristic of a GNN and a unifying principle in deep learning, subsuming convolutional, recurrent, and attention-based architectures on regular domains, a quantum graph model can be trained and scaled to large graphs. Any graph operation must be permutation equivariant, ensuring that relabelling nodes results in a corresponding relabelling of the output, since a graph lacks intrinsic node ordering. A key limitation is a model’s ability to separate structurally distinct graphs, and the Weisfeiler, Leman (WL) hierarchy serves as the standard measure of this distinguishing power.

Ordinary message passing is limited to the first level of the WL hierarchy, the 1-WL test, meaning it cannot differentiate graphs that 1-WL cannot distinguish. This limitation has practical consequences, as graphs indistinguishable to 1-WL can represent chemically distinct molecules or substructures that the network cannot identify. A quantum GNN faithfully performs message passing, is permutation equivariant, and operates within the Weisfeiler, Leman hierarchy at a level determined by the model, exceeding the 1-WL ceiling.

This is demonstrated through an instantiation built from subspace-preserving circuits. Confining the dynamics to a fixed subspace maintains trainability, at the cost of a classical simulation with polynomial overhead determined by the subspace size. The model is pre-trained on small graphs and applied to larger instances, avoiding cost concentration as the trainable dynamics do not scale directly with graph size, similar to classical GNNs. Trainability and scaling are demonstrated in numerical simulations of up to 56 qubits on three datasets: Cai, Furer, Immerman graphs, synthetic benchmarks that ordinary message passing cannot separate, used to validate expressivity; QM9 for molecular property prediction; and the Euclidean travelling salesperson problem.

Beginning with an introduction to the general framework for defining GNNs and their theoretical properties, the framework and its guarantees are presented. The instantiation with subspace-preserving circuits is then shown to respect these properties and maintain scalability through the pre-training strategy and readout process. Numerical validation is performed on three datasets, with Cai, Furer, Immerman graphs confirming the expressivity result on graph pairs that no message-passing network can differentiate.

A GNN processes a graph G with N nodes, collecting node features into a matrix X ∈ RN×DF using an encoder V(G). Connectivity is represented by an adjacency operation A(G) ∈ RN×N. Message passing refines these features over L rounds, starting with H = X, and transforming H(l) into H(l+1) by alternating A(G) to aggregate neighbours, with a trainable evolution W(θ) ∈ RDF × DF acting on the feature space, followed by a nonlinearity σ. Respecting theoretical properties is important for useful GNNs. After L layers, it embeds node I’s aggregated features from its L-hop neighbourhood in G, exploiting graph connectivity rather than node features alone, and unifies convolutional, recurrent, and attention-based architectures on grids, sequences, and fully connected graphs. Exact permutation equivariance requires that the function f computed by a GNN satisfies f(π · G, π · X) = π · f(G, X) for every relabelling π ∈ SN of the nodes, ensuring consistent predictions for the same graph under different labelling. Encoding symmetry into the architecture restricts the model to label-consistent functions, lowering sample complexity and improving generalisation.

The j-Weisfeiler, Leman (j-WL) test assigns colours to j-subsets of nodes, refined over steps t = 0, 1, 2, … from an initial colour 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 an injective relabelling, {{·}} denotes a multiset, and S’S′ is the symmetric difference. Two graphs are distinguished when their multisets of subset colours differ. An architecture has j-WL expressivity when it matches the Weisfeiler, Leman test, providing identical outputs for graphs indistinguishable by j-WL and different outputs when they are separated.

The Weisfeiler, Leman hierarchy measures a model’s distinguishing power, with ordinary message passing reaching only the first level, 1-WL. Lifting this ceiling is a central aim of higher-order graph learning, as 1-WL cannot separate graphs differing in higher-order structure, including molecules with distinct properties and substructures such as cycles. The quantum GNN framework consists of a data loader V, an equivariant adjacency layer A(G), a trainable evolution W(θ), and a joint-register mixing layer M(θM). It is instantiated with subspace-preserving quantum circuits, demonstrating that the resulting architecture respects the properties outlined previously. The hierarchical data loader splits qubits into N-qubit node registers at Hamming weight j, spanning Hj N, and D-qubit embedding registers at Hamming weight k, in Hk D. The loader V prepares |x⟩= X T DF X f=1x(T ) f |enode T ⟩⊗|eembedding f ⟩, with enode T ∈{0, 1}N of Hamming weight j, eembedding f ∈ {0, 1’D of Hamming weight k, and x(T ) the features of subset T. The equivariant adjacency layer applies Givens rotations between node-qubit pairs forming edges in G, respecting permutation equivariance with appropriately assigned rotation angles. The trainable evolution W(θ) acts only on the embedding register, shared across node-register components, and can utilise various gate sets with differing trainability and expressivity.

Quantum graph neural networks scale to 56 qubits via 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 effective message passing between connected elements. This work delivers an important framework for building and training quantum graph neural networks, mirroring successful techniques from classical graph learning like pre-training on smaller datasets, offering a pathway towards practical quantum algorithms with guaranteed performance characteristics. Dr. Eleanor Rieffel of Delft University of Technology and Dr. Nathan Wiebe of Quantinuum highlight a persistent challenge: scaling these quantum models beyond a limited number of qubits while maintaining both accuracy and the ability to learn complex relationships within the data.

The team’s new quantum GNN successfully integrates message passing within a quantum circuit, a departure from previous designs relying on classical data processing. Scalability up to 56 qubits across diverse applications, from synthetic graphs to molecular prediction and optimisation problems, validates the potential of this method for near-term quantum devices. This approach overcomes a key limitation of standard graph learning models, the inability to differentiate between certain complex graph structures, by exceeding the capabilities of the first-level Weisfeiler-Leman test. Validated through simulations utilising up to 56 qubits and encompassing molecular property prediction and optimisation challenges, the framework demonstrates both theoretical guarantees and practical scalability.

Researchers demonstrated a quantum graph neural network capable of performing message passing and scaling to 56 qubits. This achievement matters because it provides a method for building quantum models that can analyse complex relational data, such as molecules or networks, while addressing the challenge of training quantum circuits. The framework was validated on synthetic graphs, molecular property prediction, and the travelling salesperson problem, and utilises pre-training on smaller graphs to improve performance. The authors suggest this work establishes a path towards near-term quantum algorithms with guaranteed scalability and expressivity.