Homomorphism Indistinguishability Relations induced by Quantum Groups

• URL: http://arxiv.org/abs/2505.07922v1
• Date: Mon, 12 May 2025 16:58:51 GMT
• Title: Homomorphism Indistinguishability Relations induced by Quantum Groups
• Authors: Tim Seppelt, Gian Luca Spitzer,
• Abstract summary: Homomorphism indistinguishability is a way of characterising many natural equivalence relations on graphs.<n>We generalise Manvcinska and Roberson's result to all easy quantum groups.
• Score: 0.23020018305241333
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: Homomorphism indistinguishability is a way of characterising many natural equivalence relations on graphs. Two graphs $G$ and $H$ are called homomorphism indistinguishable over a graph class $\mathcal{F}$ if for each $F \in \mathcal{F}$, the number of homomorphisms from $F$ to $G$ equals the number of homomorphisms from $F$ to $H$. Examples of such equivalence relations include isomorphism and cospectrality, as well as equivalence with respect to many formal logics. Quantum groups are a generalisation of topological groups that describe "non-commutative symmetries" and, inter alia, have applications in quantum information theory. An important subclass are the easy quantum groups, which enjoy a combinatorial characterisation and have been fully classified by Raum and Weber. A recent connection between these seemingly distant concepts was made by Man\v{c}inska and Roberson, who showed that quantum isomorphism, a relaxation of classical isomorphism that can be phrased in terms of the quantum symmetric group, is equivalent to homomorphism indistinguishability over the class of planar graphs. We generalise Man\v{c}inska and Roberson's result to all orthogonal easy quantum groups. We obtain for each orthogonal easy quantum group a graph isomorphism relaxation $\approx$ and a graph class $\mathcal{F}$, such that homomorphism indistinguishability over $\mathcal{F}$ coincides with $\approx$. Our results include a full classification of the $(0, 0)$-intertwiners of the graph-theoretic quantum group obtained by adding the adjacency matrix of a graph to the intertwiners of an orthogonal easy quantum group.

Related papers

• NPA Hierarchy for Quantum Isomorphism and Homomorphism Indistinguishability [0.18749305679160366]
  We show that each level of the NPA hierarchy of SDP relaxations for quantum isomorphism of graphs is equivalent to homomorphism indistinguishability over an appropriate class of planar graphs.<n>This homomorphism indistinguishability characterization also allows us to give a randomized-time algorithm deciding exact feasibility of each fixed level of the NPA hierarchy of SDP relaxations for quantum isomorphism.
  arXiv  Detail & Related papers  (2024-07-15T11:48:09Z)
• Quantum Current and Holographic Categorical Symmetry [62.07387569558919]
  A quantum current is defined as symmetric operators that can transport symmetry charges over an arbitrary long distance. The condition for quantum currents to be superconducting is also specified, which corresponds to condensation of anyons in one higher dimension.
  arXiv  Detail & Related papers  (2023-05-22T11:00:25Z)
• Planar #CSP Equality Corresponds to Quantum Isomorphism -- A Holant Viewpoint [0.0]
  Graph homomorphism is the special case where each of $mathcalF$ and $mathcalF'$ contains a single symmetric 0-1-valued binary constraint function. We show that any pair of sets $mathcalF$ and $mathcalF'$ of real-valued, arbitrary-arity constraint functions give the same value on any planar #CSP instance.
  arXiv  Detail & Related papers  (2022-12-06T21:38:40Z)
• Quantum isomorphism of graphs from association schemes [0.0]
  We show that any two Hadamard graphs on the same number of vertices are quantum isomorphic. This follows from a more general recipe for showing quantum isomorphism of graphs arising from certain association schemes.
  arXiv  Detail & Related papers  (2022-09-10T03:22:28Z)
• Algebraic Aspects of Boundaries in the Kitaev Quantum Double Model [77.34726150561087]
  We provide a systematic treatment of boundaries based on subgroups $Ksubseteq G$ with the Kitaev quantum double $D(G)$ model in the bulk. The boundary sites are representations of a $*$-subalgebra $Xisubseteq D(G)$ and we explicate its structure as a strong $*$-quasi-Hopf algebra. As an application of our treatment, we study patches with boundaries based on $K=G$ horizontally and $K=e$ vertically and show how these could be used in a quantum computer
  arXiv  Detail & Related papers  (2022-08-12T15:05:07Z)
• Quantum teleportation in the commuting operator framework [63.69764116066747]
  We present unbiased teleportation schemes for relative commutants $N'cap M$ of a large class of finite-index inclusions $Nsubseteq M$ of tracial von Neumann algebras. We show that any tight teleportation scheme for $N$ necessarily arises from an orthonormal unitary Pimsner-Popa basis of $M_n(mathbbC)$ over $N'$.
  arXiv  Detail & Related papers  (2022-08-02T00:20:46Z)
• 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)
• Uncertainties in Quantum Measurements: A Quantum Tomography [52.77024349608834]
  The observables associated with a quantum system $S$ form a non-commutative algebra $mathcal A_S$. It is assumed that a density matrix $rho$ can be determined from the expectation values of observables. Abelian algebras do not have inner automorphisms, so the measurement apparatus can determine mean values of observables.
  arXiv  Detail & Related papers  (2021-12-14T16:29:53Z)
• Classification of equivariant quasi-local automorphisms on quantum chains [0.0]
  We classify automorphisms on quantum chains, allowing both spin and fermionic degrees of freedom, that are equivariant with respect to a local symmetry action of a finite symmetry group $G$. We find that the equivalence classes are uniquely labeled by an index taking values in $mathbbQ cup sqrt2 mathbbQ times mathrmHom(G, mathbbZ_2) times H2(G, U(1))$.
  arXiv  Detail & Related papers  (2021-06-03T21:41:05Z)
• The Geometry of Time in Topological Quantum Gravity of the Ricci Flow [41.94295877935867]
  We continue the study of nonrelativistic quantum gravity associated with a family of Ricci flow equations.<n>This topological gravity is of the cohomological type, and it exhibits an $cal N=2$ extended BRST symmetry.<n>We demonstrate a standard one-step BRST gauge-fixing of a theory whose fields are $g_ij$, $ni$ and $n$, and whose gauge symmetries consist of (i) the topological deformations of $g_ij$, and (ii) the ultralocal nonrelativistic limit of space
  arXiv  Detail & Related papers  (2020-11-12T06:57:10Z)
• Sub-bosonic (deformed) ladder operators [62.997667081978825]
  We present a class of deformed creation and annihilation operators that originates from a rigorous notion of fuzziness. This leads to deformed, sub-bosonic commutation relations inducing a simple algebraic structure with modified eigenenergies and Fock states. In addition, we investigate possible consequences of the introduced formalism in quantum field theories, as for instance, deviations from linearity in the dispersion relation for free quasibosons.
  arXiv  Detail & Related papers  (2020-09-10T20:53:58Z)
• Graph Homomorphism Convolution [19.94778871237204]
  We show that graph homomorphism numbers provide a natural invariant (isomorphism invariant and $mathcalF$-invariant) embedding maps which can be used for graph classification. By choosing $mathcalF$ whose elements have bounded tree-width, we show that the homomorphism method is efficient compared with other methods.
  arXiv  Detail & Related papers  (2020-05-03T23:56:20Z)

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.