Quantum Graph Neural Networks: Architectures, Trainability, and Applications
Organizations: School of Computer Engineering, Iran University of Science and Technology, Tehran, Iran · Faculty of Information and Communications Technology, Malek Ashtar University of Technology, Tehran, Iran
Abstract
Quantum graph neural networks (QGNNs) apply parametrized quantum circuits to graph-structured data, with the aim of overcoming limits of classical graph neural networks in scalability, expressivity, and long-range information flow. Since the first Hamiltonian-based model in 2019, the field has produced many architectures, applications, and claims, but the evidence behind them has not been assessed systematically. This survey introduces a unified formalism that describes every QGNN as an encoder, a graph-conditioned circuit, observables, and an optional classical head, together with a circuit-level condition for permutation equivariance and a resource model for comparing costs. We organize the literature into five architecture families (convolutional, equivariant, message-passing and recurrent, Hamiltonian, and hybrid) and compare them by qubit cost, symmetry, scalability, and evidence. We then review symmetry and geometric inductive biases (permutation, rotation, and Lorentz), the results on expressivity, trainability, noise, and scalability, and applications in high-energy physics, chemistry, finance, healthcare, earth observation, and transportation. An audit of datasets and evaluation practices leads to a minimum reporting protocol. Our main finding is that the design space is rich and symmetry is the best-supported inductive bias, whereas the evidence remains thin: results are mostly simulated, on small graphs, at parity with classical models or with fewer parameters, and no advantage has yet been established on tasks over classical graph data. We identify five open challenges and a research agenda covering provable advantage, equivariant and geometric designs, fault-tolerant implementations, and shared benchmarks. The coverage extends through 2026 and emphasizes recent work.
Figures & tables
| Limitation | Quantum hope | What the evidence shows | Where |
|---|---|---|---|
| Scalability | compressed encodings; block-encoded graph operators | cost moves to data loading, circuit executions, or classical pre-processing | Sections 6.4 and 9.3 |
| Over-smoothing | unitary, norm-preserving layers | no dedicated study found; not tested against classical remedies | Section 9.3 |
| Over-squashing | entanglement and long-range Hamiltonian interactions | untested; local-gate circuits have the same -hop light cone as message passing | Propositions 2.4 and 9.3 |
| Expressivity | high-dimensional quantum feature maps | universality and WL-level results, but no separation from classical GNNs at equal cost | Sections 6.1 and 9.5 |
| Status | Covered | Examples |
|---|---|---|
| Included | parametrized circuits applied to attributed graphs, fully quantum or hybrid | Hamiltonian, equivariant, convolutional, message-passing, and hybrid QGNNs ( Section 4 ) |
| Context | quantum-inspired models; quantum data on graphs; quantum-computed features | Bai et al. [10] ; Beer et al. [25] ; Thabet et al. [26] ( Section 3.2 ) |
| Excluded | learning-free quantum graph algorithms; GNNs that support quantum computing; graph-agnostic QNNs | walk speedups, QAOA as an optimizer; GNN decoders and compilers; generic variational classifiers |
| Survey | Year | Focus | Relation to this work |
|---|---|---|---|
| Tang et al. [23] | 2022 | quantum computing for graph tasks, from graph computing to graph learning | predates most architectures reviewed here |
| Ceschini et al. [27] | 2026 (preprint 2024) | critical review of QGNNs: noise, decoherence, scalability | closest in topic; we add formalism, symmetry, evidence audit, 2025–2026 works |
| Shayeganfar et al. [24] | 2025 | taxonomy of quantum graph learning; materials and image classification | broader and application-driven |
| This survey | 2026 | unified formalism, taxonomy, symmetry, evidence audit, research agenda | — |
| Representation | Memory | Role in (quantum) graph learning |
|---|---|---|
| Adjacency matrix | dense; sparse | Defines neighbourhoods and message routing; basis of spectral methods and of Hamiltonian-type encodings of the graph. |
| Laplacians | same | Smoothness (Dirichlet energy), spectral filters, diffusion, positional encodings. |
| Edge list / CSR | Efficient sparse message passing and mini-batch sampling. | |
| Node/edge feature matrices , | , | Inputs to message functions; must be embedded (“encoded”) in qubits for quantum models. |
| Positional/structural encodings | Eigenvectors of , random-walk statistics, shortest-path distances; break symmetries beyond 1-WL ( Section 2.1.3 ). |
| Model | Node update | Time | Key property |
|---|---|---|---|
| ChebNet [ 34 ] | -hop localized spectral filter | ||
| GCN [ 35 ] | Fixed low-pass filter | ||
| GraphSAGE [ 12 ] | Inductive; sampling | ||
| GAT [ 80 ] | Learned anisotropic weights | ||
| GIN [ 17 ] | As expressive as 1-WL | ||
| PNA [ 75 ] | multiple aggregators degree scalers | Richer aggregation |
| Failure mode | Symptom and mechanism | Diagnostic | Representative remedies |
|---|---|---|---|
| Over-smoothing | Representations converge as depth grows; repeated low-pass filtering Equation 12 | Dirichlet energy, MAD [ 135 ] | Residuals [ 142 ] ; normalization [ 146 ] ; DropEdge [ 148 ] ; PDE/oscillator models [ 150 , 153 ] |
| Over-squashing | Exponentially many messages compressed through bottlenecks Equation 13 | Jacobian sensitivity; curvature; effective resistance [ 16 , 158 ] | Rewiring [ 157 , 164 ] ; multi-hop [ 165 ] ; global attention [ 84 ] |
| Scalability | Neighbourhood explosion; attention | Memory and time vs. | Sampling [ 12 , 172 ] ; decoupling [ 67 , 175 ] ; distributed [ 179 ] ; linear attention [ 85 ] |
| Encoding | Qubits | Depth | Noise robustness | Typical use |
|---|---|---|---|---|
| Basis | (edges) | high | exact structure | |
| Angle | high | node features, NISQ QGNNs | ||
| Dense angle | high | compact node features | ||
| Amplitude | (generic) | low | small graphs; compression | |
| Re-uploading | as angle | medium | expressivity | |
| Graph-state / Hamiltonian | medium | topology |
| Obstacle | Cause | Mitigation | Caveat |
|---|---|---|---|
| Barren plateaus | Expressive/global/entangled circuits; large Lie algebra [ 205 , 206 , 208 ] | Local costs; symmetric/equivariant ansatz; structured initialization [ 215 , 212 ] | BP-free may be classically simulable [ 21 ] |
| Noise | Gate errors; decoherence [ 211 ] | Shallow circuits; error mitigation [ 227 ] | Mitigation overhead grows with size |
| Data loading | Amplitude encoding costs [ 201 ] | Shallow angle or dense-angle encoding [ 200 ] | More qubits for angle encoding |
| Shot cost | samples per estimate | Gradient-free or Fisher-aware optimizers; batching | Slow wall-clock training |
| Connectivity | Mismatch of graph and device coupling map | Sparse graphs; subgraph partitioning | Routing overhead |
| Component | Classical ( Equations 6 and 7 ) | Quantum (this survey) |
|---|---|---|
| Node input | angle/amplitude-encoded qubit(s) of node via | |
| Node state | reduced state ; accessed via | |
| Topology | , , | entangling pattern Equation 18 ; couplings of Equation 19 |
| , | learnable message, invariant aggregator | shared-parameter two-qubit gates over (commuting or symmetrized) |
| MLP / recurrent cell | trainable single-qubit rotations Equation 17 | |
| sum / mean / learned pooling | symmetric observable, e.g. , then classical head |
| Symbol | Meaning |
|---|---|
| , , | Graph, number of nodes, number of edges |
| , , , | Adjacency, degree, Laplacian, neighbourhood of node |
| , | Node features, feature vector of node |
| , , | Permutation group, permutation matrix, qubit-permuting unitary on |
| , | Classical hidden vector; reduced quantum state of node after layer |
| Number of qubits ( in the node–qubit mapping) |
| Variant | Parameter tying | Classical analogue | Use |
|---|---|---|---|
| General QGNN | none; free | general message passing with per-node weights | quantum processes on a network |
| QGRNN | (over repetitions) | recurrent network, weights shared over time | learning effective graph Hamiltonian dynamics |
| QGCNN | , | GCN / MPNN, filter shared over the graph | permutation-invariant learning, e.g. graph classification |
| QSGCNN | spectral form, CV-QAOA-inspired | Laplacian-based spectral convolution | spectral tasks, e.g. clustering |
| Work | Graph data | Quantum ingredient | Execution | Regime |
|---|---|---|---|---|
| Bai et al. [10] | classical graphs | quantum information propagation on aligned vertex grids | classical hardware | quantum-inspired |
| Dernbach et al. [11] | classical graphs | learned, feature-dependent quantum-walk coins | classical hardware | quantum-inspired |
| Verdon et al. [9] | quantum network / classical graphs | Hamiltonian evolution with graph interaction topology ( Section 3.1 ) | numerical simulation | fully quantum |
| Zheng et al. [236] | classical graphs | amplitude encoding, graph-structured gates, measurement pooling | circuit simulation | fully quantum |
| Zheng et al. [235] | classical graphs | circuit realization of the QSGCNN | circuit simulation | fully quantum |
| Beer et al. [25] | quantum data on vertices | QNN with graph-informed learning objective | simulation | quantum data |
| Family | Examples | Qubits | Equivariance | Scalability limit | Evidence |
|---|---|---|---|---|---|
| Convolutional, variational | Zheng et al. [236] , Hu et al. [238] , Zeng et al. [239] | (amplitude) | not imposed | state preparation; circuit per graph | simulation; one hardware run [ 239 ] |
| Convolutional, algorithmic/spectral | Liao et al. [237] , Ye et al. [240] | plus ancillas | not applicable (algorithmic) | data access (QRAM); fault tolerance | complexity analysis |
| EQGC (EH/EDU) | Mernyei et al. [231] , Mernyei et al. [241] | by construction | width , edge gates per layer | universality proof; small simulations | |
| Ego-graph / sampled aggregators | Ai et al. [242] , Faria et al. [233] | , independent of | shared aggregator; stated in [ 233 ] | circuit runs grow with nodes; local view only | simulation (QM9 and others) |
| In-circuit message passing | Raj et al. [244] | node register plus embedding register; simulated to 56 qubits | by construction (stated) | simulation cost; preprint | proofs; simulation |
| Recurrent / Hamiltonian | Verdon et al. [9] , Wang et al. [234] | by construction if tied ( Proposition 3.1 ) | graph-specific circuit; Trotter depth | small simulations |
| Strategy | Where symmetry lives | Examples | Cost / limit |
|---|---|---|---|
| Invariant inputs | features (distances, Minkowski products) | Jahin et al. [255] ; invariant baselines of Forestano et al. [256] | cheap; loses directional information |
| Equivariant gates | circuit (commutant of the group) | EQGC [ 231 ] ; Liu et al. [252] | group-aware encoding; more qubits |
| Symmetrization | average over the group | Das and Caruso [217] | many circuit evaluations |
| Classical equivariant backbone | classical layers; quantum part small | Jahin et al. [255] ; Park and Park [254] | symmetry of the quantum part unchecked |
| Result | Mechanism | Source | Scope and caveat |
|---|---|---|---|
| Universality on bounded graphs | equivalence to MPNN with random node initialization | Mernyei et al. [231] | existence statement; circuit size not bounded; probabilistic |
| Beyond 1-WL, equivariant | in-circuit message passing at a chosen WL level | Raj et al. [244] | preprint; simulation up to 56 qubits |
| Quantum PE RRWP | correlations of graph-Hamiltonian dynamics | Thabet et al. [26] | quantum part untrained; classical versions also help |
| Fourier-series model | encoding generators fix the frequencies | Schuld et al. [199] | function-class statement, not graph-specific |
| Family | Mechanism | Evidence | Caveat |
|---|---|---|---|
| Equivariant / tied Hamiltonian | symmetry restricts the algebra | theory for permutation-equivariant circuits [ 215 ] | restriction may allow classical simulation [ 21 ] |
| Sampled / ego-graph | circuit width independent of graph | numerical gradient variance without plateau as qubits grow [ 233 ] | small qubit counts; simulation |
| In-circuit message passing | trainable dynamics do not scale with graph size | Lie-algebra argument and simulation [ 244 ] | preprint |
| Variational convolutional | shallow, local circuits | plateau analysis of the QSGCN [ 235 ] ; trainability study with dequantization [ 221 ] | mixed conclusions |
| Recurrent | residual connections | empirical improvement [ 247 ] | simulation |
| Strategy | Mechanism and examples | Qubits | Trade-off |
|---|---|---|---|
| Sampling, ego-graphs | process local subgraphs [ 242 , 233 , 243 ] | set by | runs grow with nodes; local view |
| Graph compression, pooling | reduce nodes and features first [ 258 , 257 , 253 ] | small, fixed | information loss; classical model needed |
| Compressed encodings | amplitude encoding [ 236 , 249 ] | state-preparation cost | |
| Block / walk encodings | block-encode [ 237 , 240 ] | plus ancillas | data access; fault tolerance |
| Size-independent dynamics | shared parameters; pre-training on small graphs [ 244 ] | grows with graph in simulation | preprint |
| Domain | Graph | Works | Family | Outcome (as reported) |
|---|---|---|---|---|
| HEP tracking | hits, segments | Tüysüz et al. [259] , Tüysüz et al. [260] | hybrid | similar to the classical GNN |
| HEP jets | jet constituents | Chen and Chen [261] , Forestano et al. [256] , Jahin et al. [255] , Casals et al. [258] | in-circuit, EQGC, hybrid | vs. classical GNNs: speedup argued; higher AUC; efficiency gains |
| Chemistry, materials | atoms, bonds | Ryu et al. [262] , Vitz et al. [263] , Piperno et al. [264] , Villalba-Díez [265] , Lu et al. [266] | hybrid and fully quantum | competitive; fewer parameters |
| Finance | accounts, transactions | Innan et al. [267] | VQC-based QGNN | AUC 0.85, above classical GNNs |
| Healthcare | cells in tissue | Ray et al. [249] | hybrid | on par with classical GNNs |
| Earth observation | grid, teleconnections | Mauro et al. [250] | hybrid | ONI forecasting |
| Domain | Dataset | Size | Used in |
|---|---|---|---|
| Molecules, materials | QM9 | atoms | Faria et al. [233] , Villalba-Díez [265] |
| perovskite formation energies | – | Vitz et al. [263] | |
| water-molecule configurations | 3 atoms | Piperno et al. [264] | |
| DAVIS kinase (affinity) | – | Santo et al. [271] | |
| HEP | tracking events | – | Tüysüz et al. [259] , Tüysüz et al. [260] |
| Top, JetNet jets | ; | Chen and Chen [261] |
| Item | What to report | Why / example |
|---|---|---|
| Model resources | , depth, gates, , encoding, shots | lets cost be compared ( Section 2.3.4 ) |
| Execution mode | statevector, shots, noise model, or hardware | hardware runs are rare [ 239 ] |
| Baselines | parameter-matched, equally tuned; encoding-matched controls | Faria et al. [233] |
| Seeds and statistics | several seeds, mean and interval, paired tests | multi-seed changes conclusions [ 271 ] |
| Data protocol | fixed splits, subset indices, sampling procedure, graph size vs. | subsets differ across papers ( Table 19 ) |
| Ablations | replace the quantum layer by a classical layer of equal width | compression and encoding checks [ 249 ] |
| Challenge | Evidence so far | Missing | Section |
|---|---|---|---|
| Hardware, noise | gate-budget estimates; two small hardware runs | hardware-aware graph embedding; symmetry under noise; logical-qubit estimates | 9.1 |
| Trainability | numerical absence of plateaus vs. qubits; symmetry-based guarantees | graph-dependent Lie-algebra analysis; scaling by graph, not qubits | 9.2 |
| Scaling | sampling, compression, in-circuit dynamics in simulation | information-loss accounting; end-to-end resource estimates | 9.3 |
| Fair comparison | parameter-matched and encoding-controlled baselines in a few studies | shared, size-aware benchmark; cost-normalized reporting | 9.4 |
| Theory | universality, WL-level, QPE results | separation at equal cost; size generalization; advantage without data-access assumptions | 9.5 |
| Route | Cost moves to | What remains to be shown |
|---|---|---|
| Node–qubit mapping | qubits and depth ( ) | any graph beyond the budget of Figure 13 |
| Index or amplitude registers | loading and readout; possibly QRAM | speedup net of state preparation and dequantization |
| Sampling, ego-graphs | circuit executions grow with nodes | value of the quantum part relative to the classical sampler |
| Compression, pooling | a classical encoder | how much task-relevant structure is lost |
| In-circuit, size-independent dynamics | classical simulation (so far) | behaviour beyond simulated sizes |
| Claim | What is typically shown | What is needed |
|---|---|---|
| Fewer parameters | lower at similar score | total cost: shots, depth, simulation time; a classical model of equal accuracy |
| Better generalization | lower gap at small data or larger molecules [ 233 ] | learning curves, several seeds, out-of-distribution splits, encoding controls |
| Noise robustness | small circuits; few noisy runs | noise sweeps and hardware runs ( Table 20 ) |
| Expressivity beyond 1-WL | separation of small synthetic graphs | comparison with classical random-initialization and subgraph GNNs at equal cost |
| Speedup | asymptotic argument, assumes data access | end-to-end cost including loading and readout; dequantization check |
| Advantage | AUC or accuracy above one baseline [ 267 ] | strong tuned baselines; several datasets; paired statistics |
| Question | Why it matters | Possible route |
|---|---|---|
| Which graph properties are efficiently computable by QGNNs but not by classical GNNs of equal cost? | turns universality into separation | substructure counting; WL-hierarchy arguments |
| How does the dynamical Lie algebra of QGNN layers depend on graph structure? | decides trainability by graph class | extend the QAOA analysis [ 276 ] to encoders and readouts |
| What are size-generalization bounds for tied-parameter QGNNs? | justifies pre-training on small graphs | stability and kernel methods [ 282 , 283 ] |
| Is there a trainable QGNN family with no classical surrogate? | minimal condition for advantage | surrogate construction [ 278 ] |
| Where do quantum inputs give provable advantage on graphs? | the most plausible regime | quantum-data graphs [ 25 , 285 ] |
| Direction | Now (NISQ, simulation) | Early fault tolerance | Fault tolerance |
|---|---|---|---|
| Advantage | quantum-data and generative tasks on tens of qubits | dynamics learning on graphs | spectral layers with data access |
| Equivariant, geometric | scalar-input and small equivariant circuits | symmetry-preserving mitigation; layers | large equivariant dynamics |
| Fault tolerance | per-layer resource estimates | Hamiltonian layers on few logical qubits | block-encoded layers |
| Benchmarks, software | shared tiers and reporting protocol | hardware-in-the-loop leaderboards | resource-based end-to-end benchmarks |
| Regime | Why advantage is plausible | Support | Obstacle |
|---|---|---|---|
| Quantum data on graphs | the learner can use quantum memory; classical learners cannot | Beer et al. [25] , Huang and others [285] | graph-structured task with a proof |
| Graph-structured generative models | hard-to-sample, classically trainable circuits | Huang et al. [286] , Recio-Armengol et al. [287] | not yet shown for graph data |
| Dynamics learning on graphs | data generated by quantum dynamics on an interaction graph | QGRNN [ 9 ] | classical surrogates |
| Fault-tolerant spectral layers | block encodings and phase estimation | Liao et al. [237] , Ye et al. [240] | data access; dequantization |
| Walk-based graph algorithms | exponential speedup in the oracle model | Childs et al. [20] | not a learning problem |
| Layer | Primitive | Dominant cost | Status |
|---|---|---|---|
| Block-encoded convolution, attention, message passing | block encoding of graph matrices | data access and normalization [ 237 ] | complexity analysis |
| Spectral convolution | phase estimation and swap test | phase-estimation depth; data loading [ 240 ] | no numerics |
| Hamiltonian-evolution layer | product formulas, qubitization | evolution time; gates growing with | small simulations |
| Variational layer on logical qubits | parametrized rotations | logical-gate and magic-state overhead | not studied for QGNNs |
| Component | Existing resource | Gap |
|---|---|---|
| Graph data | standardized classical benchmarks with fixed splits [ 167 , 272 ] ; QM9 through PyTorch Geometric [ 57 ] | size tiers matched to qubit budgets; shared subsets |
| Expressivity | BREC pairs, used by Raj et al. [244] | comparison at equal cost with classical randomized and subgraph GNNs |
| Quantum-ML tasks | curated QML benchmark datasets [ 224 ] , hosted in PennyLane | graph tasks and graph-specific baselines |
| Protocol and statistics | minimum reporting protocol ( Table 20 ); paired tests in the classical suites | adoption; cost-normalized leaderboards |
| Software | differentiable circuit libraries [ 274 ] paired with graph libraries; the release of Raj et al. [244] with a vectorized PyTorch backend and a PennyLane reference backend | a common QGNN layer interface, automatic resource counters, and hardware back-ends |
| Question | Answer | Where |
|---|---|---|
| What is a QGNN? | encoder, graph-conditioned circuit, observables, optional classical head; equivariance as a circuit-level condition | Section 2.3 |
| How are QGNNs organized? | five families: convolutional, equivariant, message-passing/ego-graph/recurrent, Hamiltonian, hybrid | Section 4 |
| Which inductive bias works best? | symmetry, from permutations to rotations and Lorentz transformations | Section 5 |
| Can they be trained, scaled, and run? | yes on small graphs in simulation; limited by noise, graph-dependent trainability, and qubit counts | Section 6 |
| Where are they used, and how good is the evidence? | many domains; parity or parameter efficiency, mostly simulated, few baselines | Sections 7 and 8 |
| Is there a quantum advantage? | not yet shown for classical graph data; quantum-data and generative settings are most plausible | Sections 9.5 and 10.1 |