Introduction to QUDO, Tensor QUDO and HOBO formulations: Qudits, Equivalences, Knapsack Problem, Traveling Salesman Problem and Combinatorial Games

Dit artikel introduceert en bespreekt QUDO-, T-QUDO- en HOBO-vormuleringen voor combinatorische optimalisatie, waarbij hun expliciete coderingen en toepassingen op problemen zoals het rugzakprobleem en het reizend verkoperprobleem, evenals diverse logische spellen, worden gedemonstreerd om hun gebruik in quantum- en quantum-geïnspireerde algoritmen te faciliteren.

De kern

Stel je voor dat je probeert een enorm, ingewikkeld raadsel op te lossen. In de wereld van computers heet dit combinatorische optimalisatie. Het is alsof je probeert de enige beste manier te vinden om een reeks items te rangschikken om de hoogste score te behalen, terwijl je strikte regels volgt.

Al geruime tijd zijn computers geleerd om deze raadsels op te lossen met behulp van een specifieke taal genaamd QUBO (Quadratic Unconstrained Binary Optimization). Denk aan QUBO als een strenge taal waarbij elk stukje van het raadsel zich slechts in één van twee toestanden kan bevinden: AAN of UIT (zoals een lichtschakelaar). Hoewel dit voor veel dingen werkt, is het vaak alsof je probeert een complex schilderij te beschrijven met alleen maar zwart-wit pixels. Je moet duizenden kleine schakelaars gebruiken om slechts één kleur weer te geven, wat het raadsel enorm en moeilijk oplosbaar maakt.

Dit artikel introduceert drie nieuwe, flexibelere "talen" die computers toelaten om in rijkere kleuren te spreken, waardoor het gemakkelijker wordt om deze raadsels op te lossen. De auteur, Alejandro Mata Ali, laat zien hoe deze nieuwe talen werken aan de hand van beroemde wiskundeproblemen en logische spelletjes.

Hier is een uiteenzetting van de drie nieuwe talen en de spellen die gebruikt werden om ze te testen:

1. QUDO: De "Draaiknop" in plaats van de "Schakelaar"

Het Concept:
In de oude QUBO-taal zijn variabelen binaire schakelaars (0 of 1). QUDO (Quadratic Unconstrained D-ary Optimization) upgrade deze schakelaars naar draaiknoppen. In plaats van alleen AAN of UIT te zijn, kan een draaiknop worden ingesteld op elk getal van 0 tot een specifiek maximum (zoals een volumeknop die van 0 tot 10 gaat).

De Analogie:
Stel je voor dat je een koffer inpakt.

• QUBO-aanpak: Je moet voor elke enkele sok, elk overhemd en elk paar schoenen beslissen of je het meeneemt (1) of niet (0). Als je 5 overhemden wilt meenemen, heb je 5 aparte schakelaars nodig.
• QUDO-aanpak: Je hebt één enkele draaiknop voor "Overhemden". Je draait de knop gewoon op "5", en de computer weet dat je vijf overhemden meeneemt.

De Voorbeelden uit het Artikel:

• Het Rugzakprobleem: Dit is het klassieke "wat past er in de tas"-raadsel. Het artikel toont aan dat het gebruik van QUDO-draaiknoppen veel efficiënter is dan het gebruik van honderden binaire schakelaars om te tellen hoeveel items van elk type je meeneemt.
• Hashiwokakero (Bruggen): Een raadsel waarbij je eilanden met bruggen verbindt. Omdat je 0, 1 of 2 bruggen tussen eilanden kunt bouwen, past een draaiknop (0, 1 of 2) perfect bij het probleem, terwijl binaire schakelaars extra trucs vereisen om tot 2 te tellen.

2. T-QUDO: De "Slimme Relatie"-kaart

Het Concept:
Soms gaan de regels van een raadsel niet alleen over de waarde van één draaiknop, maar over de relatie tussen twee draaiknoppen. T-QUDO (Tensor QUDO) is een taal die deze complexe relaties direct begrijpt.

De Analogie:
Stel je voor dat je een feestje hebt waar je gasten moet plaatsen.

• QUDO: Je kunt de computer vertellen: "Gast A is blij als hij in Stoel 1 zit."
• T-QUDO: Je kunt de computer vertellen: "Gast A is blij als hij in Stoel 1 zit EN Gast B in Stoel 3 zit. Maar als Gast B in Stoel 4 zit, wordt Gast A boos."
  T-QUDO stelt de computer in staat om deze specifieke "als-dan"-koppelingen te begrijpen zonder dat ze hoeven te worden opgebroken in kleine, onhandige binaire stappen.

De Voorbeelden uit het Artikel:

• Het Probleem van de Reizende Handelaar: Een handelaar moet elke stad precies één keer bezoeken. T-QUDO maakt het gemakkelijk om te zeggen: "Als je op stap 1 in Stad A bent, kun je op stap 2 niet in Stad A zijn."
• N-Konijnen: Het doel is om konijnen op een schaakbord te plaatsen zodat ze elkaar niet aanvallen. T-QUDO behandelt de regel "Als Koningin A in Rij 1, Kolom 3 zit, dan kan Koningin B niet in Rij 2, Kolom 4 zitten" heel natuurlijk.
• Kakuro & Inshi no Heya: Dit zijn getalraadsels (zoals Sudoku maar met sommen en producten). T-QUDO stelt de computer in staat om sommen en producten van groepen getallen direct te controleren, in plaats van ze te forceren in binaire wiskunde.

3. HOBO: De "Groepsomhelzing"

Het Concept:
Soms gaat een regel over drie of meer variabelen die tegelijkertijd samenwerken. HOBO (Higher-Order Binary Optimization) is een taal die variabelen toestaat om in groepen te interageren, niet alleen in paren.

De Analogie:
Stel je voor dat je stoelendans speelt.

• Binair/Paarsgewijs: Je kunt alleen controleren of Persoon A naast Persoon B zit.
• HOBO: Je kunt controleren of Persoon A, Persoon B en Persoon C allemaal tegelijkertijd in een specifieke driehoeksvorm zitten. Het vangt de "groepsdynamiek" in één keer op.

Het Voorbeeld uit het Artikel:

• Peg Solitaire: Dit is het spel waarbij je pennen over elkaar heen springt om ze te verwijderen. Een zet betreft drie specifieke plekken: de startpen, de overgeslagen pen en de landingsplek. HOBO is perfect om deze driezijdige interactie in één stap te beschrijven, waardoor de oplossing veel schoner wordt.

Waarom is dit belangrijk?

Het artikel betoogt dat hoewel deze nieuwe talen (QUDO, T-QUDO, HOBO) complexer zijn om te leren dan de oude binaire taal, ze vaak veel efficiënter zijn voor specifieke soorten problemen.

• Minder Rommel: Ze gebruiken minder variabelen (minder "schakelaars" of "draaiknoppen") om hetzelfde probleem te beschrijven.
• Betere Hardware: Het artikel merkt op dat toekomstige quantumcomputers (die "qudits" gebruiken in plaats van alleen "qubits") worden gebouwd om deze talen van nature te spreken. Door problemen nu op deze manier te formuleren, bereiden we ons voor op die toekomstige hardware.
• De Ruil: Je kunt deze nieuwe talen terugvertalen naar de oude binaire taal (QUBO), maar dit maakt het probleem vaak groter en rommeliger. Het is alsof je een gedicht vertaalt van het Engels naar een taal met slechts 26 letters, en het vervolgens probeert terug te forceren naar het Engels – het verliest zijn elegantie.

Samenvatting

Het artikel is een handleiding voor wiskundigen en computerwetenschappers. Het zegt: "Stop met proberen elke complexe kwestie in een simpele AAN/UIT-doos te forceren. Soms heb je een draaiknop (QUDO), een relatiekaart (T-QUDO) of een groepsomhelzing (HOBO) nodig om het raadsel efficiënt op te lossen."

De auteur bewijst dit door moeilijke logische spelletjes (zoals Hashiwokakero, N-Konijnen en Peg Solitaire) te nemen en te laten zien hoe deze nieuwe formuleringen ze oplossen met minder middelen en duidelijkere regels dan de traditionele methoden.

Technische samenvatting

1. Probleemstelling

Combinatorische optimalisatieproblemen (zoals het Rugzakprobleem, de Reisende Verkoper en N-Konijnen) zijn vaak NP-moeilijk en missen efficiënte klassieke oplossingen. Hoewel de Quadratic Unconstrained Binary Optimization (QUBO)-formulering de standaard is voor het mappen van deze problemen naar quantumhardware (specifiek via de Ising-Hamiltoniaan en QAOA), kent deze beperkingen:

• Inefficiëntie van variabelen: Problemen met natuurlijke meerwaardige toestanden (bijvoorbeeld het selecteren van $k$ items uit $n$) vereisen binaire codering, wat het aantal variabelen verhoogt en ongeldige toestanden introduceert die straftermen vereisen.
• Beperkingen van constraints: Bepaalde logische constraints (bijvoorbeeld specifieke waarde-implicaties of het niet-samenvallen van specifieke waarden) zijn moeilijk of onmogelijk efficiënt te implementeren in standaard QUBO vanwege de binaire aard van de variabelen ($x_i^2 = x_i$).
• Mismatch met hardware: Opkomende quantumtechnologieën, zoals qudits (d-niveau quantum-systemen), bieden een natuurlijke manier om niet-binaire variabelen weer te geven, maar vereisen optimalisatieformuleringen die verder gaan dan QUBO.

Het paper adresseert de behoefte aan meer algemene formuleringen die qudits en hogere-orde interacties benutten om de resource-overhead te verminderen en de implementatie van constraints te vereenvoudigen.

2. Methodologie

De auteur introduceert en analyseert drie gegeneraliseerde optimalisatiekaders, waarbij expliciete wiskundige formuleringen worden geboden en hun toepassing op klassieke problemen en combinatorische spellen wordt aangetoond.

A. Quadratic Unconstrained D-ary Optimization (QUDO)

• Definitie: Een generalisatie van QUBO waarbij variabelen $x_i$ begrenste niet-negatieve gehele getallen zijn ($x_i \in \{0, 1, \dots, d_i-1\}$) in plaats van binair.
• Kostfunctie: $C(\vec{x}) = \sum_{i \le j} Q_{ij}x_i x_j + \sum D_i x_i$.
• Belangrijkste kenmerken:
  • Vereist qudits voor directe implementatie.
  • Staat lineaire termen toe (in tegenstelling tot pure QUBO waar $x_i^2=x_i$).
  • Beperkingen: Bepaalde constraints (bijvoorbeeld "als $x_i=a$ dan $x_j \neq b$") zijn moeilijk te implementeren omdat het teken van interactietermen afhangt van de specifieke waarden van niet-binaire variabelen.
  • Implementatie: Kan worden gemapt naar QAOA met behulp van qudit-fasengates $P(\theta)$ en gecontroleerde fasengates.

B. Tensor Quadratic Unconstrained D-ary Optimization (T-QUDO)

• Definitie: Een paarsgewijze categorische generalisatie van QUDO. Het behandelt variabelen als categorische labels in plaats van numerieke waarden.
• Kostfunctie: $C(\vec{x}) = \sum U_i(x_i) + \sum_{i<j} V_{ij}(x_i, x_j)$.
• Belangrijkste kenmerken:
  • Gebruikt een kosttensor $Q_{i,j, a, b}$ om de kost te definiëren van het toewijzen van waarde $a$ aan variabele $i$ en waarde $b$ aan variabele $j$.
  • Voordeel: Overwint de beperkingen van QUDO door complexe logische constraints (bijvoorbeeld specifieke waarde-implicaties, niet-samenvallen van specifieke waarden) eenvoudig te implementeren zonder te vertrouwen op rekenkundige eigenschappen.
  • Codering: Kan worden gecodeerd in HOBO of QUBO (via one-hot of binaire codering), hoewel dit het aantal variabelen kan verhogen.

C. Higher-Order Binary Optimization (HOBO)

• Definitie: Een formulering die gebruikmaakt van multilinear pseudo-Boolese functies van orde $m$ (waarbij $m > 2$).
• Kostfunctie: $C(\vec{y}) = \sum_{S} q_S \prod_{i \in S} y_i$, waarbij $y_i \in \{0, 1\}$.
• Belangrijkste kenmerken:
  • Staat interacties tussen meer dan twee variabelen toe.
  • Relatie met T-QUDO: T-QUDO-interacties kunnen worden gecodeerd in HOBO door qudit-labels te binariseren.
  • Implementatie: Direct toepasbaar op qubit-gebaseerde quantumapparatuur die hogere-orde interacties ondersteunt, of via reductietechnieken.

3. Belangrijkste bijdragen en casestudies

Het paper valideert deze formuleringen door ze toe te passen op het Rugzakprobleem, het Reisende Verkoper-probleem (TSP) en vijf combinatorische spellen.

Probleem	Gebruikte Formulering	Belangrijkste Inzicht/Resultaat
Rugzakprobleem	QUDO	Toont aanzienlijke reductie in resources aan. In plaats van binaire variabelen voor item-aantallen, vertegenwoordigt een enkele qudit per itemklasse het aantal direct. Vermindert het aantal benodigde variabelen en slack-variabelen ten opzichte van QUBO.
Hashiwokakero	QUDO	Modelleert brugverbindingen (0, 1 of 2) natuurlijk. Gebruikt hulpflow-variabelen (gecodeerd als qudits) om globale connectiviteit af te dwingen, wat bewijst dat QUDO complexe topologische constraints exact kan hanteren.
Reisende Verkoper (TSP)	T-QUDO	Gebruikt variabelen $x_t$ die de node op tijdstap $t$ vertegenwoordigen. De "geen-herhaling"-constraint wordt natuurlijk afgehandeld via een paarsgewijze strafterm $\delta_{x_t, x_{t'}}$, waardoor complexe coderingen met priemgetallen of enorme binaire matrices worden vermeden.
N-Konijnen	T-QUDO	Vermindert het aantal variabelen van $N^2$ (binair rooster) naar $N$ (kolomindex per rij). De T-QUDO-tensor codeert rij-, kolom- en diagonaalconstraints op natuurlijke wijze als specifieke tensor-ingangen, wat de structuur van de kostfunctie vereenvoudigt.
Kakuro	T-QUDO	Combineert QUDO (voor somconstraints) en T-QUDO (voor niet-herhalingsconstraints). De categorische aard van T-QUDO behandelt de regel "uniek nummer in een rij/kolom" perfect.
Inshi no Heya	T-QUDO	Hanteert multiplicatieve regioconstraints door producten om te zetten in sommen van priemexponenten (unaire functies), wat natuurlijk past binnen het T-QUDO-kader.
Peg Solitaire	HOBO	Modelleert het spel als een reeks toestanden. De bewegingslogica (springen over een peg) vereist interacties van 4 variabelen (bron, midden, bestemming, tijd), wat op natuurlijke wijze tot uitdrukking komt in HOBO zonder reductie naar kwadratische termen nodig te hebben.

4. Resultaten

• Resource-efficiëntie: QUDO- en T-QUDO-formuleringen vereisen vaak minder variabelen dan hun QUBO-tegenhangers. Bijvoorbeeld, N-Konijnen daalt van $N^2$ binaire variabelen naar $N$ qudits.
• Flexibiliteit van constraints: T-QUDO staat de directe implementatie toe van logische constraints (implicatie, niet-samenvallen) die in QUDO/QUBO lastig of onmogelijk zijn zonder hulpvariabelen.
• Haalbaarheid: Het paper biedt expliciete kostfuncties en straftermen voor alle voorbeelden, wat aantoont dat deze formuleringen wiskundig sound en "exact" zijn (d.w.z. geldige oplossingen hebben een kost van nul).
• Quantum-implementatie: De auteur schetst hoe deze kostfuncties in QAOA kunnen worden geïmplementeerd:
  • QUDO: Gebruikt single-qudit-fasengates en twee-qudit-gates.
  • T-QUDO: Gebruikt gecontroleerde focus-fasengates.
  • HOBO: Gebruikt multi-gecontroleerde fasengates (of reducties gebaseerd op ancilla's).

5. Betekenis

• Brug tussen theorie en hardware: Het paper dient als een praktische handleiding voor het benutten van opkomende qudit-gebaseerde quantumhardware, en gaat voorbij aan de binaire beperking van huidig qubit-gericht onderzoek.
• Algoritmische optimalisatie: Het toont aan dat het kiezen van de juiste formulering (QUDO/T-QUDO/HOBO) gebaseerd op de natuurlijke structuur van het probleem de complexiteit van het optimalisatielandschap drastisch kan verminderen, wat de prestaties van quantumalgoritmen zoals QAOA mogelijk kan verbeteren.
• Educatief kader: Door gebruik te maken van bekende spellen en puzzels, verlaagt het paper de instapdrempel voor het begrijpen van complexe hogere-orde en meerwaardige optimalisatieformalismen.
• Toekomstige richtingen: Het werk suggereert dat toekomstige quantumhardware-architecturen hogere-orde interacties en qudits natief moeten ondersteunen om combinatorische problemen efficiënter op te lossen dan huidige binaire-reductiemethoden toelaten.

Concluderend stelt het paper dat hoewel QUBO een krachtig hulpmiddel is, QUDO, T-QUDO en HOBO superieure efficiëntie en expressiviteit bieden voor specifieke klassen van combinatorische problemen, met name die welke meerwaardige variabelen of complexe logische constraints betreffen, en direct implementeerbaar zijn op quantumapparatuur van de volgende generatie.