Attributed-graphs kernel implementation using local detuning of neutral-atoms Rydberg Hamiltonian

Probleemstelling

Graph-gestructureerde data (zoals moleculen, sociale netwerken en code) zijn fundamenteel niet-Euclidisch, wat het moeilijk maakt om ze met klassieke vectorruimte-methoden te vergelijken. Hoewel exacte combinatorische methoden (zoals graf-isomorfisme) perfect onderscheidend vermogen bieden, zijn ze computationeel te duur voor grote grafen. Graf-kernels bieden een oplossing door grafen af te beelden in een Hilbert-ruimte, maar de meeste bestaande quantum-kernel-implementaties zijn beperkt tot niet-toegewezen grafen (unattributed graphs), waarbij alleen de structuur (knooppunten en kanten) wordt meegenomen en niet de eigenschappen van de knooppunten of kanten (zoals atoomtypes of bindingslengtes).

Het doel van dit onderzoek is om quantum-feature kernels uit te breiden naar toegewezen grafen (attributed graphs) en te demonstreren dat quantum hardware (specifiek neutrale-atoomprocessoren) kernels kan genereren die expressiever en performanter zijn dan klassieke tegenhangers.

Methodologie

De auteurs gebruiken een neutrale-atoom quantum processing unit (QPU) (van Pasqal) om grafen te simuleren via een Rydberg-Ising Hamiltoniaan. De methode omvat drie hoofdzakelijke innovaties:

1. Embedding van toegewezen grafen:

   • Randen (Edges): De connectiviteit van de graf wordt gecodeerd in de posities van de atomen. Atomen die verbonden zijn in de graf, worden dichter bij elkaar geplaatst zodat ze een sterke van-der-Waals interactie ($J_{ij}$) hebben.
   • Knooppunten (Nodes/Attributes): In tegenstelling tot eerdere werken die alleen globale detuning gebruikten, coderen de auteurs de knooppuntkenmerken (bijv. atoommassa's) in lokale detuningvelden ($\delta_i$) van de Hamiltoniaan. De lokale detuning wordt berekend op basis van de atoommassa ($m_i$) ten opzichte van koolstof ($m_C$), zoals beschreven in vergelijking (8). Dit zorgt ervoor dat de quantum-evolutie afhankelijk is van zowel de structuur als de chemische samenstelling van het molecuul.

2. Twee Quantum-Feature Kernels:

   • Quantum Evolution Kernel (QEK): Bestaande methode die gebruikmaakt van een globale observable (de excitatiekans $P_k(t)$ voor een vast aantal excitaties). Deze is permutatie-invariant maar mist lokale details.
   • Generalized-Distance Quantum-Correlation (GDQC) Kernel: Een nieuwe methode die gebruikmaakt van lokale observabelen (de correlatiematrix $C_{ij}(t) = \langle \hat{n}_i \hat{n}_j \rangle$). Deze kernel combineert de quantum-correlaties met de kortste-paadafstanden tussen knooppunten. Het is geïnspireerd op de klassieke Generalized-Distance Weisfeiler-Leman (GD-WL) kernel.

3. Pooling van tijdstappen:

   • In plaats van te vertrouwen op metingen op één enkel tijdstip, combineren de auteurs informatie uit meerdere stadia van de quantum-evolutie. Ze testen twee pooling-strategieën: som-pooling (lineaire combinatie) en product-pooling (Hadamard-product) van de kernels gegenereerd op verschillende tijdstippen.

De experimenten worden uitgevoerd via simulaties (emulatie) met de bibliotheken Pulser en EMU-MPS op twee standaard datasets: MUTAG (mutagene moleculen) en PTC_FM (toxische moleculen).

Belangrijkste Bijdragen

1. Implementatie van Attributed Graphs: De eerste demonstratie van het coderen van knooppuntattributen (via lokale detuning) in een neutrale-atoom Rydberg-systeem voor graf-kernels.
2. Theoretische en Empirische Expressiviteit: Bewijs dat het gebruik van lokale detuning de expressiviteit van de kernel verhoogt ten opzichte van globale detuning (Propositie 1). De lokale detuning maakt het mogelijk om grafen te onderscheiden die structuur-identiek zijn maar verschillende atoomtypes hebben.
3. De GDQC Kernel: Introductie van een nieuwe kernel gebaseerd op lokale correlaties, die bewezen is minstens zo expressief te zijn als de GD-WL kernel (Propositie 3) en voldoet aan alle eigenschappen van een geldige kernel (symmetrisch, positief semi-definit).
4. Pooling voor Prestatieverbetering: Demonstration dat het samenvoegen van informatie uit meerdere tijdstippen de prestaties aanzienlijk verbetert, waardoor quantum-kernels klassieke baselines kunnen overtreffen.

Resultaten

De prestaties werden gemeten met een Support Vector Machine (SVM) en de gewogen F1-score:

• Vergelijking met Klassieke Kernels: Zowel QEK als GDQC presteren concurrerend met de beste klassieke algoritmen (zoals Random Walk en Weisfeiler-Lehman optimal assignment).
• Invloed van Attributen: Kernels die gebruikmaken van lokale detuning (attributed) presteren over het algemeen beter dan die zonder (non-attributed), wat bevestigt dat het coderen van knooppuntkenmerken essentieel is voor deze taken.
• Invloed van Pooling: Dit is de belangrijkste bevinding. Door pooling toe te passen (vooral product-pooling over meerdere tijdstippen), overschrijden de quantum-feature kernels de prestaties van de beste klassieke baselines op beide datasets.
  • Op MUTAG bereikt de gepoolde GDQC(loc) een F1-score van 90,83%.
  • Op PTC_FM bereikt de gepoolde QEK(loc) een F1-score van 69,55%.
• Expressiviteit vs. Distinguishability: Analyse van de rang van de Gram-matrix toont aan dat lokale detuning een rijkere structuur van similariteit creëert dan globale detuning, wat leidt tot een beter onderscheidend vermogen tussen grafen.

Significantie en Conclusie

Dit werk markeert een belangrijke stap in quantum-versterkt machine learning voor grafen. Het toont aan dat:

1. Neutrale-atoom quantum hardware geschikt is voor het verwerken van complexe, toegewezen grafen (zoals moleculen) door gebruik te maken van lokale detuning.
2. Het gebruik van lokale observabelen (GDQC) en het combineren van tijdsinformatie (pooling) de expressiviteit van quantum-kernels kan maximaliseren.
3. Quantum-kernels niet alleen concurrerend zijn met state-of-the-art klassieke methoden, maar deze zelfs kunnen overtreffen wanneer de juiste kernel-architectuur en pooling-strategie worden toegepast.

Hoewel er geen asymptotische snelheidswinst wordt geclaimd ten opzichte van klassieke algoritmen (de complexiteit is nog steeds hoog door de simulatie en het aantal shots), biedt de empirische prestatieverbetering een sterke motivatie voor het gebruik van quantum hardware in toekomstige graf-machine learning toepassingen, vooral in domeinen zoals chemie en farmacologie.