# Quantum isomorphism is equivalent to equality of homomorphism counts from planar graphs

@article{Maninska2020QuantumII, title={Quantum isomorphism is equivalent to equality of homomorphism counts from planar graphs}, author={Laura Man{\vc}inska and David E. Roberson}, journal={2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS)}, year={2020}, pages={661-672} }

Over 50 years ago, Lovász proved that two graphs are isomorphic if and only if they admit the same number of homomorphisms from any graph. Other equivalence relations on graphs, such as cospectrality or fractional isomorphism, can be characterized by equality of homomorphism counts from an appropriately chosen class of graphs. Dvořák [J. Graph Theory 2010] showed that taking this class to be the graphs of treewidth at most $k$ yields a tractable relaxation of graph isomorphism known as $k… Expand

#### 22 Citations

Graph isomorphism: Physical resources, optimization models, and algebraic characterizations

- Mathematics
- 2020

In the $(G,H)$-isomorphism game, a verifier interacts with two non-communicating players (called provers) by privately sending each of them a random vertex from either $G$ or $H$, whose aim is to… Expand

Graph Similarity and Homomorphism Densities

- Computer Science
- ICALP
- 2021

The fairly general statement that, for every “reasonably” defined graphon pseudometric, an exact correspondence to homomorphism densities can be turned into an approximate one is proved. Expand

Graph Similarity and Homomorphism Densities

- Computer Science, Mathematics
- 2021

The fairly general statement that, for every “reasonably” defined graphon pseudometric, an exact correspondence to homomorphism densities can be turned into an approximate one is proved. Expand

Lovász-Type Theorems and Game Comonads

- Computer Science, Mathematics
- 2021 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)
- 2021

This work proposes a new categorical formulation, which applies to any locally finite category with pushouts and a proper factorisation system, and presents a novel application to homomorphism counts in modal logic. Expand

The quantum-to-classical graph homomorphism game

- Mathematics, Physics
- 2020

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… Expand

Quantum Cuntz-Krieger algebras

- Mathematics
- 2020

Motivated by the theory of Cuntz-Krieger algebras we define and study $ C^\ast $-algebras associated to directed quantum graphs. For classical graphs the $ C^\ast $-algebras obtained this way can be… Expand

Counting Bounded Tree Depth Homomorphisms

- Computer Science, Mathematics
- LICS
- 2020

We prove that graphs G, G' satisfy the same sentences of first-order logic with counting of quantifier rank at most k if and only if they are homomorphism-indistinguishable over the class of all… Expand

Quantum partial automorphisms of finite graphs

- Mathematics
- 2021

The partial automorphisms of a graphX havingN vertices are the bijections σ : I → J with I, J ⊂ {1, . . . , N} which leave invariant the edges. These bijections form a semigroup G̃(X), which contains… Expand

Some examples of quantum graphs

- Mathematics, Physics
- 2021

We summarize different approaches to the theory of quantum graphs and provide several ways to construct concrete examples. First, we classify all undirected quantum graphs on the quantum space M2.… Expand

Sinkhorn Algorithm for Quantum Permutation Groups

- Mathematics
- Experimental Mathematics
- 2021

We introduce a Sinkhorn-type algorithm for producing quantum permutation matrices encoding symmetries of graphs. Our algorithm generates square matrices whose entries are orthogonal projections onto… Expand

#### References

SHOWING 1-10 OF 66 REFERENCES

Relaxations of Graph Isomorphism

- Computer Science
- ICALP
- 2017

It is shown that both classical and quantum isomorphism can be reformulated as feasibility programs over the completely positive and completely positive semidefinite cones respectively, and that DNN-isomorphism is equivalent to the previous defined notion of graph equivalence, a polynomialtime decidable relation that is related to coherent algebras. Expand

The Morita Theory of Quantum Graph Isomorphisms

- Mathematics, Physics
- 2018

We classify instances of quantum pseudo-telepathy in the graph isomorphism game, exploiting the recently discovered connection between quantum information and the theory of quantum automorphism… Expand

Bigalois Extensions and the Graph Isomorphism Game

- Physics, Mathematics
- Communications in Mathematical Physics
- 2019

We study the graph isomorphism game that arises in quantum information theory. We prove that the non-commutative algebraic notion of a quantum isomorphism between two graphs is same as the more… Expand

Nonlocal games and quantum permutation groups

- Mathematics, Physics
- 2017

We present a strong connection between quantum information and quantum permutation groups. Specifically, we define a notion of quantum isomorphisms of graphs based on quantum automorphisms from the… Expand

Lovász Meets Weisfeiler and Leman

- Mathematics, Computer Science
- ICALP
- 2018

In this paper, we relate a beautiful theory by Lov\'asz with a popular heuristic algorithm for the graph isomorphism problem, namely the color refinement algorithm and its k-dimensional… Expand

Quantum and non-signalling graph isomorphisms

- Computer Science, Mathematics
- J. Comb. Theory, Ser. B
- 2019

It is shown that quantum isomorphic graphs are necessarily cospectral, and a construction for reducing linear binary constraint system games to isomorphism games is provided, related to the FGLSS reduction from inapproximability literature, as well as the CFI construction. Expand

On the quantum symmetry of distance-transitive graphs

- Mathematics
- 2020

Abstract In this article, we study quantum automorphism groups of distance-transitive graphs. We show that the odd graphs, the Hamming graphs H ( n , 3 ) , the Johnson graphs J ( n , 2 ) and the… Expand

Quantum Symmetries of Graph C *-algebras

- Mathematics
- Canadian Mathematical Bulletin
- 2018

Abstract The study of graph ${{C}^{*}}$ -algebras has a long history in operator algebras. Surprisingly, their quantum symmetries have not yet been computed. We close this gap by proving that the… Expand

Base collapse of holographic algorithms

- Mathematics, Computer Science
- STOC
- 2016

It is proved for any n, the base collapse to a r≤ ⌊ logn ⌋, under some similar conditions, that the original problem is defined by one symmetric function. Expand

On the complexity of zero gap MIP

- Mathematics, Computer Science
- ICALP
- 2020

This paper proves that $\mathsf{MIP}^*_0$ extends beyond the first level of the arithmetical hierarchy, and in fact is equal to $\Pi_2^0$, the class of languages that can be decided by quantified formulas of the form $\forall y \, \exists z \, R(x,y,z)$. Expand