A Game-Theoretic Quantum Algorithm for Solving Magic Squares

1. Problem Statement

The paper addresses the challenge of discovering optimal quantum strategies for Non-Local Games (NLGs), specifically the Magic Square Game (MSG).

• Context: NLGs are interactive tasks where non-communicating players (Alice and Bob) share an entangled state to win against a referee. They test quantum correlations beyond classical limits.
• The Magic Square Game: A 2-player game where players must fill a $3 \times 3$ grid with $\pm 1$ values. Alice is assigned a row (must have product $+1$), and Bob is assigned a column (must have product $-1$). They win if their answers agree on the intersecting cell.
• The Gap: While the perfect quantum strategy for the MSG is known analytically (winning probability $\omega_q = 1$ vs. classical $\omega_c = 8/9$), deriving such strategies for larger or more complex games often requires complex analytical solutions. The authors propose a Variational Quantum Algorithm (VQA) approach to learn these strategies from first principles, making the method scalable for near-term quantum hardware.

2. Methodology

The authors propose a hybrid quantum-classical framework using a Variational Quantum Eigensolver (VQE) style approach.

A. Theoretical Framework & Hamiltonian Construction

• Stabilizer Formalism: The game constraints are encoded into a Value Hamiltonian ($H$).
• Fixed Observables: The authors define a set of fixed Pauli observables $\{A_i\}$ for Alice (rows) and $\{B_j\}$ for Bob (columns) acting on 3-qubit subsystems. These are constructed from tensor products of Pauli matrices ($X, Z$) such that each operator contains exactly one $X$ and two $Z$s.
  • Constraint: $A_i$ and $B_j$ are designed to satisfy specific parity and anti-commutation rules inherent to the MSG.
• The Cost Function: The Hamiltonian is defined as:
  $$H = -\sum_{i,j} A_i \otimes B_j$$
  The ground state energy of $H$ corresponds to a perfect win (value $-9$). Minimizing the expectation value $\langle H \rangle$ is equivalent to maximizing the game win probability.

B. Variational Circuit Design

• State Preparation: The system initializes with a 6-qubit entangled state composed of three Bell pairs ($|\Phi^+\rangle$), one for each corresponding qubit pair between Alice and Bob.
• Parameterized Unitaries: Instead of measuring fixed observables, the players apply local unitary transformations $U_i(\theta)$ and $V_j(\phi)$ to rotate the fixed observables into trainable measurement bases:
  $$\tilde{A}_i = U_i^\dagger A_i U_i, \quad \tilde{B}_j = V_j^\dagger B_j V_j$$
• Ansatz: The unitaries are implemented using the StronglyEntanglingLayers template in PennyLane. This consists of layers of single-qubit rotations ($X, Y$) followed by entangling gates (CNOT/CZ), repeated for 3 layers. This ensures hardware efficiency and full expressibility over the 3-qubit local Hilbert space.

C. Optimization Loop

• Objective: Minimize the cost function $L(\theta, \phi) = \langle \psi | \sum \tilde{A}_i \otimes \tilde{B}_j | \psi \rangle$.
• Algorithm: The Adam optimizer is used with automatic differentiation (PennyLane autograd) to update parameters $\theta$ and $\phi$.
• Key Insight: The commutation structure of the fixed operators is preserved during optimization. The authors leverage the fact that observables within a player's set commute ($[A_i, A_{i'}] = 0$), ensuring local compatibility and no-signaling conditions are maintained even as the strategy is learned.

3. Key Contributions

1. Algebraic Interpretability: Unlike previous works that treat NLGs as black-box optimization problems, this paper explicitly dissects the algebraic structure (stabilizers and commutation relations) of the MSG. It demonstrates how these algebraic properties guide the variational search.
2. Hamiltonian Encoding: The construction of a specific Value Hamiltonian that encodes parity and consistency constraints, allowing the VQA to "learn" the exact winning strategy without prior knowledge of the analytical solution.
3. Hardware Efficiency: The use of a shallow, hardware-efficient ansatz (StronglyEntanglingLayers) makes the approach suitable for near-term quantum devices (NISQ).
4. Validation of Commutativity: The work empirically validates that the variational optimization preserves the necessary commutation relations between local observables, ensuring the physical validity of the learned strategy.

4. Results

The authors performed extensive numerical simulations with the following outcomes:

• Convergence: The cost function converged rapidly to the theoretical minimum of $-9.0$ within approximately 30 optimization steps.
• Win Rate: The learned strategy achieved a 100% win rate (perfect fidelity) across all 9 input combinations.
• Expectation Values:
  • Joint observables $\langle \tilde{A}_i \otimes \tilde{B}_j \rangle$ consistently reached $+1.0$ (within $10^{-6}$), satisfying the winning condition.
  • Marginal expectation values $\langle \tilde{A}_i \rangle$ and $\langle \tilde{B}_j \rangle$ often hovered near zero, confirming that the strategy relies on non-local correlations rather than local predictability.
• Constraint Verification:
  • Parity: Alice's row outputs maintained odd parity; Bob's column outputs maintained even parity.
  • Consistency: The overlapping cell outputs agreed with high fidelity ($\approx +1.0$).
  • Commutativity: Post-training commutators $[\tilde{A}_i, \tilde{A}_{i'}]$ and $[\tilde{B}_j, \tilde{B}_{j'}]$ remained near zero ($<10^{-6}$), confirming the strategy respects the no-signaling condition.

5. Significance and Future Outlook

• Scalability: The framework generalizes to larger games (e.g., $n \times n$ magic squares). The authors suggest that for $n \times n$ grids, the number of qubits grows linearly with $n$, and the Hamiltonian consists of $n^2$ operator pairs.
• Theoretical Bridge: The paper connects semi-simple Lie algebras (specifically the algebra of Pauli matrices) to game strategies. It suggests that Cartan decompositions of these algebras could provide a systematic path to constructing strategies for larger, analytically intractable games.
• Practical Application: By optimizing over unitaries rather than fixed observables, this approach is adaptable to hardware noise and calibration data, paving the way for device-independent verification and self-testing on real quantum hardware.
• Broader Impact: The methodology offers a template for solving other binary constraint systems and non-local games where analytical solutions are unknown, bridging the gap between foundational quantum mechanics and practical quantum algorithm design.

In summary, this work demonstrates that Variational Quantum Algorithms can not only approximate but exactly recover perfect quantum strategies for non-local games by leveraging the underlying algebraic structure of the problem, offering a promising path for exploring quantum advantage on near-term hardware.