Project Overview
This research explores Quantum Graph Neural Networks (QGNN) to overcome the classical limitations of Graph Neural Networks (GNN). We construct richer representation spaces through quantum superposition and entanglement, and implement Variational Quantum Algorithms (VQA) applicable to NISQ devices.
Key Experiments
Experiment 1: Isomorphism Verification
1-WL vs EQGC Quantum Invariants
Testing EQGC-based quantum invariants' ability to distinguish SRG pairs that 1-WL test cannot differentiate
- Toy Case: Successfully distinguished Cycle6 + chord
- SRG Case: Partial separation of Rook vs Shrikhande
Experiment 2: Laplacian λ₂ Approximation
Classical vs VQE-style Surrogate
Comparing algebraic connectivity λ₂ using classical power method and quantum circuit-based surrogate
- Classical λ₂: 3.6180 (stable convergence)
- VQE Surrogate: Loss → 0 convergence confirmed
Experiment 3: QAOA Optimization
Max-Cut Problem & Noise Analysis
Max-Cut optimization using QAOA and impact analysis of depolarizing/amplitude damping noise
- p=1 structure: ~57% stable performance
- Noisy environment: Significant performance degradation
Key Achievements
Core Experiments
Isomorphism, Laplacian, QAOA tests
Limitation Overcome
SRG distinction via EQGC confirmed
Practicality Verified
Performance analysis in noisy environments
Conclusions & Significance
🎯 Research Achievements
Empirically confirmed that quantum circuits can capture structural information different from classical message-passing approaches.
🔍 Technical Insights
QGNN shows potential to complement classical GNN expressiveness limitations, but technical challenges like noise, scale, and learning plateaus need resolution.
🚀 Future Directions
Verification of QGNN's practical applicability through real quantum hardware experiments and development of error mitigation techniques.