Quantum-Inspired Algorithm for Classical Spin Hamiltonians Based on Matrix Product Operators

Technische Samenvatting: Quantum-geïnspireerd Algoritme voor Klassieke Spin-Hamiltonianen gebaseerd op Matrix Product Operators

Probleemstelling
Het artikel behandelt de uitdaging van het oplossen van combinatorische optimalisatieproblemen (COP's) die zijn geformuleerd als klassieke spin-glas Hamiltonianen. Deze problemen, waaronder het vinden van de grondtoestanden van Ising-modellen met concurrerende interacties, zijn over het algemeen NP-hard vanwege de exponentiële grootte van de configuratieruimte en de aanwezigheid van frustratie. Klassieke heuristische methoden, zoals Simulated Annealing (SA) en Genetische Algoritmen, leveren vaak bijna optimale oplossingen, maar kunnen moeite hebben met complexe energielandschappen. Daarentegen zijn quantum-geïnspireerde algoritmen die gebruikmaken van tensornetwerken, zoals de Density-Matrix Renormalization Group (DMRG), efficiënt maar gevoelig voor het vastlopen in lokale minima, met name wanneer het energielandschap grote degeneraties vertoont.

Methodologie
De auteurs stellen een "powered-MPO" aanpak voor die spectrale filtering combineert met tensornetwerkrepresentaties om deze optimalisatieproblemen op klassieke hardware op te lossen. De methodologie verloopt via de volgende stappen:

1. Hamiltonian Transformatie: De kosten-Hamiltonian $\hat{H}$ wordt verschoven en geschaald om een nieuwe operator $\hat{G} = a\hat{H} + b\hat{I}$ te vormen. De parameters $a$ en $b$ worden gekozen zodat $\hat{G}$ positief semidefiniet is en de grondtoestanden van het oorspronkelijke probleem overeenkomen met de grootste eigenwaarden van $\hat{G}$.
2. Spectrale Amplificatie: De operator $\hat{G}$ wordt verheven tot een hoge macht $K$ (d.w.z. $\hat{G}^K$). Deze operatie versterkt exponentieel de relatieve gewichten van de configuraties met de grootste eigenwaarden (de grondtoestanden van $\hat{H}$) terwijl andere worden onderdrukt.
3. Tensornetwerk Representatie:
   • $\hat{G}$ wordt gerepresenteerd als een Matrix Product Operator (MPO).
   • De macht $\hat{G}^K$ wordt geconstrueerd via herhaalde MPO-MPO contracties. De auteurs maken gebruik van twee contractieschema's: een "lineair" schema (herhaaldelijk vermenigvuldigen met $\hat{G}$) en een "verdubbelingsschema" (het resultaat iteratief kwadrateren, $K=2^m$).
   • Tijdens de contractie wordt de bond-dimensie getrunceerd met behulp van Singular Value Decomposition (SVD) met een vaste drempelwaarde om de computationele kosten te beheersen, waarbij een maximale bond-dimensie $\chi$ behouden blijft.
4. Sampling: De resulterende powered MPO wordt in een Matrix Product State (MPS) ingebed door te werken op een uniforme superpositietoestand $|+\rangle^{\otimes N}$. Omdat $\hat{G}^K$ diagonaal is in de computationele basis, maakt deze embedding "perfecte sampling" van bitstrings mogelijk. De kans op het samplen van een configuratie is evenredig met het kwadraat van het bijbehorende diagonale element in $\hat{G}^K$, wat de output bias naar lage-energie toestanden stuurt.

Belangrijkste Bijdragen

• Trotter-vrije Spectrale Filtering: In tegenstelling tot quantum imaginary time evolution methoden die vertrouwen op gate-decompositie en Trotterisering, implementeert deze aanpak de niet-unitaire kostenfunctie direct in een enkele klassieke MPO, waardoor Trotter-fouten worden vermeden.
• Systematische Verbetering: Het artikel demonstreert dat, in tegen tegenstelling tot DMRG dat kan stagneren in lokale minima, de powered-MPO methode een meer systematische route naar verbetering biedt door de bond-dimensie $\chi$ te verhogen.
• Efficiënte Constructie: De auteurs beschrijven de constructie van de MPO voor algemene kostenfuncties en bieden theoretische grenzen aan de vereiste macht $K$ om een doel-succeskans te bereiken, waarbij zij aantonen dat $K$ omgekeerd evenredig schaalt met de spectrale kloof en logaritmisch met de dimensie van de Hilbertruimte.
• Hybride Scheduling: De studie identificeert complementaire sterktes tussen lineaire en verdubbelingscontractieschema's: verdubbeling zorgt voor snelle initiële filtering, terwijl lineaire evolutie stabiele, voortgezette verfijning biedt in latere stadia.

Resultaten
De auteurs hebben hun methode getest op twee klassen van problemen:

1. Edwards-Anderson Spin Glass Modellen: Getest op $D$-dimensionale hyperkubische roosters ($D=2, 3$).
   • De powered-MPO methode presteerde consequent beter dan DMRG, vooral wanneer DMRG werd geïnitialiseerd met een uniforme superpositietoestand, waarbij het vaak in lokale minima vastliep.
   • Terwijl de DMRG-resultaten weinig verbetering lieten zien bij een verhoogde bond-dimensie in deze gevallen, toonde de powered-MPO methode een systematische verbetering in de benaderingsratio naarmate $\chi$ toenam.
   • De methode identificeerde succesvol exacte grondtoestanden voor kleinere systeemgroottes en lage-energie configuraties voor grotere instanties (tot $N=400$ variabelen).
2. Hogere-orde Ising Modellen op Heavy-Hexagonal Lattices: Getest op roosters die relevant zijn voor huidige IBM quantum devices (HUBO-problemen met tot wel cubische interacties).
   • De powered-MPO methode (met $\chi=64$) presteerde beter dan Simulated Annealing (zowel standaard als orde-gereduceerde QUBO-formuleringen) bij het vinden van lagere energie configuraties.
   • De methode bleek robuust tegen de ruige energielandschappen die kenmerkend zijn voor deze problemen, waarbij het lineaire schema uiteindelijk de prestaties van het verdubbelingsschema overtrof bij hogere machten ($m \geq 12$).

Betekenis en Claims
Het artikel beweert dat deze quantum-geïnspireerde aanpak een robuuste klassieke baseline biedt voor het oplossen van combinatorische optimalisatieproblemen, waarbij het effectief door energielandschappen navigeert waar traditionele heuristieken en variatiemethoden zoals DMRG moeite mee hebben.

• Baseline voor Quantum Algoritmen: De auteurs stellen dat de hoogwaardige oplossingen gegenereerd door deze op tensornetwerken gebaseerde methode kunnen dienen als een cruciale benchmark voor het beoordelen van de bruikbaarheid en het voordeel van toekomstige quantumalgoritmen en hardware.
• Schaalbaarheid en Toekomstige Richtingen: De auteurs merken op dat hoewel de methode meer stappen vereist dan DMRG om te convergeren, het lokale vastlopen voorkomt. Ze suggereren dat toekomstig werk gebruik kan maken van MPI-niveau parallellisme en GPU-acceleratie om grotere bond-dimensies ($\chi \sim O(10^3)$) aan te kunnen. Bovendien stellen ze voor dat het uitbreiden van de methode naar tree tensor networks of het ontwikkelen van stabielere contractietechnieken voor Projected Entangled Pair Operators (PEPOs) de toepasbaarheid verder kan vergroten.
• Bescheiden Beperkingen: Het artikel erkent dat het bereiken van exacte oplossingen voor alle problemtypen nog steeds het overwinnen van hoge entanglement-barrières vereist, en dat de schaling van de vereiste bond-dimensie over verschillende probleemklassen nog verdere systematische verheldering behoeft. Er wordt ook opgemerkt dat huidige hardwarebeperkingen (qubit-aantallen en niet-lokale operaties) directe implementatie van de niet-unitaire kostenfunctie op huidige quantumcomputers verhinderen, hoewel het identificeren van shallow circuits om deze actie na te bootsen een toekomstige mogelijkheid blijft.