论文标题
图形同构：物理资源，优化模型和代数特征
Graph isomorphism: Physical resources, optimization models, and algebraic characterizations
论文作者
论文摘要
在$（g，h）$ - 同构游戏中，一个验证者通过私下向$ g $或$ h $发送每个随机顶点而与两个非交流玩家（称为掠夺）进行互动，其目的是说服验证者两个图形$ g $和$ h $是iSomorphic。在最近与Atserias，šámal和Severini的工作中[组合理论杂志，系列B，136：89--328，2019]，我们表明，如果允许鉴定可以共享量子资源，则可以确信一个验证者是同构的两个非同构图。在本文中，我们通过在某些复杂的凸锥上进行线性约束来对经典和量子图同构进行建模，然后我们将其放松到一对可拖动的凸模型（半芬特程序）。我们的主要结果是根据适当的矩阵代数对相应的等效关系的完全代数表征。我们的技术是代数，组合，优化和量子信息的有趣组合。
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, Šámal 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.
