Application-level Benchmarking of Quantum Computers using Nonlocal Game Strategies

• URL: http://arxiv.org/abs/2311.01363v4
• Date: Mon, 10 Mar 2025 16:57:47 GMT
• Title: Application-level Benchmarking of Quantum Computers using Nonlocal Game Strategies
• Authors: Jim Furches, Sarah Chehade, Kathleen Hamilton, Nathan Wiebe, Carlos Ortiz Marrero,
• Abstract summary: In nonlocal games, two players cooperate to convince a referee that they possess a strategy that does not violate the rules of the game.<n>We present a variational quantum algorithm to compute quantum strategies for nonlocal games by encoding the rules of a nonlocal game into a Hamiltonian.
• Score: 1.4835379864550937
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In a nonlocal game, two noncommunicating players cooperate to convince a referee that they possess a strategy that does not violate the rules of the game. Quantum strategies allow players to optimally win some games by performing joint measurements on a shared entangled state, but computing these strategies can be challenging. We present a variational quantum algorithm to compute quantum strategies for nonlocal games by encoding the rules of a nonlocal game into a Hamiltonian. We show how this algorithm can generate a short-depth optimal quantum strategy for a graph coloring game with a quantum advantage. This quantum strategy is then evaluated on fourteen different quantum hardware platforms to demonstrate its utility as a benchmark. Finally, we discuss potential sources of errors that can explain the observed decreased performance of the executed task and derive an expression for the number of samples required to accurately estimate the win rate in the presence of noise.

Related papers

• 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)
• Lossy-and-Constrained Extended Non-Local Games with Applications to Quantum Cryptography [0.0]
  We show that if one extends such games by considering constraints and loss, the convergence of the SDPs to the optimal value still holds. We give applications of this result, and we compute SDPs that show tighter security of protocols for relativistic bit commitment, quantum key distribution, and quantum position verification.
  arXiv  Detail & Related papers  (2024-05-22T15:09:30Z)
• Exploiting Finite Geometries for Better Quantum Advantages in Mermin-Like Games [0.0]
  Quantum games embody non-intuitive consequences of quantum phenomena, such as entanglement and contextuality. In this paper we look at the geometric structure behind such classical strategies, and borrow ideas from the geometry of symplectic polar spaces to maximise this quantum advantage.
  arXiv  Detail & Related papers  (2024-03-14T15:56:43Z)
• 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)
• 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)
• Implementing 2-qubit pseudo-telepathy games on noisy intermediate scale quantum computers [0.0]
  Mermin-Peres like proofs of quantum contextuality can furnish non-local games with a guaranteed quantum strategy. We show that the quantumness of these games are almost revealed when we play them on the IBM Quantum Experience.
  arXiv  Detail & Related papers  (2023-10-11T12:47:12Z)
• Finding mixed-strategy equilibria of continuous-action games without gradients using randomized policy networks [83.28949556413717]
  We study the problem of computing an approximate Nash equilibrium of continuous-action game without access to gradients. We model players' strategies using artificial neural networks. This paper is the first to solve general continuous-action games with unrestricted mixed strategies and without any gradient information.
  arXiv  Detail & Related papers  (2022-11-29T05:16:41Z)
• Parallel repetition of local simultaneous state discrimination [12.984519159674525]
  Local simultaneous state discrimination is a recently introduced problem in quantum information processing. We investigate the advantage of no-signalling strategies over classical ones. We show numerically that for three players and binary values, no-signalling strategies cannot provide any improvement over classical ones.
  arXiv  Detail & Related papers  (2022-11-11T19:33:46Z)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vazirani algorithm allows one to determine a bit string encoded into an oracle. We analyze in detail the quantum resources in the Bernstein-Vazirani algorithm. We show that in the absence of entanglement, the performance of the algorithm is directly related to the amount of quantum coherence in the initial state.
  arXiv  Detail & Related papers  (2022-05-26T20:32:36Z)
• Efficient Bipartite Entanglement Detection Scheme with a Quantum Adversarial Solver [89.80359585967642]
  Proposal reformulates the bipartite entanglement detection as a two-player zero-sum game completed by parameterized quantum circuits. We experimentally implement our protocol on a linear optical network and exhibit its effectiveness to accomplish the bipartite entanglement detection for 5-qubit quantum pure states and 2-qubit quantum mixed states.
  arXiv  Detail & Related papers  (2022-03-15T09:46:45Z)
• Generating Diverse and Competitive Play-Styles for Strategy Games [58.896302717975445]
  We propose Portfolio Monte Carlo Tree Search with Progressive Unpruning for playing a turn-based strategy game (Tribes) We show how it can be parameterized so a quality-diversity algorithm (MAP-Elites) is used to achieve different play-styles while keeping a competitive level of play. Our results show that this algorithm is capable of achieving these goals even for an extensive collection of game levels beyond those used for training.
  arXiv  Detail & Related papers  (2021-04-17T20:33:24Z)
• Surpassing the Classical Limit in Magic Square Game with Distant Quantum Dots Coupled to Optical Cavities [0.0]
  We propose an experimental setup for quantum computation with quantum dots inside optical cavities. Considering various physical imperfections of our setup, we first show that the MSG can be implemented with the current technology. We show that our work gives rise to a new version of the game. That is, if the referee has information on the physical realization and strategy of the players, he can bias the game through filtered randomness and increase his winning probability.
  arXiv  Detail & Related papers  (2020-11-03T05:45:06Z)
• Complexity and Algorithms for Exploiting Quantal Opponents in Large Two-Player Games [16.43565579998679]
  Solution concepts of traditional game theory assume entirely rational players; therefore, their ability to exploit subrational opponents is limited. This paper aims to analyze and propose scalable algorithms for computing effective and robust strategies against a quantal opponent in normal-form and extensive-form games.
  arXiv  Detail & Related papers  (2020-09-30T09:14:56Z)
• Learning to Play Sequential Games versus Unknown Opponents [93.8672371143881]
  We consider a repeated sequential game between a learner, who plays first, and an opponent who responds to the chosen action. We propose a novel algorithm for the learner when playing against an adversarial sequence of opponents. Our results include algorithm's regret guarantees that depend on the regularity of the opponent's response.
  arXiv  Detail & Related papers  (2020-07-10T09:33:05Z)
• Robust Spammer Detection by Nash Reinforcement Learning [64.80986064630025]
  We develop a minimax game where the spammers and spam detectors compete with each other on their practical goals. We show that an optimization algorithm can reliably find an equilibrial detector that can robustly prevent spammers with any mixed spamming strategies from attaining their practical goal.
  arXiv  Detail & Related papers  (2020-06-10T21:18:07Z)
• Efficient exploration of zero-sum stochastic games [83.28949556413717]
  We investigate the increasingly important and common game-solving setting where we do not have an explicit description of the game but only oracle access to it through gameplay. During a limited-duration learning phase, the algorithm can control the actions of both players in order to try to learn the game and how to play it well. Our motivation is to quickly learn strategies that have low exploitability in situations where evaluating the payoffs of a queried strategy profile is costly.
  arXiv  Detail & Related papers  (2020-02-24T20:30:38Z)

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.