2023/10/31 by Slimane Thabet, Thabet, Slimane, Romain Fouilland +11 · 1 citation
Computer Science · Engineering · Physics and Astronomy · #Advanced Memory and Neural Computing #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph) #Quantum and electron transport phenomena
paper · pdf · doi:10.48550/arxiv.2310.20519
openalex publication_date 2023/10/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.