mlsanityData to 7 Oct 2026

Graph Neural Networks on Quantum Computers

arXiv 2405.17060 ↗First posted 27 May 2024quant-ph cs.AI cs.LGcited by 4

Not on the map. Why?

Abstract (arXiv)

Graph Neural Networks (GNNs) are powerful machine learning models that excel at analyzing structured data represented as graphs, demonstrating remarkable performance in applications like social network analysis and recommendation systems. However, classical GNNs face scalability challenges when dealing with large-scale graphs. This paper proposes frameworks for implementing GNNs on quantum computers to potentially address the challenges. We devise quantum algorithms corresponding to the three fundamental types of classical GNNs: Graph Convolutional Networks, Graph Attention Networks, and Message-Passing GNNs. A complexity analysis of our quantum implementation of the Simplified Graph Convolutional (SGC) Network shows potential quantum advantages over its classical counterpart, with significant improvements in time and space complexities. Our complexities can have trade-offs between the two: when optimizing for minimal circuit depth, our quantum SGC achieves logarithmic time complexity in the input sizes (albeit at the cost of linear space complexity). When optimizing for minimal qubit usage, the quantum SGC exhibits space complexity logarithmic in the input sizes, offering an exponential reduction compared to classical SGCs, while still maintaining better time complexity. These results suggest our Quantum GNN frameworks could efficiently process large-scale graphs. This work paves the way for implementing more advanced Graph Neural Network models on quantum computers, opening new possibilities in quantum machine learning for analyzing graph-structured data.

Key facts. Cited by 4 papers in the map (data through 7 Oct 2026). Builds on 36 of its 86 references that are in the map. First posted on arXiv 27 May 2024.

Builds on

36 of 86 references.

References · 36

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  2. 2017Graph Attention Networkscited by 8,854
  3. 2017Inductive Representation Learning on Large Graphscited by 6,284
  4. 2017Neural Message Passing for Quantum Chemistrycited by 3,460
  5. 2016Convolutional Neural Networks on Graphs with Fast Localized Spectral Filteringcited by 2,085
  6. 2018Graph Neural Networks: A Review of Methods and Applicationscited by 1,571
  7. 2019Simplifying Graph Convolutional Networkscited by 1,470
  8. 2018Relational inductive biases, deep learning, and graph networkscited by 1,341
  9. 2021Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gaugescited by 1,131
  10. 2019Graph Neural Networks for Social Recommendationcited by 711
  11. 2019Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networkscited by 540
  12. 2018Modeling polypharmacy side effects with graph convolutional networkscited by 237
24 more
  1. 2023Challenges and Opportunities in Quantum Machine Learningcited by 202
  2. 2021Connecting ansatz expressibility to gradient magnitudes and barren plateauscited by 180
  3. 2021ETA Prediction with Graph Neural Networks in Google Mapscited by 130
  4. 2021Theory of overparametrization in quantum neural networkscited by 100
  5. 2020Scalable Graph Neural Networks via Bidirectional Propagationcited by 87
  6. 2023Everything is Connected: Graph Neural Networkscited by 85
  7. 2022Exploiting symmetry in variational quantum machine learningcited by 68
  8. 2019Quantum Graph Neural Networkscited by 66
  9. 2022Group-Invariant Quantum Machine Learningcited by 56
  10. 2022Equivariant quantum circuits for learning on weighted graphscited by 41
  11. 2022Representation Theory for Geometric Quantum Machine Learningcited by 40
  12. 2020Network Medicine Framework for Identifying Drug Repurposing Opportunities for COVID-19cited by 38
  13. 2020GRIP: A Graph Neural Network Accelerator Architecturecited by 37
  14. 2017Quantum Neuron: an elementary building block for machine learning on quantum computerscited by 34
  15. 2024LiGNN: Graph Neural Networks at LinkedIncited by 31
  16. 2021Speeding up Learning Quantum States through Group Equivariant Convolutional Quantum Ans"atzecited by 29
  17. 2022Beyond Real-world Benchmark Datasets: An Empirical Study of Node Classification with GNNscited by 23
  18. 2021Hybrid Quantum Classical Graph Neural Networks for Particle Track Reconstructioncited by 20
  19. 2021Quantum Graph Convolutional Neural Networkscited by 18
  20. 2024Personalized Audiobook Recommendations at Spotify Through Graph Neural Networkscited by 14
  21. 2021Nonlinear transformation of complex amplitudes via quantum singular value transformationcited by 9
  22. 2021Quantum Optimization for Training Quantum Neural Networkscited by 6
  23. 2023The quantum cost function concentration dependency on the parametrization expressivitycited by 6
  24. 2023Spacetime-Efficient Low-Depth Quantum State Preparation with Applicationscited by 2

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2025: 3; 2026: 1.

4 papers.

  1. 2025Inductive Graph Representation Learning with Quantum Graph Neural Networkscited by 1
  2. 2025Guided Graph Compression for Quantum Graph Neural Networkscited by 0
  3. 2025Quantum Topological Graph Neural Networks for Detecting Complex Fraud Patternscited by 0
  4. 2026Scalable Message-Passing Quantum Graph Neural Networks in the Weisfeiler-Leman Hierarchycited by 0