Perfect Games in Dimension-Bounded Communication

• URL: http://arxiv.org/abs/2608.05092v1
• Date: Wed, 05 Aug 2026 17:28:44 GMT
• Title: Perfect Games in Dimension-Bounded Communication
• Abstract summary: We show that perfect prepare-and-measure games exhibit an all-or-nothing quantum advantage.<n>A quantum system dimension $d$ satisfies every prescribed winning constraint, whereas a classical $d$-level message cannot.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Perfect prepare-and-measure games exhibit an all-or-nothing quantum advantage: a quantum system of dimension $d$ satisfies every prescribed winning constraint, whereas a classical $d$-level message cannot. We establish two structural results for such forbidden-output support constraints. First, every binary-output support game reduces exactly to a conflict graph: perfect classical realization with a $d$-level message is equivalent to $d$-colorability, perfect $d$-dimensional quantum realization is equivalent to a $d$-dimensional orthogonal representation, and the minimum number of Bob inputs realizing a fixed conflict graph is its edge biclique-cover number. Second, for an arbitrary finite output alphabet, every perfect qubit strategy admits a perfect classical-bit realization. As a flagship application, the $13$-ray qutrit graph yields a compressed game $(X,Y,B)=(13,8,2)$ with $C_3=39<Q_3=S=40$, and eight Bob inputs are minimal among all binary-output realizations of that graph. Graph extensions demonstrate the mechanism in every dimension, while Torpedo and antidistinguishability games illustrate the genuinely nonbinary regime. These results connect exact communication, graph coloring, contextuality, state exclusion, and zero-error information theory.

Related papers

• Optimal entanglement-assisted source coding under a balanced-difference promise [0.0]
  Entanglement can reduce the communication required for coding tasks, but establishing the minimum achievable cost is essential to understanding its limits.<n>We address this question in a zero-error source-coding task where Alice receives a word and Bob knows an unordered pair of candidates containing it.<n>We prove that the task requires exactly $n$ messages when $(q-1)ell$ is even and two messages when it is odd.
  arXiv  Detail & Related papers  (2026-09-14T15:43:27Z)
• Robust Quantum Memory Advantage from Contextuality [0.0]
  We show an exponential, noise-resilient memory advantage for quantum finite automata arising from graph-theoretic approaches to contextuality.<n>This memory advantage maintains an $mathcalO(1)$ threshold against both depolarizing and coherent noise.
  arXiv  Detail & Related papers  (2026-07-01T06:42:59Z)
• Quantum strategies, error bounds, optimality, and duality gaps for multiplayer XOR, $\mathrm{XOR}^{*}$, compiled XOR, $\mathrm{XOR}^{*}$, and strong parallel repetiton of XOR, $\mathrm{XOR}^{*}$, and FFL games [0.0]
  We characterize exact, and approximate, optimality of games that players can interact with using quantum strategies.<n>We conclude this effort by describing other variants of other possible strategies, as proposed sources for quantum advantage.
  arXiv  Detail & Related papers  (2025-05-09T03:47:41Z)
• Cloning Games, Black Holes and Cryptography [50.022147589030304]
  We introduce a new toolkit for analyzing cloning games.<n>This framework allows us to analyze a new cloning game based on binary phase states.<n>We show that the binary phase variantally optimal bound offers quantitative insights into information scrambling in idealized models of black holes.
  arXiv  Detail & Related papers  (2024-11-07T14:09:32Z)
• Vertex-minor universal graphs for generating entangled quantum subsystems [3.1758167940451987]
  We study the notion of $k$-stabilizer universal quantum state, that is, an $n$-qubit quantum state, such that it is possible to induce any stabilizer state on any $k$ qubits. These states generalize the notion of $k$-pairable states introduced by Bravyi et al., and can be studied from a perspective using graph states and $k$-vertex-minor universal graphs.
  arXiv  Detail & Related papers  (2024-02-09T09:17:19Z)
• Universality of graph homomorphism games and the quantum coloring problem [0.0]
  We show that quantum graph parameters encode winning strategies for all possible synchronous non-local games. Winning strategies for a synchronous game can be transformed into winning strategies for an associated graph coloring game.
  arXiv  Detail & Related papers  (2023-05-29T14:28:28Z)
• Global Nash Equilibrium in Non-convex Multi-player Game: Theory and Algorithms [66.8634598612777]
  We show that Nash equilibrium (NE) is acceptable to all players in a multi-player game. We also show that no one can benefit unilaterally from the general theory step by step.
  arXiv  Detail & Related papers  (2023-01-19T11:36:50Z)
• Exponential Separation between Quantum and Classical Ordered Binary Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
  We study quantum Ordered Binary Decision Diagrams($OBDD$) model. We prove lower bounds and upper bounds for OBDD with arbitrary order of input variables. We extend hierarchy for read$k$-times Ordered Binary Decision Diagrams ($k$-OBDD$) of width.
  arXiv  Detail & Related papers  (2022-04-22T12:37:56Z)
• Near-Optimal Learning of Extensive-Form Games with Imperfect Information [54.55092907312749]
  We present the first line of algorithms that require only $widetildemathcalO((XA+YB)/varepsilon2)$ episodes of play to find an $varepsilon$-approximate Nash equilibrium in two-player zero-sum games. This improves upon the best known sample complexity of $widetildemathcalO((X2A+Y2B)/varepsilon2)$ by a factor of $widetildemathcalO(maxX,
  arXiv  Detail & Related papers  (2022-02-03T18:18:28Z)
• 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)
• Quantum double aspects of surface code models [77.34726150561087]
  We revisit the Kitaev model for fault tolerant quantum computing on a square lattice with underlying quantum double $D(G)$ symmetry. We show how our constructions generalise to $D(H)$ models based on a finite-dimensional Hopf algebra $H$.
  arXiv  Detail & Related papers  (2021-06-25T17:03: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.