Research map / Graph learning / GNN architectures
Quantum Positional Encodings for Graph Neural Networks
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Theoretical analysis of quantum-walk and Ising/XY-Hamiltonian-evolution graph features as positional encodings, relating their expressiveness to WL tests and showing limits on strongly regular graphs (text provided is only the theory section and appendix).
Problem
Quantum-computed positional encodings for GNNs need a principled expressiveness characterization relative to Weisfeiler-Lehman (WL) tests, especially on strongly regular graphs.
Approach
Relates single- and multi-walker XY-Hamiltonian quantum walks and uniform-field Ising evolutions to WL/k-WL hierarchies and Furer invariant, proving that Ising one- and two-body observables cannot distinguish non-isomorphic SRGs while XY quantum walks (2-QW) empirically can.
Key results
- Proves that uniform-field Ising one- and two-body occupation observables cannot distinguish non-isomorphic strongly regular graphs from the same family.
- Shows 1-QW with localized input is at least as strong as 1-WL and strictly weaker than the Furer invariant (hence weaker than 2-WL).
- Experimentally, Ising (p=2) and 2-QW correlation features distinguish all pairs of non-isomorphic SRGs in srg(25,12,5,6) and srg(26,10,3,4) families.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use a two-layer Ising evolution (p=2) | Graph distinguishability · srg(25,12,5,6) and srg(26,10,3,4) | distinguishability | Helped |
| Use a 2-quantum-walker XY evolution | Graph distinguishability · srg(25,12,5,6) and srg(26,10,3,4) | distinguishability | Helped |
| Use GD-WL with correlation-matrix edge features S(M) | GD-WL · srg(25,12,5,6) and srg(26,10,3,4) | pairwise distinguishability | Helped |
| Use total occupation, linear local occupation, or quadratic local occupation observables | Uniform-field Ising evolution · Non-isomorphic SRGs from the same family | distinguishability | Hurt |
| Use GD-WL with RRWP distance, including eigen-decomposition of the distance matrix | GD-WL · Non-isomorphic SRGs from the same family | distinguishability | Hurt |
| Use a uniform-superposition input state rather than a localized input state | 1-QW with XY Hamiltonian · Graph distinguishing expressiveness | expressiveness relative to 1-WL | Hurt |
Surprising findings
- Uniform-field Ising total-occupation and one/two-body observables fail to distinguish non-isomorphic SRGs, even though the Ising model is a candidate encoding.
- The paper notes that the claimed quantum advantage is conditional on k-WL relevance and that k-QW > k-WL is proven only for k=1 and observed for k=2.
Limitations
- Proof that k-QW is strictly more powerful than k-WL for general k is not established; only k=1 proven and k=2 observed on SRGs.
- Formal expressions only available for p=1 Ising; larger p requires costly simulation or quantum hardware.
- Quantum advantage is limited to datasets where large k in k-WL is relevant.
Experimental setup
Datasets: strongly regular graph families srg(25,12,5,6) and srg(26,10,3,4)
Metrics: permutation-invariant distance between correlation matrices
Baselines: 1-WL 2-WL 3-WL GD-WL with RRWP distance SPD-WL RD-WL
Builds on: Weisfeiler-Lehman test k-delta-LWL GD-WL Furer invariant
Closest papers by meaning
- On the Stability of Expressive Positional Encodings for Graphs (ICLR 2024 · similarity 0.86)
- Exploring channel distinguishability in local neighborhoods of the model space in quantum neural networks (ICLR 2025 · similarity 0.86)
- A Unified Theory of Quantum Neural Network Loss Landscapes (ICLR 2025 · similarity 0.86)
- Exponential Hardness of Optimization from the Locality in Quantum Neural Networks (AAAI 2024 · similarity 0.85)
- Beyond Oversquashing: Understanding Signal Propagation in GNNs Via Observables (NeurIPS 2026 · similarity 0.85)
- Exponential Quantum Communication Advantage in Distributed Inference and Learning (NeurIPS 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.