Graph Neural Networks on Quantum Computers

图神经网络（GNNs）是强大的机器学习模型，擅长分析以图形表示的结构化数据，在社交网络分析和推荐系统等应用中表现出了卓越的性能。然而，当处理大规模图形时，传统的GNNs面临着可扩展性挑战。本文提出了在量子计算机上实现GNNs的框架，以潜在地解决这些挑战。我们设计了对应于三种基本类型的经典GNNs的量子算法：图卷积网络、图注意力网络和消息传递GNNs。我们对简化图卷积（SGC）网络的量子实现进行了复杂度分析，表明其量子优势可能比其经典对应物更好，时间和空间复杂度都有显著的改进。我们的复杂度可以在两者之间进行权衡：当优化电路深度时，我们的量子SGC在输入大小上实现了对数时间复杂度（尽管以线性空间复杂度为代价）。当优化量子位使用时，量子SGC在输入大小上呈对数空间复杂度，相比于经典SGC，可以实现指数级的降低，同时仍然保持更好的时间复杂度。这些结果表明，我们的量子GNN框架可以有效地处理大规模图形。这项工作为在量子计算机上实现更先进的图神经网络模型铺平了道路，为分析图形结构化数据的量子机器学习开辟了新的可能性。

本论文旨在提出一种在量子计算机上实现GNNs的框架，以解决经典GNNs在处理大规模图形数据时面临的可扩展性挑战。

论文提出了三种基本类型的GNN的量子算法：图卷积网络、图注意力网络和消息传递GNN。通过对简化图卷积（SGC）网络的量子实现进行复杂性分析，证明了量子SGC具有潜在的量子优势。

论文的实验结果表明，量子GNN框架可以高效地处理大规模图形数据。当优化电路深度时，量子SGC在输入大小的时间复杂度上实现了对数级别的优化，但代价是线性空间复杂度；当优化量子位使用时，量子SGC在输入大小的空间复杂度上实现了对数级别的优化，比经典SGC实现了指数级别的降低，同时仍然保持更好的时间复杂度。

近期的相关研究包括：Quantum Machine Learning on Graphs和Quantum Graph Neural Networks。