The quantum-to-classical graph homomorphism game

• URL: http://arxiv.org/abs/2009.07229v2
• Date: Thu, 23 Sep 2021 17:35:27 GMT
• Title: The quantum-to-classical graph homomorphism game
• Authors: Michael Brannan, Priyanga Ganesan, Samuel J. Harris
• Abstract summary: We introduce a graph homomorphism game between quantum graphs and classical graphs. We show that winning strategies in the various quantum models for the game is an analogue of the notion of non-commutative graph homomorphisms. We also demonstrate explicit quantum colorings of all quantum complete graphs, yielding the surprising fact that the algebra of the $4$-coloring game for a quantum graph is always non-trivial.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Motivated by non-local games and quantum coloring problems, we introduce a graph homomorphism game between quantum graphs and classical graphs. This game is naturally cast as a "quantum-classical game"--that is, a non-local game of two players involving quantum questions and classical answers. This game generalizes the graph homomorphism game between classical graphs. We show that winning strategies in the various quantum models for the game is an analogue of the notion of non-commutative graph homomorphisms due to D. Stahlke [44]. Moreover, we present a game algebra in this context that generalizes the game algebra for graph homomorphisms given by J.W. Helton, K. Meyer, V.I. Paulsen and M. Satriano [22]. We also demonstrate explicit quantum colorings of all quantum complete graphs, yielding the surprising fact that the algebra of the $4$-coloring game for a quantum graph is always non-trivial, extending a result of [22].

Related papers

• Quantum Games and Synchronicity [0.0]
  We extend nonlocal games to allow quantum questions and answers. Equations are presented using a diagrammatic calculus for tensor categories. We extend the standard definitions, including strategies, correlations, and synchronicity.
  arXiv  Detail & Related papers  (2024-08-27T23:27:59Z)
• 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)
• Communication Complexity of Graph Isomorphism, Coloring, and Distance Games [0.0]
  We show that perfect non-signalling strategies collapse communication complexity under favorable conditions. Surprisingly, we observe that non-signalling strategies provide a finer distinction for the new game compared to classical and quantum strategies.
  arXiv  Detail & Related papers  (2024-06-04T10:53:16Z)
• 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)
• The quantum commuting model (Ia): The CHSH game and other examples: Uniqueness of optimal states [91.3755431537592]
  We use the universal description of quantum commuting correlations as state space on the universal algebra for two player games. We find that the CHSH game leaves a single optimal state on this common algebra.
  arXiv  Detail & Related papers  (2022-10-07T17:38:31Z)
• Quantum Extensive Form Games [0.0]
  We propose a concept of quantum extensive-form games, which is a quantum extension of classical extensive-form games. A quantum extensive-form game is also a generalization of quantum learning, including Quantum Generative Adrial Networks.
  arXiv  Detail & Related papers  (2022-07-12T09:58:21Z)
• From Quantum Graph Computing to Quantum Graph Learning: A Survey [86.8206129053725]
  We first elaborate the correlations between quantum mechanics and graph theory to show that quantum computers are able to generate useful solutions. For its practicability and wide-applicability, we give a brief review of typical graph learning techniques. We give a snapshot of quantum graph learning where expectations serve as a catalyst for subsequent research.
  arXiv  Detail & Related papers  (2022-02-19T02:56:47Z)
• 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)
• Spectral bounds for the quantum chromatic number of quantum graphs [0.0]
  We obtain lower bounds for the classical and quantum number of a quantum graph using eigenvalues of the quantum adjacency matrix. We generalize all the spectral bounds given by Elphick and Wocjan to the quantum graph setting. Our results are achieved using techniques from linear algebra and a complete definition of quantum graph coloring.
  arXiv  Detail & Related papers  (2021-12-03T05:36:21Z)
• 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)
• 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)

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.