  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.
