Probabilistic modeling over permutations using quantum computers

Titel: Probabilistische modellering over permutaties met behulp van quantumcomputers

Auteurs: Vasilis Belis et al. (Xanadu, Universiteit van Triëst, CERN, INFN)
Datum: 25 maart 2026

1. Het Probleem

Probabilistische modellering over permutaties (de rangschikking van $n$ objecten) is een fundamenteel probleem in toepassingen zoals multi-object tracking en aanbevelingssystemen. Wiskundig valt dit binnen het kader van niet-commutatieve harmonische analyse op de symmetrische groep $S_n$.

De kernuitdagingen zijn:

• Exponentiële complexiteit: De grootte van de ruimte van permutaties is $n!$. Klassieke methoden vereisen geheugen en rekentijd die super-exponentieel schalen ($O(n! n^2)$ voor FFT over $S_n$).
• Bandbreedte-beperkingen: Om klassiek haalbaar te zijn, moeten modellen worden beperkt tot "lage frequenties" (band-limited), wat betekent dat alleen lage-orde correlaties worden gemodelleerd. Hoge-orde interacties gaan verloren.
• Intractable Fourier-transformaties: Het schakelen tussen de directe ruimte (permutaties) en de Fourier-ruimte (spectrale representatie) is klassiek ondoenlijk vanwege de super-exponentiële kosten van de Fast Fourier Transform (FFT) over $S_n$.

2. Methodologie

De auteurs stellen een quantumalgoritme voor dat gebruikmaakt van de Quantum Fourier Transform (QFT) over de symmetrische groep $S_n$ om een exact probabilistisch model te coderen zonder de noodzaak van band-limited benaderingen.

Kerncomponenten:

• Codering: Permutaties worden gecodeerd in computatie-basisstaten $|\sigma\rangle$ met behulp van Lehmer-codes, wat $O(n \log n)$ qubits vereist.
• Markov-keten dynamiek: Het model evolueert via een Markov-keten bestaande uit twee afwisselende operaties:
  1. Diffusie: Een groep-equivariante convolutie (een random walk op de Cayley-grafiek van $S_n$) die de onzekerheid verhoogt. In de Fourier-ruimte werkt dit als een diagonale vermenigvuldiging.
  2. Conditionering: Een Bayesiaanse update op basis van waarnemingen (data) die de waarschijnlijkheidsmassa concentreert. Dit werkt als een punt-voor-punt vermenigvuldiging in de directe ruimte.
• Quantum Schakeling: Het algoritme wisselt efficiënt tussen directe en Fourier-ruimte met de QFT over $S_n$, die een runtime heeft van $O(n^3 \log n)$ (super-exponentiële versnelling ten opzichte van klassiek).
• Implementatie van Operatoren:
  • Diffusie: Geïmplementeerd via block-encoding van de diffusiekernel in de Fourier-ruimte. Omdat de kernel een klasse-functie is, is de Fourier-transformatie diagonaal, wat de implementatie vereenvoudigt.
  • Conditionering: Geïmplementeerd via block-encoding in de directe ruimte. Voor specifieke observaties (zoals partiële toewijzingen of rangschikkingen) wordt een "reorder-update" strategie gebruikt. Hierbij worden qubits herschikt (via unitaire transformaties) zodat de relevante constraints lokaal kunnen worden gecontroleerd zonder complexe globale operaties.
• Amplitude Amplification: Omdat diffusie en conditionering niet-unitair zijn, worden ze uitgevoerd met behulp van ancilla-qubits. Aan het einde van het proces wordt Amplitude Amplification (of Fixed-Point Amplitude Amplification) gebruikt om de kans op het succesvol meten van de gewenste toestand te maximaliseren.

3. Belangrijkste Bijdragen

1. Exact Quantum Model: Het eerste voorstel om een exact probabilistisch model over $S_n$ te coderen in de amplitude van een quantumtoestand, zonder de klassieke beperkingen van band-limited benaderingen.
2. Efficiënte Block-encoding: Een methode om de diffusie- en conditioneringsoperatoren efficiënt te implementeren via block-encoding en QFT, waarbij de complexiteit wordt gedomineerd door de QFT-runtime ($O(n^3 \log n)$).
3. Scalabiliteitsanalyse: Een rigoureuze analyse van de succeskans (overlap) van de operatoren. De auteurs bewijzen dat de succeskans onderaan wordt begrensd door een constante of een polynoom in $n$, afhankelijk van de "lazy walk" parameters, wat het algoritme asymptotisch haalbaar maakt.
4. Twee Coderingsstrategieën:
   • Amplitude Encoding: De amplitude is evenredig met de waarschijnlijkheid $h(\sigma)$. Meting levert monsters op volgens $|h(\sigma)|^2$ (een scherper, maar vertekend, posterior).
   • Born Encoding: De amplitude is evenredig met $\sqrt{h(\sigma)}$. Meting levert monsters op volgens het ware posterior $h(\sigma)$. Dit vereist een niet-Markovische dynamiek voor de diffusiestap.
5. Toepassingsmogelijkheden: Het algoritme maakt generatieve modellering, steekproeven in Fourier-ruimte en Maximum-A-Posteriori (MAP) schattingen mogelijk via polynoomfiltering (QSVT) om de waarschijnlijkheidspieken te versterken.

4. Resultaten en Prestaties

• Complexiteit: Het algoritme bereikt een super-exponentiële versnelling ten opzichte van klassieke exacte methoden voor het uitvoeren van inferentie over permutaties. De runtime wordt gedomineerd door de QFT ($O(n^3 \log n)$) in plaats van $O(n! n^2)$.
• Succeskans: De analyse toont aan dat voor redelijke parameters (bijv. $p > 1/2$ voor de lazy walk) de succeskans van de diffusiestap constant blijft, ongeacht $n$. Voor algemene rationale waarden is de kans begrensd door een polynoom in $n$, wat voldoende is voor amplitudeversterking.
• Praktische Schaal: Hoewel het theoretisch voor grote $n$ werkt, wordt geschat dat de meest praktische toepassing ligt in het bereik van $n \approx 15$ tot $30$, waar klassieke simulaties onmogelijk zijn, maar quantumhardware (met fouttolerantie) nog haalbaar is.

5. Betekenis en Toekomstperspectief

• Nieuw Toepassingsgebied voor QFT: Dit werk positioneert de QFT over de symmetrische groep niet als een oplossing voor het Graph Isomorphism-probleem (zoals eerder gehoopt), maar als een krachtig gereedschap voor machine learning en statistische analyse over groepsstructuren.
• Spectrale Methoden voor ML: Het demonstreert dat quantumcomputers spectrale methoden kunnen unlocken voor probabilistische modellering, waarbij de interactiecomplexiteit wordt geregeld door de frequentiecomponenten van het spectrum.
• Feasibility Study: Het artikel fungeert als een haalbaarheidsstudie. De volgende stap is het uitvoeren van numerieke experimenten op realistische datasets om de prestaties te valideren en de constante factoren in de gate-complexiteit te optimaliseren voor toekomstige quantumhardware.

Conclusie:
De auteurs tonen aan dat quantumcomputers, door gebruik te maken van de efficiënte QFT over $S_n$, in staat zijn om complexe probabilistische modellen over permutaties exact te hanteren. Dit opent de deur tot het oplossen van klassiek onoplosbare inferentieproblemen in gebieden zoals object-tracking en aanbevelingssystemen, en markeert een belangrijke stap in de ontwikkeling van niet-Abelse quantumalgoritmen voor machine learning.