From graphs to qubits: a critical review of quantum graph neural networks

Many real-world problems are naturally represented as graphs. Molecules can be described through atoms and their bonds, transportation systems through locations and connections, financial networks through transactions, and physical systems through interacting particles. Graph Neural Networks (GNNs) have become one of the main artificial intelligence approaches for extracting information from these complex relational structures. Their strength comes from message passing: each node progressively combines information from its neighbours, allowing the network to learn representations that reflect both individual characteristics and the topology of the graph. However, as graphs become larger and more densely connected, this process can require substantial computational resources. Repeated aggregation can also lead to phenomena such as over-smoothing, where node representations gradually become too similar to remain easily distinguishable. Quantum computing introduces a radically different computational environment. Instead of processing information exclusively through classical bits, it operates with qubits, superposition, entanglement and quantum measurements. Combining these principles with graph learning leads to Quantum Graph Neural Networks (QGNNs): models designed to explore whether quantum computation can improve how complex relational data are represented and processed.

The first challenge is translating classical graph information into something a quantum computer can process. A graph can contain node features, edge information, adjacency matrices and structural relationships, but quantum algorithms require these data to be encoded into quantum states. Different strategies can be used. Angle encoding represents classical variables through quantum rotations, basis encoding maps discrete information onto computational states, and amplitude encoding can represent high-dimensional vectors using a relatively small number of qubits. Graph topology can also be embedded directly into Hamiltonians, creating a particularly interesting connection between graph structures and quantum dynamics. Once encoded, information is processed through parameterized quantum circuits. Quantum gates manipulate the qubits, entangling operations introduce correlations, and measurements convert the resulting quantum states into classical information. Training generally creates a feedback loop between quantum and classical computation. A quantum circuit generates an output, a classical processor evaluates a cost function and updates the circuit parameters, and the process is repeated until the model converges. This hybrid mechanism is particularly important for current Noisy Intermediate-Scale Quantum devices, where fully quantum learning pipelines remain difficult to implement at scale.

The integration between quantum computing and graph neural networks can occur at different depths. One approach moves the entire graph-processing pipeline into the quantum domain. In these fully quantum architectures, graph information is encoded and manipulated directly through quantum states and parameterized circuits. A second strategy combines quantum and classical computation more tightly. Hybrid QGNNs insert quantum operations directly into fundamental graph-learning mechanisms, such as message passing, aggregation, convolution or node updating. Classical computation can therefore handle some parts of the problem while quantum circuits are used where their properties may provide an advantage. A third approach is more conservative. Quantum-assisted models preserve the classical GNN architecture and introduce quantum computation only as an external component, for example to transform features before graph processing or to classify representations produced by the classical network. This distinction is important because increasing quantum integration also increases hardware requirements. Fully quantum approaches offer the strongest conceptual connection with quantum computation, while hybrid and quantum-assisted architectures are generally more compatible with the limitations of current devices.

Quantum graph learning is being explored across very different application domains. In high-energy physics, graph structures can represent particle interactions and collision events, supporting tasks such as jet tagging, particle identification and track reconstruction. In chemistry and biology, molecules naturally form graphs, making QGNNs suitable for predicting molecular properties, modelling interactions and analysing quantum-chemical characteristics. Complex systems provide another application area, including traffic forecasting, climate modelling and fraud detection, where relationships between multiple entities evolve over space and time. An especially natural application appears when the problem itself is quantum mechanical. If a graph directly represents a Hamiltonian, interactions between quantum systems or quantum-state relationships, the mapping between graph topology and quantum computation becomes much more direct. This is one of the contexts in which the potential of QGNNs becomes particularly interesting.

A central question is whether adding quantum computation actually makes graph learning better. The answer cannot be reduced to classification accuracy alone. Current results indicate that the benefits are strongly dependent on the task. Some hybrid architectures can match or modestly improve classical performance while using fewer trainable parameters or requiring fewer training iterations. In particular configurations, theoretical or computational complexity advantages have also been identified. At the same time, there is still no general evidence that QGNNs systematically outperform strong classical GNNs across ordinary large-scale graph-learning problems. This makes the definition of quantum advantage especially important. A model with fewer parameters may demonstrate useful quantum efficiency without necessarily providing faster end-to-end execution. Similarly, reducing the complexity of a quantum circuit does not automatically translate into an overall advantage if loading classical graph data into the quantum system is itself computationally expensive. The entire pipeline must therefore be considered: encoding, circuit execution, repeated measurements, optimization and interaction between classical and quantum hardware.

Present-day quantum computers introduce limitations that classical neural networks do not face. Quantum states are fragile and susceptible to noise and decoherence. The number of available qubits is limited, connectivity between them is constrained, and increasing circuit depth can make computation progressively less reliable. Training introduces another problem known as the barren plateau phenomenon. As some quantum circuits become larger or deeper, the gradients used for optimization can become extremely small. The learning algorithm then receives almost no useful information about how its parameters should change, making effective training increasingly difficult. Graph size adds further pressure. Representing large networks can require increasing numbers of qubits, deeper circuits or more expensive encoding procedures. Techniques such as quantum error mitigation, topology-aware circuit design, gate pruning, hybrid architectures and more suitable optimization strategies are therefore being investigated to make QGNNs more compatible with realistic hardware.

The most significant direction emerging from quantum graph learning is not simply the replacement of classical GNNs with quantum versions. Instead, it is the search for computational structures in which classical and quantum resources can complement one another. Near-term opportunities appear particularly relevant for parameter-efficient hybrid models and problems whose graph structure has a natural quantum interpretation. At the same time, standardized benchmarks, realistic hardware measurements and complete resource estimates are needed to determine whether an apparent improvement represents genuine quantum advantage or simply a different computational trade-off. QGNNs therefore represent an evolving intersection between two powerful ways of representing complexity: graphs describe relationships, while quantum systems describe information through states, interactions and correlations. Bringing these two paradigms together creates a new way to investigate relational intelligence, but the transition from promising experiments to scalable quantum-enhanced graph learning will depend on proving where quantum resources provide a concrete computational benefit.