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 groups. Specifically, we show that graphs quantum isomorphic to a given graph are in bijective correspondence with Morita equivalence classes of certain Frobenius algebras in the category of finite-dimensional representations of the quantum automorphism algebra of that graph. We show that such a Frobenius algebra may be constructed from a central type subgroup of the classical automorphism group, whose action on the graph has coisotropic vertex stabilisers. In particular, if the original graph has no quantum symmetries, quantum isomorphic graphs are classified by such subgroups. We show that all quantum isomorphic graph pairs corresponding to a well-known family of binary constraint systems arise from this group-theoretical construction. We use our classification to show that, of the small order vertex-transitive graphs with no quantum symmetry, none is quantum isomorphic to a non-isomorphic graph. We show that this is in fact asymptotically almost surely true of all graphs.
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 groups. Specifically, we show that graphs quantum isomorphic to a given graph are in bijective correspondence with Morita equivalence classes of certain Frobenius algebras in the category of finite-dimensional representations of the quantum automorphism algebra of that graph. We show that such a Frobenius algebra may be constructed from a central type subgroup of the classical automorphism group, whose action on the graph has coisotropic vertex stabilisers. In particular, if the original graph has no quantum symmetries, quantum isomorphic graphs are classified by such subgroups. We show that all quantum isomorphic graph pairs corresponding to a well-known family of binary constraint systems arise from this group-theoretical construction. We use our classification to show that, of the small order vertex-transitive graphs with no quantum symmetry, none is quantum isomorphic to a non-isomorphic graph. We show that this is in fact asymptotically almost surely true of all graphs.
Part I: We present two new schemes for teleportation of a quantum state between parties whose local reference frames are misaligned by the action of a compact Lie group G. These schemes require no prior alignment of reference frames and are unaffected by arbitrary changes in reference frame alignment during execution, suiting them to situations of rapid reference frame drift. Our tight scheme yields improved purity compared to standard teleportation, in some cases substantially ---including the case of qubit teleportation under arbitrary SU(2) reference frame uncertainty--- while communicating no information about either party's reference frame alignment at any time. Our perfect scheme performs perfect teleportation, but does communicate some reference frame information. The mathematical foundation of these schemes is a unitary error basis permuted up to a phase by the conjugation action of a finite subgroup of G; we completely classify such unitary error bases for qubits, exhibit constructions in higher dimension, and provide a method for proving nonexistence in some cases. Part II: Quantum pseudo-telepathy is a phenomenon whereby two non-communicating parties can use the non-signalling correlations from shared quantum entanglement to perform a task that would ordinarily be impossible without communication. Here we consider the graph isomorphism game: an instance of the game is defined by a pair of graphs, and a perfect deterministic classical strategy precisely corresponds to an isomorphism of those graphs. We call a pair of graphs for which a perfect strategy using shared entanglement (a quantum strategy) exists pseudo-telepathic, and call a quantum strategy a quantum isomorphism between the graphs. Using a deep connection between noncommutative mathematics and nonlocal games, we classify all graphs quantum isomorphic to a given graph in terms of the quantum automorphism group of the graph. This implies a construction of quantum isomorphisms from central type subgroups of the ordinary automorphism group; we give an explicit description of the resulting quantum strategy and the new graph. We consider generation of new examples of quantum contextuality from central type groups. For abelian central type groups we show that this reduces to construction of quantum solutions of a binary linear constraint system from the abelianisation of its homogeneous solution group.
In 2019, Aterias et al. constructed pairs of quantum isomorphic, non-isomorphic graphs from linear constraint systems. This article deals with quantum automorphisms and quantum isomorphisms of colored versions of those graphs. We show that the quantum automorphism group of such a colored graph is the dual of the homogeneous solution group of the underlying linear constraint system. Given a vertex- and edge-colored graph with certain properties, we construct an uncolored graph that has the same quantum automorphism group as the colored graph we started with. Using those results, we obtain the first known example of a graph that has quantum symmetry and finite quantum automorphism group. Furthermore, we construct a pair of quantum isomorphic, non-isomorphic graphs that both have no quantum symmetry.
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. The goal of the players is to convince the verifier that the graphs G and H are isomorphic. In recent work along with Atserias et al. (J Comb Theory Ser 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.
Abstract We present an infinite sequence of finite graphs with trivial automorphism group and non‐trivial quantum automorphism group. These are the first known examples of graphs with this property. Moreover, to the best of our knowledge, these are the first examples of any asymmetric classical space that has non‐trivial quantum symmetries. Our construction is based on solution groups to (binary) linear systems, as defined by Cleve, Liu, and Slofstra in the context of non‐local games. We first show that the dual quantum group of every solution group occurs as the quantum automorphism group of some graph, and then construct an infinite sequence of systems whose solution groups are non‐trivial perfect groups. This leads to the desired sequence of graphs. In addition to our main result, we prove a number of related results that allow us to answer several open problems from the literature. We prove a weak quantum analog of Frucht's theorem, namely that every finite classical group occurs as the quantum automorphism group of a finite graph. Combined with our main result, this shows that, for every finite group , there are graphs and that both have classical automorphism group isomorphic to but one of them has quantum symmetry and the other does not. Therefore, the quantum automorphism group of a graph is never determined by its classical automorphism group, and there do not exist any “quantum excluding groups.”
In the past few decades, the connections between non-local games arising in quantum information theory and the theory of operator algebras have undergone a phase of significant development. Operator algebras provide a particularly fruitful framework for approaching questions of non-locality in quantum systems, as the input-output behavior of measurements on bipartite quantum systems can be encoded through noncommutative operator algebras and their state spaces. This thesis is the compilation of a series of papers, written by the author in collaboration with Ivan G. Todorov, utilizing this framework by using the theory of operator algebras and completely positive maps to study questions involving non-local games. ☐ Using the simulation paradigm from information theory, we define a quantized version of homomorphisms and isomorphisms between classical hypergraphs, generalizing quantum homomorphisms and isomorphisms of graphs from the literature. We show that these quantum homomorphisms and isomorphisms constitute pre-orders and equivalence relations, respectively. We use quantum homomorphisms of hypergraphs to provide multiple examples of strict separation between correlation classes of varying types. Specializing to the case when our underlying hypergraphs arise from classical non-local games, we define quantum non-local game homomorphisms and isomorphisms. We also show how the existence of a homomorphism or isomorphism of some fixed type between games is reflected in a comparison of optimal and asymptotic game values with respect to this type. These non-local game homomorphisms are defined via a new class of non-signalling correlations which we introduce here. We develop the multivariate tensor product theory in the category of operator systems, which we then use to provide a characterization of game homomorphisms in terms of state spaces for various tensor products of canonically associated operator systems. We then apply these results to the study of synchronous non-local games, defining jointly synchronous correlations and showing how they correspond to tracial states of tensor products of C*-algebras canonically associated to each game party. ☐ We then move to a second level of quantization by proposing a "quantized" notion of hypergraphs (where "quantum" here is in the sense of a non-commutative analogue for a discrete combinatorial object), and introduce quantum homomorphisms between these quantum objects. We provide an initial foray into the properties quantum morphisms between quantum hypergraphs display, showing they satisfy analogous properties to quantum homomorphisms between classical hypergraphs. We also indicate initial connections these quantum homomorphisms between quantum hypergraphs have to the study of quantum input-output games. We end the thesis showing that homomorphisms of a local type between quantum hypergraphs is closely related, and in some cases identical, to the TRO equivalence of finite-dimensionally acting operator spaces canonically associated with each hypergraph. This suggests a quantum information theoretic approach to Morita equivalence in the category of operator spaces.
We introduce a notion of quantum function and develop a compositional framework for finite quantum set theory based on a 2-category of quantum sets and quantum functions. We use this framework to formulate a 2-categorical theory of quantum graphs, which captures the quantum graphs and quantum graph homomorphisms recently discovered in the study of nonlocal games and zero-error communication and relates them to quantum automorphism groups of graphs considered in the setting of compact quantum groups. We show that the 2-categories of quantum sets and quantum graphs are semisimple. We analyze dualisable and invertible 1-morphisms in these 2-categories and show that they correspond precisely to the existing notions of quantum isomorphism and classical isomorphism between sets and graphs.