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

DOI10.1007/S10107-023-01989-7MaRDI QIDQ6126661zbMATH OpenOpenAlexFDO

Authors L. Mančinska, David Roberson, A. Varvitsiotis

Publication date 9 April 2024

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2004.10893

zbMATH Keywords

\((G, H)\)-isomorphism gamequantum graph isomorphismquantum information

Mathematics Subject Classification ID

Games on graphs (graph-theoretic aspects) (05C57) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Quantum information, communication, networks (quantum-theoretic aspects) (81P45) Semidefinite programming (90C22) Convex programming (90C25) 2-person games (91A05) Games involving graphs (91A43)

Abstract: 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 convince the verifier that two graphs $G$ and $H$ are isomorphic. In recent work along with Atserias, v{S}'amal and Severini [Journal of Combinatorial Theory, Series B, 136:89--328, 2019] we showed that a verifier can be convinced that two non-isomorphic graphs are isomorphic, if the provers are allowed to share quantum resources. In this paper we model classical and quantum graph isomorphism by linear constraints over certain complicated convex cones, which we then relax to a pair of tractable convex models (semidefinite programs). Our main result is a complete algebraic characterization of the corresponding equivalence relations on graphs in terms of appropriate matrix algebras. Our techniques are an interesting mix of algebra, combinatorics, optimization, and quantum information.

Recommendations

• Quantum and non-signalling graph isomorphisms
• Relaxations of graph isomorphism
• Bigalois extensions and the graph isomorphism game
• The Morita theory of quantum graph isomorphisms
• Quantum homomorphisms

Cites work

• C^*-algebras and finite-dimensional approximations
• A comparison of the Delsarte and Lovász bounds
• Approximation algorithms and semidefinite programming.
• Approximation of the stability number of a graph via copositive programming
• Coherent algebras and the graph isomorphism problem
• Completely positive linear maps on complex matrices
• Conic approach to quantum graph parameters using linear optimization over the completely positive semidefinite cone
• Conic formulations of graph homomorphisms
• Copositive programming motivated bounds on the stability and the chromatic numbers
• Handbook of product graphs
• scientific article; zbMATH DE number 43547 (Why is no real title available?)
• scientific article; zbMATH DE number 3614188 (Why is no real title available?)
• Linear conic formulations for two-party correlations and values of nonlocal games
• On construction and identification of graphs. With contributions by A. Lehman, G. M. Adelson-Velsky, V. Arlazarov, I. Faragev, A. Uskov, I. Zuev, M. Rosenfeld and B. Weisfeiler
• On the copositive representation of binary and continuous nonconvex quadratic programs
• On the Polynomial of a Graph
• Quantum and non-signalling graph isomorphisms
• Quantum computation and quantum information. 10th anniversary edition
• Quantum graph homomorphisms via operator systems
• The set of quantum correlations is not closed
• The theory of quantum information

Cited in

(1)

• Lasserre hierarchy for graph isomorphism and homomorphism indistinguishability

This page was built for publication: Graph isomorphism: physical resources, optimization models, and algebraic characterizations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6126661)