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
- 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) - 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) - 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) - Qudit lattice surgery [91.3755431537592]
We observe that lattice surgery, a model of fault-tolerant qubit computation, generalises straightforwardly to arbitrary finite-dimensional qudits.
We relate the model to the ZX-calculus, a diagrammatic language based on Hopf-Frobenius algebras.
arXiv Detail & Related papers (2022-04-27T23:41:04Z) - 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.