Iterative quantum algorithms for the minimum vertex cover problem based on continuous-time quantum walks

Technische Samenvatting: Iteratieve Kwantumalgoritmen voor het Minimum Vertex Cover gebaseerd op Continuous-Time Quantum Walks

Probleemstelling
Het artikel behandelt de Minimum Vertex Cover (MVC) en de Maximum Independent Set (MIS) problemen, wat canonieke NP-volledige combinatorische optimalisatietaken zijn. Gegeven een graaf $G=(V, E)$, is het doel om een subset van vertices van minimale grootte te vinden die alle randen dekt. De auteurs kaderen dit als een geconstraineerd optimalisatieprobleem waarbij de toegestane deelruimte bestaat uit bitstrings die voldoen aan de randvoorwaarden ($x_i + x_j \geq 1$ voor alle $(i,j) \in E$). Klassieke greed-heuristieken (bijv. Largest-Degree-First) worden beperkt door hun afhankelijkheid van de lokale graafstructuur, waardoor ze vaak globale correlaties missen. Daarentegen maken standaard kwantumbenaderingen zoals QAOA of VQE vaak gebruik van ongeconstraineerde Hamiltonians door middel van straftermen (penalty terms), wat leidt tot problemen met parameterinstelling en energielandschappen die bevolkt worden door ontoelaatbare toestanden met lage energie.

Methodologie
De auteurs stellen een constraint-preserving hybride kwantum-klassiek greedy framework voor dat straftermen en variationele training vermijdt. De kernmethodologie bestaat uit drie stadia:

1. Constraint-Preserving Operatoren:
   De toegestane deelruimte wordt gedefinieerd door geprojecteerde Pauli-X operatoren, $\hat{X}_i = \Pi_{N(i)} X_i$, waarbij $\Pi_{N(i)}$ projecteert op de deelruimte waar alle buren van vertex $i$ al in de cover zitten. Dit zorgt ervoor dat het omdraaien van een bit $i$ (het verwijderen uit de cover) alleen is toegestaan als dit geen enkele randvoorwaarde schendt. Deze operatoren genereren een continuous-time quantum walk (CTQW) Hamiltonian, $H_{MVC} = \sum_i \hat{X}_i$.

2. Geïnduceerde Feasible-State Graaf en CTQW:
   De dynamica van $H_{MVC}$ kan worden geïnterpreteerd als een CTQW op een geïnduceerde feasible-state graaf $G_{VC}(G)$. De vertices van deze graaf zijn geldige vertex covers, en randen verbinden covers die verschillen door een enkele, naar de haalbaarheid leidende bit-flip. De graaf is geworteld in de "all-in-the-cover" toestand ($\Omega = |1\rangle^{\otimes |V|}$) en is verbonden; de walk kan dus elke geldige cover bereiken vanaf $\Omega$. De walk verspreidt amplitude vanuit de wortel naar lagen met een afnemend Hamming-gewicht (kleinere covers).

3. Iteratieve Greedy Reductie:
   In plaats van te proberen direct een minimale cover te meten (wat het artikel laat zien exponentieel onderdrukt is in waarschijnlijkheid voor grote systemen), gebruikt het algoritme de CTQW-toestand om vertex scores te genereren die een recursieve klassieke reductie sturen:

   • Quantum Probabilistic Greedy (QPG): Scoort vertices op basis van hun marginale bezettingskans $P_v(t) = \langle \psi(t) | \Pi_v | \psi(t) \rangle$ in de CTQW-toestand.
   • Quantum Energy Greedy (QEG): Scoort vertices op basis van de verwachte cover-grootte verkregen door de walk te conditioneren op het fixeren van een specifieke vertex $v$ in de cover. Dit vere involves het draaien van een aparte geconditioneerde walk voor elke kandidaat-vertex.
   • Reductieregels: In elke stap selecteert het algoritme een vertex op basis van deze scores (ofwel de hoogste score om in de cover op te nemen, ofwel de laagste score om te verwijderen en de buren ervan op te nemen) en reduceert het de graaf. Het proces herhaalt zich totdat de graaf leeg is of klassiek oplosbaar is.

Belangrijkste Bijdragen

• Penalty-Free Framework: Het werk introduceert een methode die haalbaarheid afdwingt door constructie met behulp van geprojecteerde Pauli-operatoren, waardoor de noodzaak voor straftermen of variationele parameteroptimalisatie vervalt.
• Geïnduceerd Graafperspectief: Het vestigt dat de geconstraineerde dynamica overeenkomt met een verbonden, gelaagde graaf van geldige covers, wat een theoretische basis biedt voor waarom de walk de oplossingsruimte effectief verkent.
• Twee Kwantum-geïnformeerde Heuristieken: Het artikel definieert en benchmarkt de QPG en QEG algoritmen. QEG wordt benadrukt omdat het globale structurele informatie aggregeert door de impact op de kosten te evalueren wanneer een specifieke vertex wordt gefixeerd, terwijl QPG vertrouwt op lokale marginale waarschijnlijkheden.
• Low-Depth Robustheid: Het framework is ontworpen voor near-term devices. Voor grafen met een begrensde graad is de circuitdiepte van elke Trotter-laag onafhankelijk van de systeemgrootte. De auteurs demonstreren dat QEG een prestatie behoudt die dicht bij de exacte continue-tijd limiet ligt, zelfs onder lage-diepte Trotterisatie ($p=4$).

Resultaten
Numerieke benchmarks werden uitgevoerd op 3-reguliere, 4-reguliere en Erdős–Rényi willekeurige grafen ($n \in \{8, \dots, 20\}$).

• Prestaties: De kwantum-geïnformeerde algoritmen (met name QEG-LDF) bereiken lagere gemiddelde benaderingsratio's en lossen een groter deel van de instanties optimaal op vergeleken met klassieke greedy baselines (Greedy LDF, Greedy SDF) en de FastVC local-search heuristiek.
• Trotterisatie: Terwijl de prestaties van QPG significant degraderen bij lage Trotter-dieptes ($p=4$) vanwege de gevoeligheid voor fijnmazige waarschijnlijkheidscontrasten, blijft QEG robuust en dicht bij de exacte continue-tijd limiet. Dit suggereert dat QEG beter geschikt is voor hardware met een beperkte circuitdiepte.
• Walk Tijd: De algoritmen vereisen een specifieke walk tijd $t$ (gekalibreerd op onafhankelijke ensembles) om de scheiding tussen vertex scores te maximaliseren. De optimale tijd vindt meestal plaats nadat de wavefront de lagen heeft getransverteerd en interferentiepatronen een rangorde hebben gevestigd, in plaats van op het moment dat de wavefront de minimale cover-laag voor het eerst bereikt.

Betekenis en Claims
Het artikel claimt dat de primaire bruikbaarheid van het kwantumcomponent niet het direct outputten van een volledige oplossing is, maar het genereren van per-vertex scores die niet-lokale structurele informatie van de toegestane toestand coderen. Deze scores sturen een recursieve klassieke reductie aan, wat effectief geconstrangeerde kwantumverkenning combineert met klassieke vereenvoudiging.

De auteurs formuleren de betekenis bescheiden als volgt:

• De methode biedt een praktisch, penalty-vrij alternatief voor variationele algoritmen voor combinatorische optimalisatie.
• Het demonstreert dat constraint-preserving kwantum walks nuttige rangordes kunnen genereren voor greedy reductie, wat puur lokale klassieke heuristieken overtreft.
• Het werk identificeert een trade-off: op energie gebaseerde scores (QEG) bieden grotere robuustheid tegen Trotter-fouten ten koste van een hogere meet-overhead ($O(|V|)$ evaluaties per stap), terwijl waarschijnlijkheid gebaseerde scores (QPG) goedkoper maar gevoeliger zijn voor ruis.
• Het artikel concludeert dat de belangrijkste openstaande vraag niet is of dergelijke walks nuttige rangordes genereren, maar hoe de statistische scheiding tussen concurrerende scores schaalt met de probleemgrootte, wat het regime van praktisch voordeel zal bepalen.

De auteurs verklaren expliciet dat het framework niet beweert MVC in polynomiale tijd op te lossen of een kwantumversnelling voor exacte optimalisatie in de fault-tolerant zin te bieden; het biedt eerder een heuristische verbetering voor near-term hybride algoritmen.