A Game-Theoretic Quantum Algorithm for Solving Magic Squares

Titel: Een speltheoretisch quantumalgoritme voor het oplossen van Magische Vierkanten

Auteurs: Sarah Chehade, Andrea Delgado, Elaine Wong (Oak Ridge National Laboratory)
Datum: 19 mei 2025

1. Het Probleem

Het artikel richt zich op niet-lokale spellen (Non-Local Games, NLGs), interactieve taken waarbij spelers die niet met elkaar kunnen communiceren, proberen een referee te verslaan door gebruik te maken van een gedeelde quantumtoestand. Deze spellen zijn fundamenteel voor het testen van quantumcorrelaties die klassieke limieten overschrijden (zoals Bell-ongelijkheden) en voor het verifiëren van verstrengeling.

Specifiek wordt de Magic Square Game (MSG) onderzocht. Dit is een tweespelersspel waarbij Alice een rij en Bob een kolom van een $3 \times 3$ rooster toegewezen krijgen. Ze moeten waarden ($\pm 1$) invullen die voldoen aan specifieke pariteitsvoorwaarden (het product van een rij is $+1$, het product van een kolom is $-1$) en moeten overeenstemming bereiken op het snijpunt van hun rij en kolom.

• Klassieke limiet: Geen enkele klassieke strategie kan alle negen mogelijke invoercombinaties winnen; de maximale klassieke winstkans is $\omega_c = 8/9$.
• Quantumvoordeel: Met verstrengeling en de juiste metingen kunnen quantumspelers met 100% zekerheid winnen ($\omega_q = 1$).

Hoewel de analytische oplossing voor kleine spellen zoals de MSG bekend is, biedt het vinden van optimale strategieën voor complexere spellen een uitdaging. Het doel van dit werk is het ontwikkelen van een variational quantum algorithm (VQA)-benadering om deze optimale strategieën te ontdekken zonder volledig op analytische afleidingen te vertrouwen, wat schaalbaar is voor toekomstige quantumhardware.

2. Methodologie

De auteurs presenteren een hybride quantum-klassiek optimalisatieraamwerk dat de stabilisatorformaliek combineert met moderne VQA-technieken.

• Hamiltoniaan van de Waarde:
  In plaats van direct de winstkans te maximaliseren, coderen de auteurs de spelregels in een waarde-Hamiltoniaan ($H$). Deze Hamiltoniaan bestaat uit de som van tensorproducten van waarnemingsoperatoren voor Alice ($A_i$) en Bob ($B_j$):
  $$H = -\sum_{i,j} A_i \otimes B_j$$
  De grondtoestandsenergie van deze Hamiltoniaan is $-9$, wat overeenkomt met een perfecte strategie waarbij alle negen combinaties voldoen aan de winvoorwaarde (verwachtingswaarde $+1$ per term).

• Operatorconstructie:
  De vaste operatoren $A_i$ en $B_j$ worden geconstrueerd als tensorproducten van Pauli-matrices ($X, Z$) op drie qubits per speler. Ze volgen een strikte structuur: elke operator bevat precies één $X$ en twee $Z$'s. Dit garandeert de nodige anti-commutatie en commutatie-eigenschappen die vereist zijn voor de pariteitsvoorwaarden van het spel.

• Parameterisatie en Schakeling:
  De daadwerkelijke metingen worden uitgevoerd door de vaste operatoren te roteren via parameteriseerbare unitaire transformaties $U_i(\theta)$ en $V_j(\phi)$.

  • De quantumcircuit-ansatz gebruikt de StronglyEntanglingLayers template (uit PennyLane), bestaande uit rotaties en verstrekkende poorten (CNOT/CZ).
  • De starttoestand bestaat uit drie Bell-paren (zes qubits in totaal), wat de maximale verstrengeling tussen Alice en Bob garandeert.

• Optimalisatie:
  Een klassieke optimizer (Adam) minimaliseert de kostenfunctie $L(\theta, \phi) = \langle \psi | H | \psi \rangle$. Het doel is om de verwachtingswaarde van de Hamiltoniaan te minimaliseren naar $-9$. Tijdens het trainingsproces worden ook de commutatoren binnen de subsystemen van elke speler gecontroleerd om te waarborgen dat de lokale metingen compatibel blijven (geen signaaloverdracht).

3. Belangrijkste Bijdragen

1. Algebraïsche Structuur en Interpretatie: In tegenstelling tot eerdere werken die zich richten op het trainen van circuits voor een breed scala aan spellen, legt dit werk de nadruk op de onderliggende algebraïsche structuur van de MSG. Ze tonen aan hoe de commutatierelaties van de operatoren cruciaal zijn voor het behoud van de spelconsistentie tijdens de variational learning.
2. Stabilisatorgebaseerde Ontwerp: De auteurs gebruiken de stabilisatorformaliek om een "skelet" van operatoren te bouwen dat de spelregels direct encodeert. Dit maakt het mogelijk om de spelstructuur te scheiden van de strategieontdekking.
3. Hardware-efficiëntie: Het gebruik van een compacte ansatz (3 lagen op 3 qubits per speler) en het vermijden van complexe dubbele optimalisatiecycli (in tegenstelling tot sommige eerdere methoden) maakt de methode geschikt voor nabije-toekomstige quantumhardware.
4. Generalisatie: Het raamwerk is ontworpen om schaalbaar te zijn naar grotere $n \times n$ magische vierkanten en andere niet-lokale spellen, waarbij de auteurs een link leggen met Cartan-decomposities van semi-simpel Lie-algebra's voor het vinden van optimale decomposities.

4. Resultaten

De numerieke experimenten tonen een succesvolle implementatie van het algoritme:

• Convergentie: De kostenfunctie convergeert snel en monotoon naar de theoretische minimumwaarde van -9,0 binnen ongeveer 30-50 optimalisatiestappen.
• Winstkans: De getrainde strategie bereikt een winstkans van 1,0 (100%). Alle negen invoercombinaties voldoen aan de pariteitsvoorwaarden en de consistentie op het snijpunt.
• Verwachtingswaarden:
  • De gezamenlijke verwachtingswaarden $\langle \tilde{A}_i \otimes \tilde{B}_j \rangle$ convergeren naar $+1,0$ (binnen $10^{-6}$ nauwkeurigheid).
  • Opvallend is dat de marginale verwachtingswaarden ($\langle \tilde{A}_i \rangle$ en $\langle \tilde{B}_j \rangle$) vaak dicht bij nul liggen. Dit bevestigt dat de winst niet voortkomt uit lokale voorspelbaarheid, maar uit de niet-lokale correlaties tussen de spelers.
• Commutatie: Na training zijn de commutatoren tussen operatoren van dezelfde speler ($[ \tilde{A}_i, \tilde{A}_{i'} ]$) verwaarloosbaar klein ($< 10^{-6}$), wat aantoont dat de lokale meetbaarheid en het "no-signaling"-principe behouden blijven.

5. Betekenis en Toekomstperspectief

Dit werk demonstreert dat variational quantum algorithms (VQAs) niet alleen bruikbaar zijn voor chemische simulaties of optimalisatieproblemen, maar ook effectief kunnen worden ingezet voor fundamentele kwantumtheoretische taken zoals het vinden van strategieën voor niet-lokale spellen.

• Interpreteerbaarheid: Het algoritme leert niet alleen een "zwarte doos"-oplossing, maar respecteert de fysieke en algebraïsche beperkingen van het spel (pariteit en commutatie).
• Schaalbaarheid: De methode biedt een route om strategieën te vinden voor complexere spellen waar analytische oplossingen onbekend of onbereikbaar zijn.
• Hardware-toepassingen: Omdat de methode variabele unitaire transformaties optimaliseert in plaats van vaste operatoren, kan deze zich aanpassen aan specifieke ruismodellen van quantumhardware. Dit opent de deur voor experimentele demonstraties van "perfecte" quantumstrategieën op echte apparaten in de nabije toekomst.

Samenvattend biedt dit artikel een robuust, algebraïsch onderbouwd raamwerk dat de brug slaat tussen abstracte speltheorie en praktische quantumoptimalisatie, met potentie voor uitbreiding naar grotere en complexere quantumnetwerken.