A Game-Theoretic Quantum Algorithm for Solving Magic Squares

• URL: http://arxiv.org/abs/2505.13366v1
• Date: Mon, 19 May 2025 17:12:53 GMT
• Title: A Game-Theoretic Quantum Algorithm for Solving Magic Squares
• Authors: Sarah Chehade, Andrea Delgado, Elaine Wong,
• Abstract summary: We present a variational framework for the Magic Square Game (MSG), a two-player non-local game with perfect quantum advantage.<n>We construct a value Hamiltonian that encodes the game's parity and consistency constraints, then optimize parameterized quantum circuits to minimize this cost.
• Score: 2.09260520196733
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Variational quantum algorithms (VQAs) offer a promising near-term approach to finding optimal quantum strategies for playing non-local games. These games test quantum correlations beyond classical limits and enable entanglement verification. In this work, we present a variational framework for the Magic Square Game (MSG), a two-player non-local game with perfect quantum advantage. We construct a value Hamiltonian that encodes the game's parity and consistency constraints, then optimize parameterized quantum circuits to minimize this cost. Our approach builds on the stabilizer formalism, leverages commutation structure for circuit design, and is hardware-efficient. Compared to existing work, our contribution emphasizes algebraic structure and interpretability. We validate our method through numerical experiments and outline generalizations to larger games.

Related papers

• A convergent sum-of-squares hierarchy for compiled nonlocal games [1.5029560229270191]
  We study "compiled" nonlocal games played between a classical verifier and a single quantum prover.<n>We show that the success probability of a quantum prover in the compiled game is bounded by the game's quantum commuting-operator value.<n>We extend the niceness framework and construct a hierarchy of semidefinite programs that searches exclusively over nice certificates.
  arXiv  Detail & Related papers  (2025-07-23T15:16:38Z)
• Quantum Checkers: The Development and Analysis of a Quantum Combinatorial Game [1.0225653612678713]
  This paper develops and analyses a novel quantum game: quantum checkers (codenamed Cheqqers)<n>The concepts of superposition, entanglement, measurements and interference from quantum mechanics are integrated into the game of checkers by adding new types of legal moves.<n>We provide the initial analysis on the complexity of this game using random agents and a Monte Carlo tree search agent.
  arXiv  Detail & Related papers  (2025-06-06T10:39:28Z)
• A bound on the quantum value of all compiled nonlocal games [49.32403970784162]
  A cryptographic compiler converts any nonlocal game into an interactive protocol with a single computationally bounded prover. We establish a quantum soundness result for all compiled two-player nonlocal games.
  arXiv  Detail & Related papers  (2024-08-13T08:11:56Z)
• Repeated quantum game as a stochastic game: Effects of the shadow of the future and entanglement [0.0]
  We present a systematic investigation of the quantum games, constructed using a novel repeated game protocol. We find that how two pure strategies fare against each other is crucially dependent on the discount factor. In the quantum game setup, always-defect strategy can be beaten by the tit-for-tat strategy for high enough discount factor.
  arXiv  Detail & Related papers  (2023-12-08T15:54:51Z)
• A Quadratic Speedup in Finding Nash Equilibria of Quantum Zero-Sum Games [95.50895904060309]
  We introduce the Optimistic Matrix Multiplicative Weights Update (OMMWU) algorithm and establish its average-iterate convergence complexity as $mathcalO(d/epsilon)$ to $epsilon$-Nash equilibria.<n>This quadratic speed-up sets a new benchmark for computing $epsilon$-Nash equilibria in quantum zero-sum games.
  arXiv  Detail & Related papers  (2023-11-17T20:38:38Z)
• Photonic implementation of the quantum Morra game [69.65384453064829]
  We study a faithful translation of a two-player quantum Morra game, which builds on previous work by including the classical game as a special case. We propose a natural deformation of the game in the quantum regime in which Alice has a winning advantage, breaking the balance of the classical game. We discuss potential applications of the quantum Morra game to the study of quantum information and communication.
  arXiv  Detail & Related papers  (2023-11-14T19:41:50Z)
• Realization of arbitrary doubly-controlled quantum phase gates [62.997667081978825]
  We introduce a high-fidelity gate set inspired by a proposal for near-term quantum advantage in optimization problems. By orchestrating coherent, multi-level control over three transmon qutrits, we synthesize a family of deterministic, continuous-angle quantum phase gates acting in the natural three-qubit computational basis.
  arXiv  Detail & Related papers  (2021-08-03T17:49:09Z)
• Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
  Matching problems on 3D shapes and images are frequently formulated as quadratic assignment problems (QAPs) with permutation matrix constraints, which are NP-hard. We propose several reformulations of QAPs as unconstrained problems suitable for efficient execution on quantum hardware. The proposed algorithm has the potential to scale to higher dimensions on future quantum computing architectures.
  arXiv  Detail & Related papers  (2021-07-08T17:59:55Z)
• Synchronicity for quantum non-local games [0.7646713951724009]
  We show that quantum homomorphisms of quantum graphs can be viewed as entanglement assisted classical homomorphisms of the graphs. We give descriptions of the perfect quantum commuting and the perfect approximately quantum strategies for the quantum graph homomorphism game.
  arXiv  Detail & Related papers  (2021-06-22T02:40:41Z)
• QUANTIFY: A framework for resource analysis and design verification of quantum circuits [69.43216268165402]
  QUANTIFY is an open-source framework for the quantitative analysis of quantum circuits. It is based on Google Cirq and is developed with Clifford+T circuits in mind. For benchmarking purposes QUANTIFY includes quantum memory and quantum arithmetic circuits.
  arXiv  Detail & Related papers  (2020-07-21T15:36:25Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.