Transformers are increasingly employed for graph data, demonstrating competitive performance in diverse tasks. To incorporate graph information into these models, it is essential to enhance node and edge features with positional encodings. In this work, we propose novel families of positional encodings tailored for graph transformers. These encodings leverage the long-range correlations inherent in quantum systems, which arise from mapping the topology of a graph onto interactions between qubits in a quantum computer. Our inspiration stems from the recent advancements in quantum processing units, which offer computational capabilities beyond the reach of classical hardware. We prove that some of these quantum features are theoretically more expressive for certain graphs than the commonly used relative random walk probabilities. Empirically, we show that the performance of state-of-the-art models can be improved on standard benchmarks and large-scale datasets by computing tractable versions of quantum features. Our findings highlight the potential of leveraging quantum computing capabilities to potentially enhance the performance of transformers in handling graph data.
Transformers are increasingly employed for graph data, demonstrating competitive performance in diverse tasks. To incorporate graph information into these models, it is essential to enhance node and edge features with positional encodings. In this work, we propose novel families of positional encodings tailored for graph transformers. These encodings leverage the long-range correlations inherent in quantum systems, which arise from mapping the topology of a graph onto interactions between qubits in a quantum computer. Our inspiration stems from the recent advancements in quantum processing units, which offer computational capabilities beyond the reach of classical hardware. We prove that some of these quantum features are theoretically more expressive for certain graphs than the commonly used relative random walk probabilities. Empirically, we show that the performance of state-of-the-art models can be improved on standard benchmarks and large-scale datasets by computing tractable versions of quantum features. Our findings highlight the potential of leveraging quantum computing capabilities to potentially enhance the performance of transformers in handling graph data.
In this work, we propose novel families of positional encodings tailored to graph neural networks obtained with quantum computers. These encodings leverage the long-range correlations inherent in quantum systems that arise from mapping the topology of a graph onto interactions between qubits in a quantum computer. Our inspiration stems from the recent advancements in quantum processing units, which offer computational capabilities beyond the reach of classical hardware. We prove that some of these quantum features are theoretically more expressive for certain graphs than the commonly used relative random walk probabilities. Empirically, we show that the performance of state-of-the-art models can be improved on standard benchmarks and large-scale datasets by computing tractable versions of quantum features. Our findings highlight the potential of leveraging quantum computing capabilities to enhance the performance of transformers in handling graph data.
Recently, efforts have been made in the community to design new Graph Neural Networks (GNN), as limitations of Message Passing Neural Networks became more apparent. This led to the appearance of Graph Transformers using global graph features such as Laplacian Eigenmaps. In our paper, we introduce a GNN architecture where the aggregation weights are computed using the long-range correlations of a quantum system. These correlations are generated by translating the graph topology into the interactions of a set of qubits in a quantum computer. This work was inspired by the recent development of quantum processing units which enables the computation of a new family of global graph features that would be otherwise out of reach for classical hardware. We give some theoretical insights about the potential benefits of this approach, and benchmark our algorithm on standard datasets. Although not being adapted to all datasets, our model performs similarly to standard GNN architectures, and paves a promising future for quantum enhanced GNNs.
Quantum computing holds significant potential for advancing machine learning, particularly in handling complex graph-structured data. This paper introduces Single-Qubit Quantum Graph Neural Networks (sQGNNs), a novel model that integrates quantum networks with quantum walk operations to improve generalization in graph learning tasks. By leveraging quantum walks, we demonstrated sQGNNs capture complex relational patterns and enhance network expressiveness beyond classical methods. Our results proved that quantum encoding efficiently represents high-dimensional graph data, preserving dependencies and optimizing memory use. Across benchmark datasets, sQGNNs demonstrate superior generalization and robustness against overfitting, achieving higher accuracy with reduced computational cost. Our results underscore sQGNNs’ promise for scalable, quantum-enhanced graph learning, establishing a foundation for future quantum-assisted machine learning applications.
Graph Neural Networks (GNNs) have established themselves as powerful tools for learning from graph-structured data. However, their reliance on local message-passing mechanisms leads to over-squashing-the compression of exponentially growing neighborhood information into fixed-size vectors-which severely limits long-range dependency modeling. We introduce the Quantum-Inspired Graph Neural Network (QGNN) with a novel Quantum Entanglement Loss (QEL) function that addresses this challenge through a fundamentally different mechanism than existing approaches. Unlike spectral regularization (which enforces smoothness) or maximum entropy methods (which encourage representation diversity), QEL minimizes the von Neumann entropy of the node embedding correlation matrix, thereby concentrating eigenvalues in dominant eigenmodes that preserve global structural patterns. This entropy minimization creates direct information pathways between distant but functionally related nodes, effectively bypassing multi-hop bottlenecks. We evaluate QGNN on both standard benchmarks (Cora, Citeseer, PPI, Electronic Circuits) and the Long Range Graph Benchmark (LRGB) suite, which features graphs with average diameters up to 56.99 (Peptides). On LRGB datasets, QGNN achieves substantial improvements: 37.6% relative MAE reduction on Peptides-struct compared to GCN, 4.0% improvement over Graph Transformers (GraphGPS), and notably, 97% better performance than GCN on node pairs separated by 7+ hops. Despite these gains, QGNN requires only 20-30% additional computational overhead compared to standard GCN, while being 5-6 × faster than Graph Transformer approaches. Our results establish entropy-based regularization as a principled and efficient approach for long-range dependency modeling in graphs.
Quantum computing has been a prominent research area for decades, inspiring transformative fields such as quantum simulation, quantum teleportation, and quantum machine learning (QML), which are undergoing rapid development. Within QML, hybrid classical-quantum algorithms like Quantum Neural Networks (QNNs) and Variational Quantum Classifiers (VQCs) have shown promise in leveraging quantum circuits and classical optimizers to classify classical data efficiently. Simultaneously, classical machine learning has made significant strides in graph classification, employing Graph Neural Networks (GNNs) to analyze systems ranging from large-scale structures like the Large Hadron Collider to molecular and biological systems like proteins and DNA. Combining the advancements in quantum computing and graph classification presents a unique opportunity to develop quantum algorithms capable of extracting features from graphs and performing their classification effectively. In this paper, we propose a novel quantum encoding framework for graph classification using VQCs. Unlike existing approaches such as PCA-VQC, which rely on dimensionality reduction techniques like Principal Component Analysis (PCA) and may lead to information loss, our method preserves the integrity of graph data. Furthermore, our encoding approach is optimized for Noise-Intermediate Scale Quantum (NISQ) devices, requiring a limited number of qubits while achieving comparable or superior classification performance to PCA-VQC. By constructing slightly more complex circuits tailored for graph encoding, we demonstrate that VQCs can effectively classify graphs within the constraints of current quantum hardware.
Quantum computing offers a promising avenue to reduce growing machine learning model complexity as required in large language models and simulation models for weather forecasts, financial forecasts, or engineering.Graph neural networks are a particular class of machine learning models that have garnered much attention for their ability to deal well with structured data.We investigate how to enhance existing GNNs and find through the inductive bias that quantum circuits are used best to encode node features.The proposed Quantum Feature Embeddings (QFEs) turn raw input features into quantum states, enabling non-linear and entangled representations.In particular, QFEs provide normalized, non-redundant weight matrices in an exponentially larger feature space and require much fewer qubits than fully quantum graph neural networks.On standard graph benchmark datasets, we showcase that for the same parameter count QFEs perform better than their classical counterpart, and are able to match the performance of an exponentially larger model.Finally, we study the potential benefit of using a hybrid quantum graph neural network over a classic alternative on a concrete use case, laser cutting.We find that the proposed model has the performance and thus the near-term potential to uplift these business applications.