Quantum n-coloring is undecidable for every n $\ge$ 3

In de stille hoekjes van de wiskunde en de informatica bestaat een klasse problemen die een eenvoudige vraag stelt: kan een specifieke set regels worden gevolgd zonder tegenspraak? Een van de bekendste hiervan is het grafkleuringsprobleem. Stel je een kaart voor waarbij elke regio een kleur moet krijgen, maar waarbij geen twee regio's die een grens delen dezelfde tint mogen hebben. Lange tijd wisten wiskundigen dat voor kaarten met slechts twee kleuren het antwoord snel door een computer gevonden kon worden. Echter, zodra het aantal beschikbare kleuren toeneemt, wordt het probleem vele malen complexer. In het domein van de kwantumfysica, waar deeltjes in meerdere toestanden tegelijk kunnen bestaan en diepe, onzichtbare verbindingen kunnen delen, krijgt dit kleurspel een nieuwe vorm. Hier zijn de "kleuren" niet alleen verf, maar wiskundige hulpmiddelen die projecties worden genoemd en die de toestand van een kwantumsysteem beschrijven. De vraag verschuift van of een kaart gekleurd kan worden met standaardregels naar de vraag of er een perfecte strategie bestaat voor een kwantumversie van het spel. Dit onderscheid is van belang omdat het de grenzen raakt van wat berekenbaar is. Als een probleem onbeslisbaar is, betekent dit dat geen enkele computer, ongeacht hoe krachtig of hoeveel tijd deze ook krijgt, ooit een antwoord kan garanderen.

Jarenlang wisten onderzoekers dat dit kwantumkleuringsspel onmogelijk op te lossen was voor een specifiek geval met drie kleuren. Het mysterie bleef bestaan voor elk aantal kleuren groter dan drie. Een team van bachelorstudenten aan de Technische Universiteit van Denemarken heeft die kloof nu gedicht. Zij bewezen dat het kwantumkleuringsprobleem onbeslisbaar is voor elk aantal kleuren vanaf drie en hoger. Hun werk steunt niet op complexe simulaties of onbewezen theorieën; het is een rigoureus wiskundig bewijs dat een bekende onmogelijkheid uitbreidt naar een geheel nieuw bereik van mogelijkheden. Door een specifieke brug te bouwen tussen het drie-kleurengeval en elk hoger aantal kleuren, toonden zij aan dat als een computer de drie-kleurenversie niet kan oplossen, hij ook geen enkele versie met meer kleuren kan oplossen.

De onderzoekers begonnen met een graaf, wat simpelweg een verzameling punten is die door lijnen verbonden zijn, die de regio's en grenzen van de kleuringskaart vertegenwoordigen. Vervolgens creëerden ze een nieuwe, grotere graaf door de oorspronkelijke graaf te combineren met een kleine, vaste structuur en een complete groep punten. Deze constructie is een precies recept dat snel door een computer gevolgd kan worden. De kern van hun ontdekking ligt in het aantonen dat het vermogen om deze nieuwe, grotere graaf te kleuren met een specifiek aantal kleuren exact hetzelfde is als het vermogen om de oorspronkelijke kleine graaf te kleuren met slechts drie kleuren. Als de oorspronkelijke graaf opgelost kan worden met een kwantumstrategie voor drie kleuren, kan de nieuwe graaf worden opgelost voor het grotere aantal kleuren. Omgekeerd, als de nieuwe graaf kan worden opgelost, moet de oorspronkelijke wel oplosbaar zijn voor drie kleuren. Dit creëert een directe link, of een reductie, wat betekent dat de moeilijkheid van het grotere probleem identiek is aan de moeilijkheid van het kleinere probleem.

Aangezien het al vastgesteld was dat het drie-kleurenkwantumprobleem onbeslisbaar is, bewijst deze link dat de grotere problemen eveneens onbeslisbaar zijn. De studenten hebben aangetoond dat er geen algoritme bestaat dat naar een graaf en een aantal kleuren groter dan drie kan kijken en definitief kan zeggen of er een perfecte kwantumstrategie bestaat. Het bewijs werkt door aan te tonen dat elke poging om het grotere probleem op te lossen in essentie zou vereisen dat eerst het onmogelijke drie-kleurenprobleem wordt opgelost. Dit resultaat is waar of het kwantumsysteem nu eindig of oneindig is, en dekt alle standaardmodellen van de kwantummechanica die in dit veld worden gebruikt. Deze bevinding lost een vraag op die al enige tijd openstond, en bevestigt dat de barrière voor berekenbaarheid niet slechts een eigenaardigheid van het drie-kleurengeval is, maar een fundamenteel kenmerk van de gehele familie van kwantumkleuringsproblemen.

De implicaties van dit werk reiken verder dan het specifieke kleurspel. Het suggereert een breder patroon in de complexiteit van kwantumsystemen. De auteurs merken op dat hoewel sommige specifieke typen kwantumkleuringsproblemen oplosbaar zijn, het algemene geval voor niet-bipartiete structuren onbeslisbaar lijkt te zijn. Zij stellen een conjectuur voor dat voor elke structuur die geen eenvoudige tweedelige verdeling is, het kwantumkleuringsprobleem waarschijnlijk onbeslisbaar zal zijn. Dit sluit aan bij een bekende tweedeling in de klassieke wiskunde, waarbij problemen ofwel makkelijk ofwel moeilijk zijn, maar hier is de "moeilijke" kant aangetoond werkelijk onoplosbaar te zijn. Het werk staat als een heldere demonstratie dat in de kwantumwereld de grenzen van de berekenbaarheid strikter zijn dan voorheen gedacht, en dat voor een breed scala aan scenario's de vraag of er een perfecte strategie bestaat, een vraag is die geen enkele machine ooit kan beantwoorden.