Graph Neural Networks on Quantum Computers
图神经网络（GNNs）是一种在处理表示为图的结构数据时表现卓越的强大的机器学习模型，在社交网络分析和推荐系统等应用中取得了显著的性能。然而，传统的GNN在处理大规模图时面临可扩展性挑战。本文提出了一种将GNNs应用于量子计算机的方法，以可能解决这一挑战。我们设计了对三种经典GNN的量子算法：图卷积网络、图注意力网络和消息传递GNN。对简化图卷积（SGC）网络的量子实现的复杂性分析表明，与经典SGC相比，量子SGC具有潜在的量子优势，在时间和空间复杂性方面都有显著的提高。我们的复杂性可以在这两个方面做出权衡：在优化最小电路深度时，我们的量子SGC在输入大小上实现对数的运行时间复杂性（尽管代价是线性空间复杂性）。而在优化最小量子比特数时，量子SGC在输入大小上表现出对数的空间复杂性，相比之下，经典SGC具有指数级的降幅，但仍保持更好的时间复杂性。这些结果表明，我们的量子GNN框架可以在处理大型图时有效处理。这项工作为在量子计算机上实现更先进的图神经网络模型铺平了道路，为分析图形化数据提供了新的量子机器学习可能性。
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.
https://arxiv.org/abs/2405.17060
https://arxiv.org/pdf/2405.17060.pdf