Onoplosbare ‘sudoku’ uit achttiende eeuw opgelost met quantumtrucjes

Natuurkundigen hebben een eeuwenoud puzzeltje zonder oplossing toch weten te kraken door gebruik te maken van principes uit de quantummechanica. 

Stel je zes regimenten voor, die elk zes officieren hebben met zes verschillende rangen, schreef de Zwitserse wiskundige Leonhard Euler in 1779. Kun je die dan neerzetten op een schaakbord van zes bij zes op zo’n manier dat er op geen enkele rij twee officieren staan uit hetzelfde regiment of met dezelfde rang?

Wie hier gelijk zijn sudoku-skills op los wil laten, moeten we teleurstellen. Zoals Euler al vermoedde en in 1901 werd bewezen door zijn Franse vakgenoot Gaston Tarry: er is geen oplossing voor dit raadsel. En dat is gek, want voor elk ander aantal regimenten en officieren, behalve twee (probeer maar), is zo’n oplossing er wél. 

Natuurkundigen Suhail Ahmad Rather en Adam Burchardt hebben nu samen met Indiase en Poolse collega’s ‘valsgespeeld’ door trucjes uit de quantummechanica los te laten op Eulers puzzel. En dan is er wél een oplossing – waarmee ook meteen een openstaand vraagstuk uit de wereld van de quantumcomputers aan te pakken bleek.

Quantum-Stratego

Belangrijk voor de quantumoplossing van het ‘36 officierenraadsel’ is dat een officier meerdere rangen en regimenten tegelijk kan hebben. Hij is bijvoorbeeld een beetje sergeant van regiment 1, en een beetje kapitein van regiment 2. Zoiets heet een superpositie, in dit geval van verschillende rangen en regimenten. Zo’n superpositie blijft dan bestaan totdat je zo’n officier daadwerkelijk bekijkt. Dan moet hij een rang en regiment kiezen. 

Vergelijk het met een potje Stratego, waarbij een stuk van de tegenstander een onbekende rang heeft, tot je het slaat met een van jouw stukken en je het om mag draaien. Met als verschil dat het stuk in dit quantum-Stratego pas zijn definitieve rang en regiment kríjgt als je het slaat.

Verstrengelde stukken

Bovendien is er sprake van verstrengeling tussen stukken. Dat wil zeggen: ze kunnen een quantummechanische band met elkaar hebben, waarbij wat er met de een gebeurt, invloed heeft op de ander. Een eenvoudige variant van zo’n verstrengeling is: twee stukken zijn beide een superpositie van majoor en kolonel. Blijkt de één een majoor als je hem bekijkt, dan moet de andere wel een kolonel zijn. 

Ook hier is een analogie te maken met Stratego. Als je tegenstander nog maar twee stukken overheeft en je slaat het ene, dan weet je meteen wat de rang van het andere is. Bij quantum-Stratego geldt dan wel dat beide stukken daadwerkelijk ‘een beetje van het een en een beetje van het ander’ zijn, totdat je een van de twee omdraait.

Geen normaal stuk

Terug naar de puzzel van Euler. De onderzoekers begonnen met een foute oplossing van een raadsel die een eind in de buurt van een goede kwam. Vervolgens lieten ze een algoritme zoeken naar een oplossing waarbij verstrengelde stukken met meerdere rangen en regimenten waren toegestaan. En jawel hoor: zo’n oplossing bleek er te zijn. 

Daarvoor moest wel het blik met quantumtrucs een flink eind open. In de gevonden oplossing is geen enkel stuk nog normaal. Allemaal zijn ze een superpositie van minstens twee, en in de meeste gevallen zelfs vier rang-en-regiment-combinaties.

Quantumdobbelstenen

Leuk, natuurlijk, dat zo’n onoplosbare puzzel op die manier toch nog op te lossen blijkt. Extra leuk dat er – toevallig – evenveel jaar zat tussen Eulers oorspronkelijke vermoeden en het wiskundige bewijs van Tarry, en tussen Tarry’s bewijs en de quantumoplossing van Rather, Burchardt en collega’s. Maar hebben we er ook wat aan?

Misschien wel. De quantumwereld kent namelijk een vergelijkbaar probleem. Quantumcomputers rekenen in de regel met qubits: quantumbits die een waarde van 0 of 1 hebben. Maar er zijn ook ‘qutrits’, die drie waardes kunnen hebben, en qubit-varianten met nog meer mogelijke waardes. Hier zijn vooral ‘quhexen’ van belang, die zes waardes kunnen hebben. Stel je ze voor als een soort quantumdobbelstenen.

Absoluut maximaal verstrengeld

Nu kun je dat soort quantumdobbelstenen in groepjes met elkaar verstrengelen, net zoals eerder gebeurde met de officieren. Een optie is dan om ze ‘absoluut maximaal te verstrengelen’ (absolutely maximally entangled of AME). Dan is elk setje van dobbelstenen dat je pakt, verstrengeld met wat er nog op tafel ligt. 

“Als er vier dobbelstenen zijn, en Alice kiest en gooit er twee, krijgt ze een van 36 even waarschijnlijke uitkomsten”, leggen de onderzoekers uit in hun wetenschappelijke artikel. “Bob gooit dan de andere twee. Als de dobbelstenen absoluut maximaal verstrengeld zijn, kan Alice altijd het resultaat van Bob afleiden uit haar eigen worp.”

‘Elegante oplossing’

Tenminste… Dat zou zo zijn als er setjes bestonden van vier absoluut maximaal verstrengelde quantumdobbelstenen. Maar net zoals je geen 36 officieren kwijt kunt op een bord van zes bij zes zonder dat je ergens dezelfde rang of hetzelfde regiment in een rij of kolom krijgt, zo lukt het ook niet om zo’n setjes van vier quantumdobbelstenen helemaal te verstrengelen. 

Tot nu, want de aanpak die Rather en Burchardt gebruikten, leverde wél zo’n setje op. “De constructie daarvan is een niet-triviaal optimalisatieprobleem dat de onderzoekers in hun artikel op een elegante manier oplossen”, zegt natuurkundige Barbara Terhal, die de theoriegroep van het Delftse quantuminstituut QuTech leidt en niet betrokken was bij het onderzoek. 

Fouten corrigeren

Nu zijn spelen absoluut maximaal verstrengelde toestanden een rol in allerlei toepassingen in de quantumwereld. Bij het corrigeren van fouten in berekeningen van een quantumcomputer bijvoorbeeld, of bij het ‘teleporteren’ van deeltjes: het overzetten van de eigenschappen van het ene deeltje naar het andere. En nu is er dus een nieuwe strategie bedacht om zulke maximaal verstrengelde toestanden te bereiken.

Natuurkundige Hoi-Kwong Lo van de Universiteit van Toronto, niet bij het onderzoek betrokken, noemt het werk, als het overeind blijft, “erg belangrijk, met implicaties voor het corrigeren van fouten in quantumberekeningen” in een bericht van de American Physical Society.

Zover wil Terhal niet gaan. “Ik zou niet zeggen dat dit een grote stap in het quantumfoutcorrectieonderzoek is. Ik zie niet direct toepassingen. Het doel van het onderzoek is eerder het oplossen van die puzzel. Bestaat er zo’n gekke speciale toestand?”

Bronmateriaal

"Thirty-six Entangled Officers of Euler: Quantum Solution to a Classically Impossible Problem" - Physical Review Letters

"A Quantum Solution to an 18th-Century Puzzle" - APS Physics

Barbara Terhal, QuTech
Afbeelding bovenaan dit artikel:

Fout gevonden?

Voor jou geselecteerd