Guess your neighbor's input: Quantum advantage in Feige's game

• URL: http://arxiv.org/abs/2510.08484v2
• Date: Wed, 22 Oct 2025 11:13:33 GMT
• Title: Guess your neighbor's input: Quantum advantage in Feige's game
• Authors: Simon Schmidt, Sigurd A. L. Storgaard, Michael Walter, Yuming Zhao,
• Abstract summary: We study a nonlocal game with two questions and three answers per player, which was first considered by Feige in 1991.<n>We prove that the game is a robust self-test for the $3$-dimensional maximally entangled state.
• Score: 3.160549625774197
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this article, we study a nonlocal game with two questions and three answers per player, which was first considered by Feige in 1991, and show that there is quantum advantage in this game. We prove that the game is a robust self-test for the $3$-dimensional maximally entangled state. Furthermore, we show that the game can be seen as the "or" of two games that each do not have quantum advantage. Lastly, we investigate the behavior of the game with respect to parallel repetition in the classical, quantum and non-signalling case and obtain perfect parallel repetition of the non-signalling value if Feige's game is repeated an even amount of times.

Related papers

• Quantum-Classical Separation in Bounded-Resource Tasks Arising from Measurement Contextuality [107.84586711462556]
  We show that quantum contextuality enables certain tasks to be performed with success probabilities beyond classical limits.<n>Our work proposes novel ways to benchmark quantum processors using contextuality-based algorithms.
  arXiv  Detail & Related papers  (2025-12-01T23:54:32Z)
• 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.<n>We establish a quantum soundness result for all compiled two-player nonlocal games.
  arXiv  Detail & Related papers  (2024-08-13T08:11:56Z)
• 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)
• Simple Tests of Quantumness Also Certify Qubits [69.96668065491183]
  A test of quantumness is a protocol that allows a classical verifier to certify (only) that a prover is not classical. We show that tests of quantumness that follow a certain template, which captures recent proposals such as (Kalai et al., 2022) can in fact do much more. Namely, the same protocols can be used for certifying a qubit, a building-block that stands at the heart of applications such as certifiable randomness and classical delegation of quantum computation.
  arXiv  Detail & Related papers  (2023-03-02T14:18:17Z)
• Counterexamples in self-testing [0.0]
  We study self-testing in nonlocal games. In particular, could it be that every 2-party nonlocal game or Bell inequality with a quantum advantage certifies the presence of a specific quantum state? Our counterexamples are based on a class of games to be of independent interest.
  arXiv  Detail & Related papers  (2022-12-22T09:52:18Z)
• Decidability of fully quantum nonlocal games with noisy maximally entangled states [5.076419064097734]
  This paper considers the decidability of fully quantum nonlocal games with noisy maximally entangled states. We prove that there is a computable upper bound on the copies of noisy maximally entangled states for the players to win a fully quantum nonlocal game with a probability arbitrarily close to the quantum value.
  arXiv  Detail & Related papers  (2022-11-19T08:11:02Z)
• Quantum guessing games with posterior information [68.8204255655161]
  A quantum guessing game with posterior information uses quantum systems to encode messages and classical communication to give partial information after a quantum measurement has been performed. We formalize symmetry of guessing games and characterize the optimal measurements in cases where the symmetry is related to an irreducible representation.
  arXiv  Detail & Related papers  (2021-07-25T19:10:26Z)
• Secure Two-Party Quantum Computation Over Classical Channels [63.97763079214294]
  We consider the setting where the two parties (a classical Alice and a quantum Bob) can communicate only via a classical channel. We show that it is in general impossible to realize a two-party quantum functionality with black-box simulation in the case of malicious quantum adversaries. We provide a compiler that takes as input a classical proof of quantum knowledge (PoQK) protocol for a QMA relation R and outputs a zero-knowledge PoQK for R that can be verified by classical parties.
  arXiv  Detail & Related papers  (2020-10-15T17:55:31Z)
• Infinitely Repeated Quantum Games and Strategic Efficiency [0.0]
  Repeated quantum game theory addresses long term relations among players who choose quantum strategies. In the conventional quantum game theory, single round quantum games or at most finitely repeated games have been widely studied.
  arXiv  Detail & Related papers  (2020-05-12T07:39:42Z)

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.