Communication Complexity of Graph Isomorphism, Coloring, and Distance Games

• URL: http://arxiv.org/abs/2406.02199v2
• Date: Tue, 25 Jun 2024 15:14:39 GMT
• Title: Communication Complexity of Graph Isomorphism, Coloring, and Distance Games
• Authors: Pierre Botteron, Moritz Weber,
• Abstract summary: 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.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In quantum information, nonlocal games are particularly useful for differentiating classical, quantum, and non-signalling correlations. An example of differentiation is given by the principle of no-collapse of communication complexity, which is often interpreted as necessary for a feasible physical theory. It is satisfied by quantum correlations but violated by some non-signalling ones. In this work, we investigate this principle in the context of three nonlocal games related to graph theory, starting from the well-known graph isomorphism and graph coloring games, and introducing a new game, the vertex distance game, with a parameter $D\in\mathbb N$, that generalizes the former two to some extent. For these three games, we prove that perfect non-signalling strategies collapse communication complexity under favorable conditions. We also define a refinement of fractional isomorphism of graphs, namely D-fractional isomorphisms, and we show that this characterizes perfect non-signalling strategies for the vertex distance game. Surprisingly, we observe that non-signalling strategies provide a finer distinction for the new game compared to classical and quantum strategies since the parameter D is visible only in the non-signalling setting.

Related papers

• Transfer of quantum game strategies [0.0]
  We show a new class of QNS correlations needed for the transfer of strategies between games. We define jointly tracial correlations and show they correspond to traces acting on tensor products of canonical $rm C*$-algebras associated with individual game parties.
  arXiv  Detail & Related papers  (2024-10-12T17:25:58Z)
• Graphon Pooling for Reducing Dimensionality of Signals and Convolutional Operators on Graphs [131.53471236405628]
  We present three methods that exploit the induced graphon representation of graphs and graph signals on partitions of [0, 1]2 in the graphon space. We prove that those low dimensional representations constitute a convergent sequence of graphs and graph signals. We observe that graphon pooling performs significantly better than other approaches proposed in the literature when dimensionality reduction ratios between layers are large.
  arXiv  Detail & Related papers  (2022-12-15T22:11:34Z)
• G-MSM: Unsupervised Multi-Shape Matching with Graph-based Affinity Priors [52.646396621449]
  G-MSM is a novel unsupervised learning approach for non-rigid shape correspondence. We construct an affinity graph on a given set of training shapes in a self-supervised manner. We demonstrate state-of-the-art performance on several recent shape correspondence benchmarks.
  arXiv  Detail & Related papers  (2022-12-06T12:09:24Z)
• Finding mixed-strategy equilibria of continuous-action games without gradients using randomized policy networks [83.28949556413717]
  We study the problem of computing an approximate Nash equilibrium of continuous-action game without access to gradients. We model players' strategies using artificial neural networks. This paper is the first to solve general continuous-action games with unrestricted mixed strategies and without any gradient information.
  arXiv  Detail & Related papers  (2022-11-29T05:16:41Z)
• Quantum hypergraph homomorphisms and non-local games [1.0152838128195465]
  We show that notions of quantum hypergraph homomorphisms and quantum hypergraph isomorphisms constitute partial orders and equivalence relations, respectively. Specialising to the case where the underlying hypergraphs arise from non-local games, we define notions of quantum non-local game homomorphisms and quantum non-local game isomorphisms.
  arXiv  Detail & Related papers  (2022-11-09T12:44:24Z)
• Arkhipov's theorem, graph minors, and linear system nonlocal games [0.0]
  We study the solution groups of graph incidence games in which the underlying linear system is the incidence system of a two-coloured graph. Arkhipov's theorem states that the graph incidence game of a connected graph has a perfect quantum strategy if and only if it either has a perfect classical strategy, or the graph is nonplanar. We extend Arkhipov's theorem by showing that, for graph incidence games of connected two-coloured graphs, every quotient closed property of the solution group has a forbidden minor characterization.
  arXiv  Detail & Related papers  (2022-05-10T03:21:38Z)
• 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-Spatial Global Graph Reasoning for Hyperspectral Image Classification [50.899576891296235]
  Convolutional neural networks have been widely applied to hyperspectral image classification. Recent methods attempt to address this issue by performing graph convolutions on spatial topologies.
  arXiv  Detail & Related papers  (2021-06-26T06:24:51Z)
• 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)
• The quantum-to-classical graph homomorphism game [0.0]
  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.
  arXiv  Detail & Related papers  (2020-09-15T17:09:35Z)
• Spectra of Perfect State Transfer Hamiltonians on Fractal-Like Graphs [62.997667081978825]
  We study the spectral features, on fractal-like graphs, of Hamiltonians which exhibit the special property of perfect quantum state transfer. The essential goal is to develop the theoretical framework for understanding the interplay between perfect quantum state transfer, spectral properties, and the geometry of the underlying graph.
  arXiv  Detail & Related papers  (2020-03-25T02:46:14Z)

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.