# Graph Neural Networks on Quantum Computers

arXiv: https://arxiv.org/abs/2405.17060 · HTML: https://mlsanity.com/paper/2405.17060/

## Key facts

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

## Builds on (most cited first, 30 of 36)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering](https://mlsanity.com/paper/1606.09375/) (2016)
- [Graph Neural Networks: A Review of Methods and Applications](https://mlsanity.com/paper/1812.08434/) (2018)
- [Simplifying Graph Convolutional Networks](https://mlsanity.com/paper/1902.07153/) (2019)
- [Relational inductive biases, deep learning, and graph networks](https://mlsanity.com/paper/1806.01261/) (2018)
- [Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges](https://mlsanity.com/paper/2104.13478/) (2021)
- [Graph Neural Networks for Social Recommendation](https://mlsanity.com/paper/1902.07243/) (2019)
- [Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networks](https://mlsanity.com/paper/1905.07953/) (2019)
- [Modeling polypharmacy side effects with graph convolutional networks](https://mlsanity.com/paper/1802.00543/) (2018)
- [Challenges and Opportunities in Quantum Machine Learning](https://mlsanity.com/paper/2303.09491/) (2023)
- [Connecting ansatz expressibility to gradient magnitudes and barren plateaus](https://mlsanity.com/paper/2101.02138/) (2021)
- [ETA Prediction with Graph Neural Networks in Google Maps](https://mlsanity.com/paper/2108.11482/) (2021)
- [Theory of overparametrization in quantum neural networks](https://mlsanity.com/paper/2109.11676/) (2021)
- [Scalable Graph Neural Networks via Bidirectional Propagation](https://mlsanity.com/paper/2010.15421/) (2020)
- [Everything is Connected: Graph Neural Networks](https://mlsanity.com/paper/2301.08210/) (2023)
- [Exploiting symmetry in variational quantum machine learning](https://mlsanity.com/paper/2205.06217/) (2022)
- [Quantum Graph Neural Networks](https://mlsanity.com/paper/1909.12264/) (2019)
- [Group-Invariant Quantum Machine Learning](https://mlsanity.com/paper/2205.02261/) (2022)
- [Equivariant quantum circuits for learning on weighted graphs](https://mlsanity.com/paper/2205.06109/) (2022)
- [Representation Theory for Geometric Quantum Machine Learning](https://mlsanity.com/paper/2210.07980/) (2022)
- [Network Medicine Framework for Identifying Drug Repurposing Opportunities for COVID-19](https://mlsanity.com/paper/2004.07229/) (2020)
- [GRIP: A Graph Neural Network Accelerator Architecture](https://mlsanity.com/paper/2007.13828/) (2020)
- [Quantum Neuron: an elementary building block for machine learning on quantum computers](https://mlsanity.com/paper/1711.11240/) (2017)
- [LiGNN: Graph Neural Networks at LinkedIn](https://mlsanity.com/paper/2402.11139/) (2024)
- [Speeding up Learning Quantum States through Group Equivariant Convolutional Quantum Ans"atze](https://mlsanity.com/paper/2112.07611/) (2021)
- [Beyond Real-world Benchmark Datasets: An Empirical Study of Node Classification with GNNs](https://mlsanity.com/paper/2206.09144/) (2022)
- [Hybrid Quantum Classical Graph Neural Networks for Particle Track Reconstruction](https://mlsanity.com/paper/2109.12636/) (2021)

## Built on by (most cited first, 4 of 4)

- [Inductive Graph Representation Learning with Quantum Graph Neural Networks](https://mlsanity.com/paper/2503.24111/) (2025)
- [Scalable Message-Passing Quantum Graph Neural Networks in the Weisfeiler-Leman Hierarchy](https://mlsanity.com/paper/2606.26873/) (2026)
- [Guided Graph Compression for Quantum Graph Neural Networks](https://mlsanity.com/paper/2506.09862/) (2025)
- [Quantum Topological Graph Neural Networks for Detecting Complex Fraud Patterns](https://mlsanity.com/paper/2512.03696/) (2025)

## 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.