Constructive nonlocal games with very small classical values

• URL: http://arxiv.org/abs/2112.07741v3
• Date: Wed, 06 Nov 2024 09:49:44 GMT
• Title: Constructive nonlocal games with very small classical values
• Authors: M. Rosicka, S. Szarek, A. Rutkowski, P. Gnaciński, M. Horodecki,
• Abstract summary: This paper is devoted to analyzing classical values of the so-called linear games. We employ nontrivial results from graph theory and number theoretic results used earlier in the context of harmonic analysis.
• Score: 0.0
• License:
• Abstract: There are few explicit examples of two player nonlocal games with a large gap between classical and quantum value. One of the reasons is that estimating the classical value is usually a hard computational task. This paper is devoted to analyzing classical values of the so-called linear games (generalization of XOR games to a larger number of outputs). We employ nontrivial results from graph theory and combine them with number theoretic results used earlier in the context of harmonic analysis to obtain a novel tool -- {\it the girth method} -- allowing to provide explicit examples of linear games with prescribed low classical value. In particular, we provide games with minimal possible classical value. We then speculate on the potential unbounded violation, by comparing the obtained classical values with a known upper bound for the quantum value. If this bound can be even asymptotically saturated, our games would have the best ratio of quantum to classical value as a function of the product of the number of inputs and outputs when compared to other explicit (i.e. non-random) constructions.

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)
• 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)
• On the power of geometrically-local classical and quantum circuits [6.011628409537168]
  We show a relation, based on parallel repetition of the Magic Square game, that can be solved, with probability exponentially close to $1$. We show that the same relation cannot be solved, with an exponentially small success probability. We propose a protocol that can potentially demonstrate verifiable quantum advantage in the NISQ era.
  arXiv  Detail & Related papers  (2023-10-02T18:27:53Z)
• On the power of quantum entanglement in multipartite quantum XOR games [3.655021726150368]
  In particular, quantum entanglement can be a much more powerful resource than local operations and classical communication to play these games. This result shows a strong contrast to the bipartite case, where it was recently proved that the entangled bias is always upper bounded by a universal constant times the one-way classical communication bias.
  arXiv  Detail & Related papers  (2023-02-23T06:26:37Z)
• Learning Correlated Equilibria in Mean-Field Games [62.14589406821103]
  We develop the concepts of Mean-Field correlated and coarse-correlated equilibria. We show that they can be efficiently learnt in emphall games, without requiring any additional assumption on the structure of the game.
  arXiv  Detail & Related papers  (2022-08-22T08:31:46Z)
• Why we should interpret density matrices as moment matrices: the case of (in)distinguishable particles and the emergence of classical reality [69.62715388742298]
  We introduce a formulation of quantum theory (QT) as a general probabilistic theory but expressed via quasi-expectation operators (QEOs) We will show that QT for both distinguishable and indistinguishable particles can be formulated in this way. We will show that finitely exchangeable probabilities for a classical dice are as weird as QT.
  arXiv  Detail & Related papers  (2022-03-08T14:47:39Z)
• On the relation between completely bounded and $(1,cb)$-summing maps with applications to quantum XOR games [65.51757376525798]
  We show that given a linear map from a general operator space into the dual of a C$*$-algebra, its completely bounded norm is upper bounded by a universal constant times its $(''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
  arXiv  Detail & Related papers  (2021-12-09T21:06:52Z)
• Probing quantum effects with classical stochastic analogs [0.0]
  We propose a method to construct a classical analog of an open quantum system. The classical analog is made out of a collection of identical wells where classical particles of mass $m$ are trapped.
  arXiv  Detail & Related papers  (2020-12-13T18:02:27Z)
• 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)
• Quantum-over-classical Advantage in Solving Multiplayer Games [0.0]
  Subtraction games are sometimes referred to as one-heap Nim games. In quantum game theory, a subset of Subtraction games became the first explicitly defined class of zero-sum games. For a narrower subset of Subtraction games, an exact quantum sublinear algorithm is known that surpasses all deterministic algorithms.
  arXiv  Detail & Related papers  (2020-06-12T06:36:07Z)

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.