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 F if for each F ∈ 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 ≈ and a graph class F, such that homomorphism indistinguishability over F coincides with ≈. 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.