A QUBO Formulation for the Generalized LinkedIn Queens and Takuzu/Tango Game

Dit artikel presenteert een veelzijdige QUBO-formulering voor het oplossen van gegeneraliseerde versies van logische puzzels zoals de LinkedIn Queens, Takuzu en Tango-spellen, introduceert bovendien nieuwe op schaak gebaseerde problemen en optimaliseert het model voor uitvoering op quantumhardware via Quantum Annealing of QAOA.

De kern

Stel je voor dat je een meester-puzzelontwerper bent die probeert een zeer specifieke, supersnelle robot te leren hoe ze logische spellen moet oplossen. Dit artikel is in essentie een "handleiding" geschreven in een speciale code genaamd QUBO (Quadratische Ongedwongen Binaire Optimalisatie). Denk aan QUBO als een universele taal die kwantumcomputers begrijpen, waarbij elke regel van een spel wordt vertaald naar een wiskundige "energiekost". Het doel van de robot is om de rangschikking van stukken te vinden die resulteert in de laagst mogelijke energie (nul kost), wat overeenkomt met de perfecte oplossing.

Hier is een uiteenzetting van de belangrijkste ideeën uit het artikel met behulp van alledaagse analogieën:

1. Het Kernconcept: Het "Energie"-spel

De auteurs nemen populaire logische puzzels en herschrijven hun regels zodat een kwantumcomputer ze kan oplossen.

• De Metafoor: Stel je een heuvelachtig landschap voor waar elke mogelijke rangschikking van een puzzel een punt op de kaart is. Een "slechte" rangschikking (waar regels worden overtreden) is een hoge bergtop. Een "perfecte" rangschikking is een diepe vallei. De QUBO-formule is een kaart die de kwantumcomputer precies vertelt hoe steil de heuvels zijn. De computer "rolt bergafwaarts" totdat het de diepste vallei vindt, wat de oplossing is.

2. De Koningin-spellen (LinkedIn & N-Koninginnen)

Het klassieke N-Koninginnen-probleem vraagt je om $N$ koninginnen op een schaakbord te plaatsen zodat ze elkaar niet kunnen aanvallen.

• De Oude Regel: Koninginnen mogen geen rij, kolom of enkele diagonale lijn delen.
• De LinkedIn-draai: Het artikel kijkt naar een nieuwere versie (LinkedIn-koninginnen) waarbij de diagonale regel "zachter" is. Koninginnen kunnen elkaar niet aanvallen als ze direct naast elkaar diagonaal staan, maar ze kunnen koninginnen die verder weg zijn negeren. Bovendien is het bord verdeeld in gekleurde regio's, en moet je precies één koningin in elke regio plaatsen.
• De Bijdrage van het Artikel: De auteurs creëerden een flexibele "recept" (QUBO-formulering) dat kan omgaan met:
  • Standaard N-Koninginnen.
  • De zachtere regels van LinkedIn.
  • Onregelmatige bordvormen (zoals een bord met ontbrekende hoeken).
  • Borden die rondlopen als een donut (Toraal), waarbij een stuk dat de rechterrand verlaat, opnieuw verschijnt aan de linkerkant.
  • Het "Tenten & Bomen"-spel: Ze pasten hun recept aan voor een spel waarbij je tenten naast bomen moet plaatsen zonder dat tenten elkaar raken, zelfs niet diagonaal.

3. De "Schaakstuk"-uitbreiding

De auteurs beseften dat hun recept niet alleen voor Koninginnen gold. Ze generaliseerden het voor elk schaakstuk.

• Het Gekleurde Schaakstuk-probleem: Stel je een bord voor waar verschillende gekleurde zones elk precies één stuk moeten bevatten. De stukken kunnen Toren, Loper of Paard zijn, en ze hebben verschillende manieren van bewegen. Het doel is om er zoveel mogelijk in te passen zonder dat ze elkaar bedreigen.
• Het Maximaal Schaakstuk-probleem: Hier is het doel simpelweg om het bord vol te proppen met zoveel mogelijk stukken zonder dat ze elkaar aanvallen. De auteurs voegden een "beloning" toe aan hun wiskundige formule: elke keer dat je succesvol een stuk plaatst, daalt de energie een beetje, wat de computer aanmoedigt om het bord te vullen.

4. De Takuzu- en Tango-spellen

Dit zijn raster-vullende spellen (zoals Sudoku, maar met 0'en en 1'en, of Zonnen en Manen).

• De Regels:
  1. Elke rij en kolom moet een gelijk aantal 0'en en 1'en hebben.
  2. Je mag niet drie dezelfde symbolen op een rij hebben (geen "000" of "111").
  3. Tango (LinkedIn's versie): Voegt speciale symbolen tussen cellen toe. Een "=" betekent dat de twee cellen hetzelfde moeten zijn; een "x" betekent dat ze verschillend moeten zijn.
  4. Klassieke Takuzu: Voegt een harde regel toe dat geen twee rijen identiek mogen zijn, en geen twee kolommen identiek mogen zijn.
• De Doorbraak van het Artikel:
  • Ze creëerden een perfecte QUBO-recept voor Tango en de lokale regels van Takuzu.
  • Het Moeilijke Deel: De "geen identieke rijen"-regel in klassieke Takuzu is lastig voor kwantumcomputers. De auteurs losten dit op door "Getuigevariabelen" in te voeren.
  • De Analogie: Stel je twee rijen mensen voor en je moet bewijzen dat ze verschillend zijn. Je huurt een "getuige" in voor elk paar rijen. De taak van de getuige is om precies één kolom aan te wijzen waar de twee rijen verschillen. Als de getuige geen verschil kan vinden, gaat de straf (energie) omhoog. Dit stelt de kwantumcomputer in staat om de "geen identieke rijen"-regel perfect af te dwingen zonder extra "slak"-variabelen te nodig hebben die middelen verspillen.

5. Waarom Dit Belangrijk Is (Volgens het Artikel)

Het artikel beweert niet dat deze puzzels ziektes zullen genezen of de beursvoorspellingen zullen doen. In plaats daarvan claimt het een universele toolkit te bieden om deze specifieke logische puzzels om te zetten in een formaat dat kwantumhardware (zoals D-Wave-machines) of kwantumalgoritmen (zoals QAOA) daadwerkelijk kunnen uitvoeren.

• Optimalisatie: Het lukte hen om het aantal "variabelen" (het aantal schakelaars dat de computer moet omzetten) en interacties te verminderen, waardoor de problemen kleiner worden en waarschijnlijker op huidige kwantumcomputers passen.
• Flexibiliteit: Hun formules kunnen omgaan met rare bordvormen, verschillende aantallen stukken per rij, en zelfs borden die in cirkels rondlopen.

Samenvattend:
De auteurs namen een aantal populaire logische spellen (Koninginnen, Tenten, Takuzu, Tango) en schreven één enkele, aanpasbare "vertalgids" die hun regels omzet in een taal die kwantumcomputers kunnen spreken. Ze bedachten ook een slimme truc met "getuigen" om het moeilijkste deel van de Takuzu-puzzel op te lossen, zodat de oplossing wiskundig perfect is.

Technische samenvatting

1. Probleemdefinitie

Het artikel behandelt de uitdaging om diverse combinatorische logische puzzels op te lossen met behulp van Quantum Annealing en het Quantum Approximate Optimization Algorithm (QAOA). Deze algoritmen vereisen dat problemen worden geformuleerd als Quadratic Unconstrained Binary Optimization (QUBO)-problemen. De auteurs richten zich op het generaliseren en verenigen van de QUBO-formuleringen voor verschillende specifieke spellen:

• N-Queens & LinkedIn Queens (LQueens): Het klassieke N-Queens-probleem (het plaatsen van $N$ koninginnen op een $N \times N$ bord zonder wederzijdse aanvallen) en de LinkedIn-variant, die diagonale beperkingen versoepelt tot alleen "aangrenzende" diagonalen en gebiedsgebonden beperkingen toevoegt (één koningin per gekleurd gebied).
• Takuzu (Binairo) & Tango: Logische puzzels waarbij een rooster moet worden gevuld met 0'en en 1'en (of zonnen en manen) onderworpen aan beperkingen: gelijke aantallen 0'en en 1'en per rij/column, niet meer dan twee identieke opeenvolgende waarden, en unieke rijen/columns (voor Takuzu). Tango voegt specifieke gelijkheids- ("=") en ongelijkheids- ("x") beperkingen tussen cellen toe.
• Extensies: Het artikel introduceert ook formuleringen voor Tents & Trees, Gekleurde Schaakstukproblemen en het Max Chess Pieces Problem.

2. Methodologie

De kernmethodologie bestaat uit het vertalen van de logische beperkingen van deze spellen naar kwadratische straffuncties. De auteurs maken gebruik van standaard binaire variabele-identiteiten ($x^2 = x$) om ervoor te zorgen dat alle termen kwadratisch blijven.

Belangrijke technische componenten:

• Straf voor beperkingen: De auteurs definiëren standaard straftermen voor:
  • Exacte aantallen: $(s - k)^2$ om precies $k$ actieve variabelen af te dwingen.
  • Ten hoogste één: $\sum x_i x_j$ om gelijktijdige activering te voorkomen.
  • Opeenvolgende waarden: Straffen voor patronen zoals 000 of 111 met behulp van $(s-1)(s-2)$.
  • Gelijkheid/Ongelijkheid: $(x-y)^2$ en $(x+y-1)^2$.
• Conflictdiagrammen: In plaats van diagonale beperkingen te behandelen als complexe gebieden, modelleren de auteurs deze als conflictdiagrammen waarbij randen verboden gelijktijdige activeringen vertegenwoordigen. Deze aanpak blijkt rigorieuzer en efficiënter te zijn voor variaties van N-Queens.
• Preprocessing & Variabele Reductie:
  • Vaste variabelen: Vooraf geplaatste stukken (aanwijzingen) worden vastgezet op 0 of 1, en hun conflicterende buren worden vastgezet op 0, wat het aantal optimalisatievariabelen vermindert.
  • Pariteitsreductie (Takuzu/Tango): Voor "=" en "x" beperkingen stellen de auteurs een Union-Find-structuur met pariteit voor. Dit vermindert het aantal vrije variabelen door afhankelijke cellen uit te drukken als $x_v = y_C \oplus \pi_v$, waarbij $y_C$ een representatieve variabele is voor een samenhangend component.
• Omgaan met globale uniciteit (Takuzu): Klassiek Takuzu vereist dat geen twee rijen of kolommen identiek zijn. Standaard lokale straffen kunnen dit niet afdwingen. De auteurs introduceren getuigevariabelen ($u_{rsj}$) om te certificeren dat voor elk paar rijen $r, s$ er ten minste één kolom $j$ bestaat waarin ze verschillen. Dit creëert een exacte QUBO-formulering zonder slack-variabelen, hoewel dit het aantal variabelen verhoogt tot $O(N^3)$.

3. Belangrijkste bijdragen

A. Generaliseerd N-Queens-kader

De auteurs stellen een verenigde QUBO-formulering voor N-Queens voor die ondersteuning biedt voor:

• Variabele aantallen koninginnen per rij/kolom.
• "Zachte" gebieden (waarbij 0 of 1 koningin is toegestaan) en overlappende gebieden.
• Toroidale borden (waarbij randen omwikkelen).
• Cruciaal inzicht: Zij tonen aan dat diagonale beperkingen het beste worden gemodelleerd als paarwijze conflictdiagrammen in plaats van gebiedsgebonden "ten hoogste één"-beperkingen, waardoor de exactheid van de oplossingsruimte behouden blijft.

B. Exacte Takuzu/Tango-formulering

• Lokaal versus globaal: Zij onderscheiden tussen het "lokale" TTP (Takuzu/Tango-probleem), dat rijbalans en herhalingsbeperkingen behandelt, en de "globale" uniciteitsbeperking.
• Constructie van getuigevariabelen: Zij presenteren een nieuwe methode om rij/kolom-uniciteit in Takuzu af te dwingen met behulp van hulpvariabelen (getuigevariabelen). Dit maakt een exacte QUBO-formulering voor klassiek Takuzu mogelijk, wat eerder moeilijk te bereiken was zonder versoepeling of slack-variabelen.
• Generalisaties: Zij breiden Takuzu uit tot onbalansregulering (verschillende aantallen 0'en/1'en), diagonale herhalingsbeperkingen en gelijkheids/ongelijkheidsymbolen op lange afstand.

C. Nieuwe probleemdefinities

• Gekleurd Schaakstukprobleem: Een generalisatie waarbij verschillende stuktypes (met verschillende zetsets) zo moeten worden geplaatst dat geen enkel stuk een ander bedreigt, met één stuk per gekleurd gebied.
• Max Chess Pieces Problem: Een optimalisatieprobleem om het maximale aantal niet-conflicterende stukken op een bord te plaatsen, geformuleerd met een beloningsterm ($-\sum w_{ij}x_{ij}$) en een conflictpenalty.
• Exact Tents & Trees: Zij bieden een exacte QUBO voor Tents & Trees met behulp van toewijzingsvariabelen ($y_{t,c}$) om bomen te koppelen aan tenten, waardoor de onnauwkeurigheden van vereenvoudigde versoepelingsmethoden worden vermeden.

4. Resultaten en theoretische analyse

• Exactheid: Het artikel bewijst dat de voorgestelde formuleringen exact zijn.
  • Voor LinkedIn Queens zorgt preprocessing ervoor dat de gereduceerde QUBO overeenkomt met de oplossingsruimte van het oorspronkelijke probleem.
  • Voor Takuzu garandeert de methode met getuigevariabelen dat elke toestand met nul-energie overeenkomt met een geldige oplossing met unieke rijen en kolommen.
  • Voor Max Chess Pieces bewijzen de auteurs dat als de strafcoëfficiënt $\lambda$ voor conflicten groter is dan het maximale beloningsgewicht, geen enkele globale minimizer conflicterende stukken zal bevatten.
• Complexiteit:
  • De standaard lokale Takuzu-formulering schaalt met de bordgrootte ($O(N^2)$ variabelen).
  • De exacte Takuzu-formulering met getuigevariabelen schaalt als $O(N^3)$ vanwege de $2N^2(N-1)$ hulpvariabelen die nodig zijn om uniciteit af te dwingen.
• Optimalisatie: Het gebruik van "fractionele" straftermen (bijv. $(s - (q+0.5))^2$) wordt benadrukt als een techniek om het aantal variabelen te verminderen (het vermijden van slack-variabelen) terwijl slechts een constante energieverschuiving wordt geïntroduceerd die de minimalizers niet beïnvloedt.

5. Betekenis

• Klaarheid voor quantumhardware: Door rigoureuze, exacte QUBO-formuleringen te bieden, overbrugt het artikel de kloof tussen abstracte logische puzzels en praktische implementatie op quantumannealers (zoals D-Wave) en poortgebaseerde quantumcomputers (via QAOA).
• Verenigd kader: Het werk toont aan dat diverse puzzeltypes (Queens, Takuzu, Tents) kunnen worden gemodelleerd binnen één wiskundig kader met behulp van conflictdiagrammen en gebiedsbeperkingen, wat de ontwikkeling van algemene quantumoplossers voor combinatorische problemen faciliteert.
• Benchmarking: Deze formuleringen dienen als robuuste benchmarks voor het testen van quantumalgoritmen, met name voor het hanteren van beperkingen, variabele reductie en de afweging tussen oplossingsexactheid en qubit-overhead (bijv. de kosten van getuigevariabelen).
• Toekomstige richtingen: Het artikel schetst paden voor toekomstig onderzoek, waaronder het implementeren van deze formuleringen op echte quantumhardware, het verminderen van de overhead van hulpvariabelen voor globale beperkingen en het verkennen van formuleringen van hogere orde (HOBO/QUDO).

Kortom, dit artikel biedt een uitgebreide toolkit voor het vertalen van complexe, beperkingsrijke logische spellen naar QUBO-formaat, met een specifieke nadruk op het bereiken van exactheid door middel van geavanceerde technieken zoals conflictdiagrammen en getuigevariabelen, waardoor deze problemen haalbare kandidaten worden voor quantumcomputertoepassingen op korte termijn.