Het 36-officierenprobleem
Het verhaal gaat dat de Russische tsarina Catharina II (Catharine de Grote) in de 18e eeuw de volgende uitdaging aan wiskundige Leonhard Euler voorlegde: er zijn 36 officieren, verdeeld over zes rangen en zes regimenten, zodat er exact één officier is voor iedere combinatie van rang en regiment. Kun je de officieren in een vierkant van zes bij zes plaatsen, zodat in elke horizontale én elke verticale rij alle zes de rangen en alle zes de regimenten precies één keer voorkomen?
Om gevoel te krijgen voor de puzzel, kun je beginnen met een eenvoudigere variant. Hieronder zie je bijvoorbeeld hoe je negen officieren, verdeeld over drie rangen en drie regimenten, in een vierkant van 3 bij 3 kunt plaatsen. Wat terminologie: wis- en natuurkundigen noemen zo’n vierkant een rooster, en de lijnen rijen en kolommen. Lukt het jou een oplossing vinden met zestien officieren in een rooster van 4 bij 4? Een oplossing vind je onderaan dit artikel. Opvallend genoeg is de puzzel niet op te lossen voor vier officieren in een rooster van 2 bij 2. Probeer maar eens!
Wie de puzzel met 36 officieren probeert op te lossen, zal merken dat dit nog niet zo eenvoudig is. Ook Euler slaagde er niet in een oplossing te vinden. In zijn zoektocht naar een oplossing, ontwikkelde hij wel methodes om de puzzel op te lossen voor roosters van n bij n, waarbij n een oneven getal is of een veelvoud van 4. Daarmee bleef een specifieke groep van getallen over waarvoor nog geen oplossing gevonden was, namelijk de even getallen die niet deelbaar zijn door 4, zoals 2, 6, 10 en 14. Omdat bewezen was dat de puzzel voor n = 2 geen oplossing heeft, en Euler geen oplossing kon vinden voor n = 6, 10, 14, enzovoort, vermoedde hij dat de puzzel voor geen enkel getal uit deze groep een oplossing had.
Ruim een eeuw later, in 1901, bewees de Franse wiskundige Gaston Tarry dat de puzzel van de tsarina, dus het geval met n = 6, inderdaad geen oplossing heeft. Eulers vermoeden hield daarmee nog een tijd stand, totdat Raj Bose en Sharadchandra Shrikhande in 1959 een tegenvoorbeeld vonden: een oplossing voor een rooster van 22 bij 22. In 1960 publiceerde het tweetal samen met Ernest Parker een artikel waarin ze aantoonden dat Eulers vermoeden onjuist was voor alle n groter dan 6. Oftewel, de enige getallen waarvoor het probleem géén oplossing heeft, zijn 2 en 6. Een gemene puzzel dus!
Quantumofficieren
Met de bewijzen van Tarry en van Bose, Parker en Shrikhande leek het laatste woord over Eulers officierenprobleem gezegd, maar een paar jaar geleden wierp een groep wetenschappers uit India en Polen nieuw licht op de puzzel. De groep liet zien dat er wél een oplossing bestaat als de 36 officieren zich in een ‘quantumtoestand’ van rangen en regimenten mogen bevinden.
Quantumsystemen, zoals elektronen en andere elementaire deeltjes, hebben een bijzondere eigenschap: ze kunnen zich in een zogenoemde superpositie van toestanden bevinden. Zo’n deeltje kan zich bijvoorbeeld voor 50 procent op positie A en voor 50 procent op positie B bevinden. Dit betekent dat we, wanneer we de positie van het deeltje meten, 50 procent kans hebben om het deeltje op positie A aan te treffen en 50 procent kans om het op positie B aan te treffen. In tegenstelling tot klassieke deeltjes betekent deze kans niet dat het deeltje al ergens zit, en wij alleen niet weten waar. De uitkomst ligt pas vast bij de meting.
Wat betekent dit voor de officierenpuzzel? In de klassieke versie heeft iedere officier precies één rang en één regiment. In de quantumvariant kan een officier zich in een superpositie van rangen en regimenten bevinden. Zo’n quantumofficier kan bijvoorbeeld met 60 procent kans een gele 2 zijn en met 40 procent kans een roze 6.
Ook de spelregel dat elke rang (weergegeven door een getal) en elk regiment (weergegeven door een kleur) precies één keer voorkomt in iedere rij en kolom, moet een quantumvertaling krijgen. Wat betekent het immers dat een officier ‘voor 60 procent geel’ is? De voor de hand liggende vertaling is optellen: Staan er in een rij één officier die voor 60 procent geel is, één officier die voor 40 procent geel is, en verder geen gele officieren, dan is er in de hele rij samen 100 procent kans op een gele officier. Tot slot moeten alle officieren werkelijk verschillend zijn, wat betekent dat ze met een (slim gekozen) quantummeting foutloos uit elkaar kunnen worden gehouden. Dit is de quantumversie van de klassieke regel dat geen twee officieren dezelfde combinatie van rang en regiment hebben.
Absoluut maximale verstrengeling
Het quantumofficierenprobleem is niet alleen een leuke wiskundige puzzel, maar heeft ook toepassingen in de quantumtechnologie. Quantumsystemen zijn kwetsbaar: deeltjes kunnen verloren gaan en kleine verstoringen van buitenaf kunnen een superpositie doen instorten. Informatie in klassieke systemen kan hiertegen beschermd worden door kopieën te maken, maar quantuminformatie kan niet gekopieerd worden. In plaats daarvan kan de informatie beschermd worden door het te verspreiden over meerdere deeltjes. Hierbij spelen zogeheten absoluut maximaal verstrengelde toestanden of AME-toestanden (naar het Engelse ‘absolutely maximally entangled’) een belangrijke rol.
Een AME-toestand bestaat uit een aantal quantumsystemen die met elkaar verstrengeld zijn. Dit betekent dat metingen aan de afzonderlijke deeltjes sterk gecorreleerd zijn. Meet je bij twee op een bepaalde manier verstrengelde deeltjes bijvoorbeeld dat het ene deeltje op positie A zit, dan weet je meteen dat het andere op positie B zit. In een AME-toestand is de verstrengeling zo gelijkmatig mogelijk verdeeld over alle deeltjes. Voor vier deeltjes betekent dat: hoe je ze ook in tweetallen opsplitst, het ene tweetal is altijd maximaal verstrengeld met het andere tweetal. Als twee van de vier deeltjes kwijtraken, kan hun toestand alsnog worden gereconstrueerd uit de toestanden van de andere twee deeltjes.
Hier komen de officieren weer in beeld. Elke officier heeft vier kenmerken: rang, regiment, rij en kolom. In een oplossing van de puzzel leggen twee willekeurige kenmerken samen de andere twee vast. Wie rij en kolom kent, weet rang en regiment; rij en regiment wijzen samen precies een kolom en rang aan; enzovoort. Dit is precies de eigenschap van een AME-toestand van vier deeltjes. Voor deeltjes met drie, vier, vijf of meer dan zes mogelijke toestanden – bijvoorbeeld posities waar we het deeltje kunnen aantreffen – bestaan zulke AME-toestanden, omdat de klassieke officerenpuzzel daar een oplossing heeft. Voor twee toestanden is in 2000 door Felix Huber en Jens Siewert bewezen dat het maken van een AME-toestand niet mogelijk is. Alleen voor zes toestanden was het dus nog een open vraag: de klassieke puzzel heeft geen oplossing, maar de quantumversie misschien wel?
Met behulp van computeralgoritmes vonden de onderzoekers inderdaad een oplossing voor het quantum-36-officierenprobleem. Wie benieuwd is naar de details van deze oplossing, kan hier een kijkje nemen in de wetenschappelijke publicatie. De onderzoekers lieten hiermee zien dat er een AME-toestand bestaat van vier deeltjes met elk zes mogelijke toestanden. Ruim tweehonderd jaar nadat Euler zich het hoofd brak over de puzzel van de tsarina, blijkt deze dus tóch oplosbaar – als de officieren zich maar volgens de regels van de quantummechanica mogen gedragen.
***
Dit artikel is gebaseerd op de volgende publicatie:
Rather, S. A., Burchardt, A., Bruzda, W., Rajchel-Mieldzioć, G., Lakshminarayan, A., & Życzkowski, K. (2022). Thirty-six entangled officers of Euler: Quantum solution to a classically impossible problem. Physical Review Letters, 128(8), 080507.
Oplossingen van de puzzels
Zestien officieren kunnen op maar liefst 6912 toegestane manieren in een rooster van 4 bij 4 worden geplaatst. Een mogelijke oplossing:
De “oplossing” van het 36-officierenprobleem bevat twee fouten. De derde kolom bevat twee zessen, de vierde kolom bevat twee drieën:
