Abstract We develop an algebraic and operational framework for quantum isomorphisms of hypergraphs, using tools from compact quantum group theory. We introduce a new synchronous version of the hypergraph isomorphism game whose game algebra uniformly encodes multiple notions of quantum isomorphisms of hypergraphs. We show that there exist hypergraphs that are quantum isomorphic but not classically isomorphic. For graphs, we show that the ‐algebra of the hypergraph isomorphism game is a quotient of the ‐algebra of the graph isomorphism game. We further prove that the hypergraph game algebra forms a bi‐Galois extension over the quantum automorphism groups of the underlying hypergraphs. This allows us to deduce that the algebraic notion of a quantum isomorphism of hypergraphs coincides with the operational one coming from the existence of perfect quantum strategies. Viewing games themselves as hypergraphs, we analyze isomorphisms and the transfer of strategies within this setting. Finally, we construct a ‐algebra whose representation theory characterizes distinct classes of quantum isomorphisms between nonlocal games.
Abstract We develop an algebraic and operational framework for quantum isomorphisms of hypergraphs, using tools from compact quantum group theory. We introduce a new synchronous version of the hypergraph isomorphism game whose game algebra uniformly encodes multiple notions of quantum isomorphisms of hypergraphs. We show that there exist hypergraphs that are quantum isomorphic but not classically isomorphic. For graphs, we show that the ‐algebra of the hypergraph isomorphism game is a quotient of the ‐algebra of the graph isomorphism game. We further prove that the hypergraph game algebra forms a bi‐Galois extension over the quantum automorphism groups of the underlying hypergraphs. This allows us to deduce that the algebraic notion of a quantum isomorphism of hypergraphs coincides with the operational one coming from the existence of perfect quantum strategies. Viewing games themselves as hypergraphs, we analyze isomorphisms and the transfer of strategies within this setting. Finally, we construct a ‐algebra whose representation theory characterizes distinct classes of quantum isomorphisms between nonlocal games.
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 define and study a collection of matroid isomorphism games corresponding to various axiomatic characterizations of matroids. These are nonlocal games played between two cooperative players. Each game is played on two matroids, and the matroids are isomorphic if and only if the game has a perfect classical winning strategy. We define notions of quantum isomorphism in terms of perfect quantum commuting strategies, and we find a pair of nonisomorphic matroids that are quantum isomorphic. We also give a purely algebraic characterization of quantum isomorphic matroids. Finally, we use this notion of quantum isomorphism to describe a new type of quantum automorphism group of a matroid and derive a sufficient condition for a matroid to have nonclassical quantum automorphism.
In the flavour of categorical quantum mechanics, we extend nonlocal games to allow quantum questions and answers, using quantum sets (special symmetric dagger Frobenius algebras) and the quantum functions of Musto, Reutter, and Verdon. Equations are presented using a diagrammatic calculus for tensor categories. To this quantum question and answer setting, we extend the standard definitions, including strategies, correlations, and synchronicity, and we use these definitions to extend results about synchronicity. We extend the graph homomorphism (isomorphism) game to quantum graphs, and show it is synchronous (bisynchronous) and connect its perfect (bi)strategies to quantum graph homomorphisms (isomorphisms). Our extended definitions agree with the existing quantum games literature, except in the case of synchronicity.
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.
Mathematical models of quantum mechanics can be studied and distinguished using nonlocal games. We discuss a class of nonlocal games called synchronous linear constraint system (syncLCS) games. We unify two algebraic approaches to studying syncLCS games and relate these games to nonlocal games played on graphs, known as graph isomorphism games. In more detail, syncLCS games are nonlocal games that verify whether or not two players share a solution to a given system of equations. Two algebraic objects associated with these games encode information about the existence of perfect strategies. They are called the game algebra and the solution group. Here, we show that these objects are essentially the same, i.e., the game algebra is a suitable quotient of the group algebra of the solution group. We also demonstrate that syncLCS games are equivalent to graph isomorphism games on a pair of graphs parameterized by the linear system.
Quantum non-local games with quantum inputs or outputs have been formulated in several different languages, including rank-one and quantum XOR games, support maps between projection lattices, probabilistic quantum hypergraphs, and Frobenius-algebraic rule operators on finite quantum sets. We give a unified operator-algebraic comparison of these models by assigning to each rule its winning transformation space: the operator space of transformations accepted with certainty. We introduce R-projection-test quantum games with finite-dimensional input and output von Neumann algebras and an arbitrary, possibly infinite-dimensional, referee von Neumann algebra R. Their winning transformation spaces are precisely operator spaces with a natural bimodule structure, equivalently rectangular quantum relations. We compare this formalism with projection-lattice games, hypergraph quantum games, and the graphical rule-operator definition. Projection-lattice games capture exactly the reflexive winning bimodules. Hypergraph quantum games admit value-preserving projection-test realisations, and, after passing to perfect transformations, describe the same reflexive part as projection-lattice games. Using Daws' technique, we also translate rule operators to projections in tensor products of finite-dimensional von Neumann algebras. This identification places graphical rules in the same operator-bimodule framework and preserves both values and perfectness. Finally, we compare concurrency with the synchronicity conditions of Goldberg and of Bochniak--Kasprzak--Sołtan. The framework is illustrated by classical, rank-one, quantum XOR, colouring, and quantum graph homomorphism and isomorphism games.