Qubit-efficient and gate-efficient encodings of graph partitioning problems for quantum optimization

Dit artikel introduceert een kwantum-optimatie-methode die grafenpartitieproblemen, zoals het minimaliseren van het aantal kleuren, efficiënter oplost door middel van een logaritmische binaire codering en een nieuw straffsysteem, wat leidt tot een aanzienlijke reductie in het aantal qubits en twee-qubit-poorten vergeleken met traditionele one-hot-coderingen.

De kern

Stel je voor dat je een enorme stad moet inrichten. Je hebt duizenden gebouwen (de punten in een grafiek) en je moet ze allemaal een kleur geven. Maar er is één belangrijke regel: twee gebouwen die direct naast elkaar staan, mogen nooit dezelfde kleur hebben.

Het doel is om te ontdekken: wat is het minimale aantal kleuren dat je nodig hebt om de hele stad te kleuren zonder dat de regels worden overtreden? Dit heet in de wiskunde het "Kleurenprobleem" (Graph Coloring), en het is een van die lastige puzzels die voor klassieke computers erg moeilijk zijn om snel op te lossen.

Deze paper introduceert een nieuwe, slimme manier om dit probleem op te lossen met quantumcomputers. Hier is de uitleg in gewone taal, met een paar creatieve vergelijkingen:

1. Het oude probleem: De "Eén-Per-Kaart" Methode

Vroeger (en vaak nog steeds) gebruikten quantum-onderzoekers een methode die we de One-Hot Encoding kunnen noemen.

• De Analogie: Stel je voor dat je voor elke kleur een eigen "wachtrij" hebt. Als je 10 kleuren hebt, heb je voor elk gebouw 10 wachtrijen. Je moet een vlaggetje in de juiste wachtrij steken om te zeggen: "Dit gebouw is blauw".
• Het Nadeel: Als je 100 gebouwen hebt en 10 kleuren, heb je 1000 wachtrijen (qubits) nodig. Dat is als een enorme parkeergarage die half leeg staat. Veel ruimte wordt verspild aan lege wachtrijen. Bovendien is het voor de quantumcomputer heel vermoeiend om al die wachtrijen tegelijk te controleren.

2. De nieuwe oplossing: De "Binaire Telefoon" Methode

De auteurs van dit paper hebben een veel slimmere manier bedacht, die ze Logaritmische Encoding noemen.

• De Analogie: In plaats van een wachtrij per kleur, geven we elk gebouw een klein telefoonnummer (in binaire code, zoals 010 of 111).
  • Met 10 kleuren hoef je niet 10 wachtrijen te hebben, maar slechts 4 cijfers (want $2^4 = 16$, wat genoeg is voor 10 kleuren).
  • Je gebruikt dus een telefoonnummer om de kleur aan te geven, in plaats van een hele wachtrij.
• Het Voordeel: Je hebt nu veel minder "telefoons" (qubits) nodig. Voor 100 gebouwen met 10 kleuren heb je in plaats van 1000 qubits nu maar ongeveer 400 nodig. Dat is een enorme besparing, alsof je van een parkeergarage voor 1000 auto's overschakelt op een slimme parkeergarage waar auto's op elkaar gestapeld kunnen worden.

3. Het slimme trucje: De "Lexicografische Boete"

Er is nog een probleem: Hoe weet de quantumcomputer dat hij moet proberen het minimale aantal kleuren te gebruiken? Hoe voorkom je dat hij gewoon zegt: "Oké, ik gebruik alle 10 kleuren, dat is makkelijker"?

De auteurs hebben een nieuw systeem bedacht dat ze een Lexicografische Boete noemen.

• De Analogie: Stel je voor dat je een lijst met cijfers hebt. De computer krijgt een boete als hij een "groot" cijfer (een hoge kleur) gebruikt, tenzij hij echt geen andere keuze heeft.
  • Het is alsof je een ladder hebt. De onderste sporten (kleuren 1, 2, 3) zijn goedkoop. De bovenste sporten (kleuren 8, 9, 10) zijn extreem duur.
  • De computer probeert dus van nature zo laag mogelijk op de ladder te blijven. Hij zal pas naar de 10e kleur gaan als hij écht niet anders kan.
  • Dit zorgt ervoor dat de computer automatisch de minimale oplossing vindt, zonder dat je extra ingewikkelde regels hoeft te schrijven.

4. Waarom is dit zo belangrijk?

De auteurs hebben dit getest op een echte quantumcomputer (een D-Wave machine).

• Snelheid: De nieuwe methode was veel sneller (tot wel 100 keer sneller) dan de oude methode.
• Stabiliteit: De oude methode creëerde veel "verwarring" in de quantumcomputer (zoals trillende touwtjes in een marionet). De nieuwe methode was rustiger en stabieler, waardoor de computer minder fouten maakte.
• Toekomst: Hoe groter het probleem wordt (hoe meer gebouwen je hebt), hoe groter het voordeel van deze nieuwe methode. Het is alsof je een fiets hebt voor een korte rit, maar een sneltrein voor een lange reis; de nieuwe methode is die sneltrein.

Samenvatting

Deze paper zegt eigenlijk: "Stop met het bouwen van enorme, inefficiënte parkeergarages (oude methode) om kleuren te tellen. Gebruik in plaats daarvan slimme telefoonnummers en een boetesysteem dat de computer dwingt om zuinig te zijn. Hierdoor kunnen quantumcomputers veel grotere en moeilijkere puzzels oplossen dan voorheen mogelijk was."

Dit is een grote stap voorwaarts om quantumcomputers echt bruikbaar te maken voor complexe problemen in de echte wereld, zoals het inrichten van netwerken, het plannen van routes of het ontdekken van gemeenschappen in sociale netwerken.

Technische samenvatting

Titel: Qubit- en gate-efficiënte coderingen van graf-partitieproblemen voor quantum-optimalisatie

Auteurs: Tristan Zaborniak, Prashanti Priya Angara, Vikram Khipple Mulligan, Hausi Müller, Ulrike Stege (Universiteit van Victoria en Flatiron Institute).

---

1. Het Probleem

Het paper richt zich op het oplossen van NP-hard combinatorische optimalisatieproblemen (COPs) op quantumhardware, met name een specifieke klasse van graf-partitieproblemen waarbij het doel is om het aantal gebruikte labels (partities) te minimaliseren.

• Voorbeelden: Minimale graf-kleuring (Minimum Graph Coloring), minimale $k$-snijding (Minimum $k$-cut) en community-detectie.
• De Uitdaging: In deze problemen krijgt elke hoek (vertex) een label uit een verzameling van $k$ mogelijke waarden. Het doel is niet alleen om een geldige toewijzing te vinden (waarbij buren verschillende labels hebben), maar specifiek om het aantal unieke labels dat nodig is te minimaliseren.
• Huidige Beperkingen: De standaardbenadering voor quantumoptimalisatie is one-hot encoding. Hierbij wordt elk van de $k$ labels vertegenwoordigd door $k$ bits (qubits), waarbij precies één bit per vertex op '1' staat. Dit leidt tot een lineaire overhead van $O(|V| \cdot k)$ qubits. Voor grote $k$ of grote grafen wordt dit een bottleneck voor huidige quantumhardware (zoals D-Wave annealers en gate-based systemen) vanwege het beperkte aantal qubits en de hoge foutkans.

2. Methodologie

De auteurs introduceren een nieuwe Higher-Order Unconstrained Binary Optimization (HUBO) formulering die gebruikmaakt van logaritmische codering in plaats van one-hot encoding.

A. Logaritmische Codering

In plaats van $k$ bits per vertex te gebruiken, coderen ze elk vertex met $\lceil \log_2 k \rceil$ bits.

• Dit reduceert het aantal qubits exponentieel ten opzichte van de one-hot methode.
• Het nadeel van logaritmische codering is dat het de interacties tussen variabelen van hogere orde maakt (niet langer kwadratisch), wat moeilijk is om direct op hardware uit te voeren die alleen kwadratische interacties ondersteunt (zoals QUBO).

B. Lexicografische Strafsysteem (Novelty)

Het grootste innovatieve aspect is de manier waarop het minimaliseren van het aantal labels wordt bereikt zonder extra indicator-variabelen.

• De auteurs introduceren een lexicografische strafterm ($H_{lexicographic}$) in de Hamiltoniaan.
• Ze wijzen een hiërarchie toe aan de bits binnen de binaire representatie van een label. De minst significante bit heeft de laagste straf, de meest significante bit de hoogste.
• Door de straffen $P_k$ zodanig te kiezen dat $P_{k+1} > |V| \cdot \sum_{j=1}^{k} P_j$, wordt gegarandeerd dat het optimalisatieproces eerst de meest significante bits minimaliseert.
• Resultaat: Een oplossing die een kleiner numeriek label gebruikt (en dus minder unieke labels in totaal), heeft een lagere energie. Dit "impliciet" minimaliseert het aantal partities zonder dat er aparte variabelen nodig zijn om te tellen hoeveel kleuren er gebruikt worden.

C. Theoretische Garantieën

De auteurs leiden proefbaar voldoende voorwaarden af voor alle strafcoëfficiënten (penalty coefficients):

1. Voor one-hot encoding: Voorwaarden voor $A_{one-hot}$, $A_{adjacency}$ en $A_{link}$ om te garanderen dat de laagste-energietoestand een geldige kleuring is met minimale kleuren.
2. Voor logaritmische encoding: Voorwaarden voor de lexicografische straffen $P_k$ en de adjacency-straf $A_{adjacency}$.
3. Voor kwadratization (Rosenberg-methode): Omdat quantumhardware vaak alleen kwadratische termen (QUBO) accepteert, moeten hogere-orde termen worden gereduceerd. De auteurs geven voorwaarden voor de straffen van de hulpvariabelen (auxiliary variables) die nodig zijn bij de Rosenberg-reductie, zodat de optimaliteit van de oplossing behouden blijft.

D. Gate-Complexiteit

Voor gate-based algoritmen (zoals QAOA) analyseren de auteurs het aantal twee-qubit gates (CNOTs):

• One-hot: $\Theta(|V|k^2 + |E|k)$
• Logaritmisch: $\Theta(|E| \cdot k \lceil \log_2 k \rceil)$
  Voor dunne grafen levert dit een bijna-exponentiële reductie op in het aantal gates.

3. Belangrijkste Bijdragen

1. Eerste werk voor optimalisatieversies: Dit is, voor zover bekend, het eerste werk dat de optimalisatieversies (minimaliseren van labels) van deze problemen in een quantumsetting behandelt, in plaats van alleen de beslissingsversies (kan het met $C$ kleuren?).
2. Nieuwe HUBO-formulering: Een qubit- en gate-efficiënte formulering die $\lceil \log_2 k \rceil$ bits per vertex gebruikt en een innovatief lexicografisch strafsysteem implementeert.
3. Rigoureuze Analyse: Het paper biedt een complete theoretische analyse van de strafcoëfficiënten, inclusief de impact van de reductie van HUBO naar QUBO via de Rosenberg-methode.
4. Empirisch Bewijs: Uitgebreide benchmarking op echte quantumhardware.

4. Resultaten

De auteurs hebben hun methode getest op een D-Wave Advantage2_1.11 quantum annealer met 350 willekeurige grafen (variërend in grootte en dichtheid).

• Time-to-Solution (TTS): De logaritmische encoding presteerde aanzienlijk beter dan de one-hot encoding. Voor grafen met ongeveer 20 knopen was de TTS 1 tot 2 orde van grootte lager (10x tot 100x sneller). Het voordeel nam toe naarmate de probleemgrootte groeide.
• Qubit-aantallen:
  • Voor de kwadratizatie (reductie naar QUBO) zijn er hulpvariabelen nodig. In zeer dichte grafen kan het totale aantal logische qubits na kwadratizatie hoger zijn dan bij one-hot, maar voor de meeste gevallen (vooral dunne grafen) blijft het lager.
  • Na "minor embedding" (het toewijzen aan fysieke qubits) waren de aantallen fysieke qubits vergelijkbaar tussen beide methoden.
• Ketenlengte Variatie (Chain Length Variance): Dit bleek de belangrijkste drijvende kracht achter de betere prestaties.
  • Bij one-hot encoding zijn de ketens (chains van qubits die één logische qubit vertegenwoordigen) vaak ongelijkmatig in lengte.
  • De logaritmische encoding resulteert in veel uniformere ketens.
  • Uniforme ketens maken het mogelijk om een optimale ketensterkte te kiezen die voor alle ketens werkt, wat de kans op ketenbreuken (chain breaks) door thermische ruis verkleint en de fideliteit van het probleem behoudt tijdens het annealing-proces.

5. Betekenis en Conclusie

Dit paper is significant omdat het een praktische weg wijst om grootschalige graf-partitieproblemen op huidige en toekomstige quantumhardware te kunnen oplossen.

• Efficiëntie: Het demonstreert dat logaritmische codering, gecombineerd met een slim strafsysteem, de beperkingen van het aantal qubits en de gate-complexiteit effectief kan omzeilen.
• Hardware-agnostisch: De methode is toepasbaar op zowel quantum annealing (D-Wave) als gate-based algoritmen (QAOA, VQE).
• Praktische Impact: De bevinding dat ketenuniformiteit (chain length uniformity) cruciaal is voor succesvolle quantum annealing, biedt waardevolle inzichten voor het ontwerp van toekomstige quantum-probleemformuleringen, zelfs als het totale aantal qubits niet drastisch daalt.

Kortom, de auteurs hebben een robuust, theoretisch onderbouwd en experimenteel gevalideerd raamwerk gepresenteerd dat de haalbaarheid van het oplossen van complexe optimalisatieproblemen op quantumcomputers aanzienlijk verbetert.