Technische Samenvatting: Kwantumvariatieve Benaderingen voor het Maximum Independent Set Probleem op Utility-schaal

Probleemstelling

Het Maximum Independent Set (MIS) probleem zoekt naar de grootste deelverzameling van knopen in een ongerichte graaf waarvoor geen twee knopen aan elkaar verbonden zijn. Het is een canoniek NP-zwaar probleem met toepassingen in frequentietoewijzing, proteïne-interactieanalyse en VLSI-ontwerp. Hoewel klassieke exacte solvers (branch-and-bound, integer programmeren) moeite hebben met harde instanties boven enkele honderd knopen, biedt quantum computing potentieel voor heuristieken. Echter, gate-gebaseerde variatieve algoritmen worden geconfronteerd met aanzienlijke uitdagingen in het Noisy Intermediate-Scale Quantum (NISQ) tijdperk, waaronder beperkte qubit-aantallen, korte coherentietijden en het "barren plateau"-fenomeen waarbij gradiënten exponentieel verdwijnen.

Een specifieke structurele uitdaging ontstaat bij grote, dichte grafen waar de MIS slechts een minuscuul fractie van de totale knopen beslaat (bijv. 15 van de 180 knopen). In dergelijke gevallen bezet de optimale oplossing een exponentieel kleine regio in de Hilbertruimte. Standaard benaderingen die initialiseren met een uniforme superpositie kennen een verwaarloosbare amplitude toe aan de MIS, wat vaak ertoe leidt dat variatieve circuits convergeren naar suboptimale energieniveaus waaruit ontsnapping zonder gecoördineerde multi-qubit wijzigingen moeilijk is.

Methodologie

De auteurs stellen een gelaagd framework voor dat circuit-preprocessing, variatieve optimalisatie en klassieke post-processing combineert om deze uitdagingen aan te pakken over drie benchmark-instanties: 64, 99 en 180 knopen.

1. Preprocessing en Circuitconstructie

• Vertex Reordering (Knopenherordening): Om de SWAP-overhead te minimaliseren en de efficiëntie van verstrengeling te verbeteren, vergelijken de auteurs drie herordeneringsstrategieën: Coupling-weighted BFS, Reverse Cuthill-McKee (RCM) en Spectral Reordering (met behulp van de Fiedler-vector). Spectral reordering wordt gekozen omdat het consequent andere strategieën overtreft op dichte instanties door structureel nabije knopen te groeperen, waardoor de indexafstand tussen sterk gekoppelde qubits wordt geminimaliseerd.
• Afstandsgebaseerde Sparsificatie: Toegepast specifiek op QAOA-circuits, verwijdert deze techniek langafstandsinteracties uit de circuitconstructie (waarbij alleen randen worden behouden waar $|i-j| \le k$) terwijl de energie wordt geëvalueerd met de volledige Hamiltonian. Dit vermindert de circuitdiepte aanzienlijk, waardoor simulaties hanteerbaar worden op Matrix Product State (MPS) simulators.
• Algoritmen: De studie vergelijkt de Variational Quantum Eigensolver (VQE) met een EfficientSU2 ansatz en het Quantum Approximate Optimization Algorithm (QAOA). Optimizers omvatten COBYLA en Simultaneous Perturbation Stochastic Approximation (SPSA). Het Conditional Value at Risk (CVaR) objectief wordt gebruikt om de optimalisatie te richten op de laagste-energie staart van de meetverdeling.

2. Klassieke Post-Processing Pipeline

Een twee-fasen klassieke bitstring-heuristiek zet ruwe kwantummetingen om in geldige MIS-kandidaten:

• History-Guided Suppression (Geschiedenisgestuurde Onderdrukking): Een Exponential Moving Average (EMA) houdt de frequentie bij waarmee qubits in de $|0\rangle$-toestand verkeren over de best presterende bitstrings. Dit genereert suppressie-masks om overgeselecteerde knopen (die de onafhankelijkheid schenden) te verwijderen en ondergeselecteerde knopen toe te voegen.
• Greedy Correction & Maximality Extension: Een twee-fasen greedy algoritme repareert eerst onhaalbare verzamelingen door knopen met hoge gewicht-schendingen te verwijderen, en breidt de verzameling vervolgens uit naar maximaliteit door compatibele knopen toe te voegen in oplopende volgorde van graad.

3. Ancilla-geassisteerde Superpositie-initialisatie (180-knopen Instantie)

Voor de 180-knopen instantie stagneert standaard VQE bij grootte 14 (de bekende MIS is 15). Om dit te overwinnen, introduceren de auteurs een nieuwe initialisatietechniek:

• Seed Selectie: Klassieke post-processing identificeert meerdere diverse, bijna-optimale grootte-14 onafhankelijke verzamelingen.
• Ancilla Superpositie: In plaats van te initialiseren vanuit een enkele seed of een uniforme superpositie, bereidt het circuit een uniforme kwantumsuperpositie van deze $m$ verschillende grootte-14 oplossingen voor met behulp van ancilla-qubits als een indexregister.
• Excitation-Preserving Ansatz: De toestand evolueert onder een ansatz bestaande uit fermionische simulatie (fSim) gates die de totale Hamming-gewicht (aantal excitaties) behouden. Dit beperkt de zoektocht tot de subspace van grootte-14 configuraties, waardoor de noodzaak voor straftermen (penalty terms) vervalt en het energielandschap verscherpt voor fijnmazige optimalisatie.
• Quantum-Parallel Search: De variatieve parameters worden collectief over alle seed-takken tegelijkertijd geoptimaliseerd. De resulterende distributie wordt vervolgens verwerkt door de klassieke heuristiek, die de grootte-14 verzamelingen kan uitbreiden naar de grootte-15 MIS.

Belangrijkste Resultaten

Benchmark-instanties (64, 99 en 180 knopen)

• 64-knopen Instantie: VQE met SPSA en CVaR slaagt erin alle 9 unieke gecertificeerde MIS (grootte 10) te herstellen over herhaalde runs. QAOA herstelt minder unieke verzamelingen (0–5 per run) en faalt om grootte 10 te bereiken met Strategie 2 (die alle herstelde verzamelingen naar maximaliteit drijft), wat het belang van oplossingsdiversiteit benadrukt.
• 99-knopen Instantie: VQE herstelt tot wel 10 unieke MIS (grootte 7) per run, waarbij een betekenend deel van de 56 gecertificeerde oplossingen wordt gesampled. QAOA wordt niet verder onderzocht vanwege de beperkingen van de MPS-simulator op het gebied van sparsificatie.
• 180-knopen Instantie: Standaard VQE (Fase 1) convergeert naar grootte 14 maar kan grootte 15 niet bereiken. De ancilla-geassisteerde Fase 3 (excitation-preserving VQE) ontdekt succesvol de grootte-15 MIS. Ablatie-studies bevestigen dat klassieke heuristieken toegepast op enkele seeds, of excitation-preserving circuits geïnitialiseerd vanuit enkele seeds, falen om de grootte-15 MIS te vinden. Alleen de multi-seed kwantumsuperpositie doorbreekt de lokale optimum-barrière.

Hardware Validatie (IBM Quantum ibm_marrakesh)

• VQE: Gebruikmakend van parameters die direct zijn overgedragen van een ruisvrije simulatie (geen hardware-reoptimalisatie), herstelt VQE ongeveer 50% van de ruisvrije MIS-diversiteit met 40% van het shot-budget. Voor de 64-knopen instantie werden 3 unieke MIS (grootte 10) gevonden; voor de 99-knopen instantie werden 5 unieke MIS (grootte 7) gevonden.
• QAOA: Onder hetzelfde parameter-transferprotocol herstelde QAOA nul geldige onafhankelijke verzamelingen op hardware. De auteurs schrijven dit toe aan het cumulatieve effect van beperkte circuitbandbreedte (vereist diepe SWAP-ketens), ondiepe klassieke optimalisatie en hardware-ruis.

Betekenis en Claims

Het artikel claimt de volgende bijdragen en betekenis:

1. Utility-Scale Simulatie: Naar weten van de auteurs is de 180-qubit MPS-simulatie de grootste schaal waarop gate-gebaseerde variatieve algoritmen het MIS-probleem tot optimaliteit hebben opgelost.
2. Methodologische Doorbraak: De primaire bijdrage is de ancilla superpositie techniek. Het biedt een principieel framework om lokale optima te doorbreken die zowel klassieke heuristieken als standaard variatieve benaderingen vangen. Door te initialiseren met een uniforme superpositie over meerdere bijna-optimale klassieke seeds en deze te laten evolueren onder een excitation-preserving ansatz, voert de methode een "hybride kwantum-klassieke parallelle zoektocht" uit. Dit maakt de ontdekking van oplossingen (grootte 15) mogelijk die ontoegankelijk zijn voor single-seed methoden.
3. Robuustheid tegen Ruis: De hardware-validatie demonstreert dat de bitstring-heuristiek pipeline robuust is onder realistische ruiscondities, waarbij een aanzienlijke oplossingsdiversiteit wordt hersteld zonder hardware-bewuste re-optimalisatie.
4. Bescheiden Claims over Kwantumvoordeel: De auteurs verklaren expliciet dat zij geen aanspraak maken op kwantumcomputationeel voordeel voor deze specifieke instanties. De bestudeerde circuits zijn klassiek efficiënt simuleerbaar via MPS (bond dimensie $\chi_{max} = 2$) vanwege hun lage verstrengelingsstructuur. De betekenis ligt in het demonstreren dat de methodologie werkt en een fundament legt voor toekomstige hardware-implementaties waar diepere ansätze en grotere seed-populaties een echt kwantumvoordeel kunnen opleveren.

Dit werk stelt vast dat de ontdekking van de MIS in de 180-knopen case een gevolg is van een kwantum-parallelle zoektocht over meerdere bijna-optimale initialisaties, in plaats van enkel de klassieke post-processing alleen. Dit framework wordt gepresenteerd als een schaalbare benadering voor combinatorische optimalisatieproblemen die een Ising-formulering toelaten.