Schedule and Abstracts

The slides of Matt Daws' talk can be found here. Lecture notes on quantum graphs by Mateusz Wasilewski can be found here. The slides of the other talks are linked down below.

Andrew Allen (Dalhousie University)

The quantum Ramsey number QR(2,k) is 3k−2

Let V be an operator system of n-by-n complex matrices. In 2016, Nik Weaver proved that for any positive integer k, if n is greater than or equal to 8k11, then there exists an n-by-n rank k orthogonal projection P such that dim(PVP) is 1 or k2. He presented this result as a quantum graph analogue to Ramsey's theorem, where 8k11 is an upper bound to the quantum analogue of the k-th Ramsey number R(k, k). In this talk, we will introduce the problem of calculating these quantum Ramsey numbers, and we will show that the quantum Ramsey number QR(2, k) is 3k−2 for all k greater than zero. To our knowledge, these are the first non-trivial quantum Ramsey numbers to be precisely determined. The proof combines a result of Weaver on quantum 2-cliques with a result of Li, Poon, and Sze on the rank-k numerical range of a matrix.

Slides

Arkadiusz Bochniak (Max Planck Institute of Quantum Optics)

Quantum Mycielskians

One of the famous problems in classical graph theory was the existence of triangle-free graphs with arbitrarily large chromatic number. The proposal by Mycielski provided a concrete construction of such objects by introducing a transformation that from a given graph produces the new one without changing its clique number but enlarging the chromatic number by one. We propose a generalisation of this construction into the world of quantum graphs, and study how this transformation affects their (quantum) characteristics. By analysing the concept of actions preserving partitions of unity, and introducing the notion of quantum twins, we determine the impact of quantum version of Mycielski construction on quantum symmetries of quantum graphs.

Michael Brannan (University of Waterloo)

Quantum symmetries of quantum graphs

Given a finite simple graph, it is a natural question to ask about the structure of its automorphism group.  The automorphism group of a graph is always finite, and in general not much more can be said thanks to Frucht's theorem: Any finite group can be realized as the automorphism group of a finite simple graph.  When we go quantum, things start to get much more interesting.  First, if we stick to classical graphs but consider quantum automorphisms, we can get genuine examples of (finite or infinite) compact quantum groups – even ones whose duals have property (T)!  In this talk I will discuss a few interesting examples, and explain a recently obtained quantum analogue of Frucht's theorem, which asserts that every finite quantum group arises as the quantum automorphism group of a finite simple quantum graph.  This is based on joint work with Daniel Gromada, Junichiro Matsuda, Adam Skalski, and Mateusz Wasilewski. 

Néstor Fabián Bravo Hernandez (Centro de Investigación en Matemáticas)

Higher-order regularity for quantum graphs 

We introduce some notions of higher-order regularity for quantum graphs, such as algebraic connectedness, the number of connected components, the existence of cycles, regularity, and strong regularity. Then, we present our results on the study of highly regular graphs in  and, particularly for quantum analogs of the 9-Paley graph and the pentagon. This is motivated by looking for examples of spin models for topological knot invariants. 

Alexandros Chatzinikolaou (National and Kapodistrian University of Athens)

Quantum contextuality via operator systems and C*-algebras

In this talk, we will discuss the phenomenon of contextuality and describe the hypergraph theoretic approach given by A. Acín, T. Fritz, A. Leverrier and A. B. Sainz in 2015. Following this framework we construct operator systems universal for the probabilistic models of the different types of contextuality scenarios (as described by hypergraphs) and discuss their associated C*-covers. We will consider products of contextuality scenarios and characterise the different types of probabilistic models as states on tensor products of operator systems as well as their C*-algebras. Finally we reformulate Connes embedding problem in terms of equalities between tensor product of operator systems and C*-algebras that arise from hypergraphs.

Igor Chełstowski (IM PAN and University of Warsaw)

Quantum Kneser Graphs

Kneser graphs are a family of graphs that can be seen as a fractional generalization of complete graphs. They are connected to the field of topological combinatorics and can be used to define a graph invariant known as fractional chromatic number. I present a construction of quantum graphs which boil down to classical Kneser graphs in the commutative case, and which can be therefore called quantum Kneser graphs. I also discuss their basic properties, focusing in particular on their chromatic numbers. 

Alexandru Chirvasitu (University at Buffalo)

Generic spatial rigidity for random quantum graphs

One possible random model for quantum graphs defines these as operator systems in Mn generated by d traceless self-adjoint operators sampling the Gaussian Unitary Ensemble. For reasonable choices of parameters d and n the subgroup of the unitary group U(n) leaving the resulting quantum graph (i.e. operator system) invariant turns out to be almost surely trivial or abelian. This is an analogue of the classical result that finite random graphs have trivial automorphism groups with high probability.  (Joint with M. Wasilewski)

Eric Culf (University of Waterloo)

New Approaches to Complexity via Quantum Graphs

Problems based on the structure of graphs – for example finding cliques, independent sets, or colourings – are of fundamental importance in classical complexity. Defining well-formulated decision problems for quantum graphs, the noncommutative generalisation of graphs, presents several technical challenges. In this work, we introduce and study the clique problem for quantum graphs, which utilizes the well-known connection between quantum graphs and quantum channels. We show that, by varying the collection of instances in the problem, this gives rise to complete problems for the classes NP, MA, QMA, and QMA(2). In this way, we exhibit a classical complexity problem whose natural quantisation is QMA(2), rather than QMA. This talk is based on work with Arthur Mehta.

Priyanga Ganesan (University of California San Diego)

Connectivity for quantum graphs

Quantum graphs are a non-commutative generalization of classical graphs that may be described mainly in two different ways. The first description uses the notion of operator systems or self-adjoint operator subspaces while the second description involves an abstract linear operator called quantum adjacency matrix. Several notions from classical graph theory have been successfully generalized to the setting of quantum graphs using these different descriptions of quantum graphs. However, many notions that have been studied in one model are not so well understood in the other. In particular, the notion of connectivity for quantum graphs has been introduced for matrix quantum graphs in the operator space model and algebraically characterized for regular quantum graphs using graph homomorphisms. In this talk, we will discuss a general definition of connectivity for quantum graphs using quantum adjacency matrices, which generalizes the classical notion and unifies existing notions in the literature. We will show that this new perspective simplifies and leads to quantum analogues of many classical results.

Adina Goldberg (University of Waterloo)

Quantum graph homomorphisms are perfect strategies

 When one extends the graph homomorphism game to quantum graphs, its perfect quantum-commuting strategies correspond to quantum homomorphisms between the graphs, in the sense of Musto, Reutter, and Verdon. (This is in direct analogy to the case of classical graphs.)

We sketch a proof of this result, with help from string diagrams and a new approach to synchronicity for quantum question-and-answer games.

The talk is based on material from a preprint Quantum games and synchronicity. 

Adina's webpage with slides.

Roberto Hernández Palomares (University of Waterloo)

Quantum graphs, subfactors and tensor categories

We will introduce equivariant graphs with respect to a quantum symmetry along with examples such as classical graphs, Cayley graphs of finite groupoids, and their quantum analogues. These graphs can be presented concretely by modeling a quantum vertex set by an inclusion of operator algebras and the quantum edge set by an equivariant endomorphism, idempotent with respect to convolution/Schur product. Equipped with this viewpoint and tools from subfactor theory, we will see how to obtain all these idempotents using higher relative commutants and the quantum Fourier transform. Finally, we will state a quantum version of Frucht's Theorem, showing that every quasitriangular finite quantum groupoid arises as certain automorphisms of some categorified graph.

Notes of the talk.

Andre Kornell (New Mexico State University)

On the category of quantum graphs

This talk concerns quantum graphs that are discrete but not necessarily reflexive. Thus, a quantum graph is a hereditarily atomic von Neumann algebra that is equipped with a self-adjoint quantum relation. These quantum graphs form a closed symmetric monoidal category qGph. I will describe how qGph can be constructed from the dagger compact closed category qRel of quantum sets and binary relations, and I will relate qGph to various quantum generalizations of graph coloring. This is joint work with Bert Lindenhovius.

Slides.

Junichiro Matsuda (University of Waterloo)

Quantum graphs violate the classical characterization of the existence of regular graphs

It is classically known that d-regular undirected simple graphs on n vertices exist if and only if dn is even and 0≤d≤n−1. Since Kennedy, Kroell, and I revealed that regular tracial real quantum graphs have integer degree d, we can consider if this characterization works for quantum graphs. The answer is NO in both ways: ‘if’ is violated by the non-existence of a 2-regular simple quantum graph on quantum space of size 5; ‘only if’ is violated by the existence of regular simple quantum graphs with both the degree and the size odd.

Ion Nechita (Laboratoire de Physique Théorique Toulouse)

Magic squares, quantum permutation matrices and related objects

I will discuss several classes of positive operator-valued matrices that satisfy different normalization and eigenvalue conditions. The focus will be on the different applications in quantum information theory of such objects and some new results on the corresponding matrix convex sets obtained jointly with Andreas Bluhm and Simon Schmidt (arXiv:2304.10920).

Ivan Todorov (University of Delaware)

Non-commutative graph parameters

I will revisit the (probably) first context for developing quantum graph theory, namely the notion of a (non-commutative) confusability graph of a quantum channel. I will discuss quantisations of some basic graph theoretic parameters and attributes, with an emphasis on the Lovasz number and the associated Grötschel–Lovász–Schrijver convex corner. I will show that the Lovász number has at least two distinct quantisations. While some of these quantisations are bounds for the zero-error capacity of the associated quantum channels, for others this is an open problem. The talk is based on a joint work with Gareth Boreland and Andreas Winter. 

Dominic Verdon

Noncommutative relations and zero-error communication: a categorical revisitation

In this talk we will revisit the original physical/information theoretical motivation for introducing quantum graphs – namely, zero-error communication – making use of some mathematical technology developed in the last few years. We begin by considering channels (i.e. dynamical maps) and relations between Q-systems in a rigid C*-tensor category, such as the representation category of a compact (quantum) symmetry group. Using Q-system completion to generalise Stinespring’s and Choi’s theorems to this setting, we show that the passage from a channel to its underlying relation is functorial. Identifying quantum graphs with symmetric relations, we show that 1) every simple quantum graph arises as the distinguishability graph of a channel (generalising Duan’s result for plain matrix algebras) and 2) a channel is reversible if and only if its confusability graph is discrete. We hope thereby to demonstrate that the higher-categorical framework is not only general but also convenient for treating channels, relations and quantum graphs. If time permits, we will discuss ongoing work to generalise these ideas to the infinite-dimensional setting.

Slides.

Matthijs Vernooij (Delft University of Technology)

Quantum expanders from discrete quantum groups with property (T)

Families of expander graphs were first constructed by Margulis from discrete groups with property (T). Within the framework of quantum information theory, several authors have generalised the notion of an expander graph to the setting of quantum channels. In this talk I will present work together with Michael Brannan and Eric Culf, where we use discrete quantum groups with property (T) to construct quantum expanders in two ways. The first approach obtains a quantum expander family by constructing the requisite quantum channels directly from finite-dimensional irreducible unitary representations, extending earlier work of Harrow using groups. The second approach directly generalises Margulis' original construction and is based on a quantum analogue of a Schreier graph using the theory of coideals. To obtain examples of quantum expanders, we apply our machinery to discrete quantum groups with property (T) coming from compact bicrossed products.

Mateusz Wasilewski (Institute of Mathematics of the Polish Academy of Sciences)

KMS states on quantum Cuntz–Krieger algebras

Many people have studied KMS states on various classes of C*-algebras, such as graph C*-algebras, Cuntz–Krieger algebras and their various generalisations. A seminal result of Laca and Neshveyev characterises a large class of KMS states on Cuntz–Pimsner algebras, C*-algebras built out of C*-correspondences, using traces on the base C*-algebra. In some cases this abstract theorem yields an explicit classification of KMS states, provided that we have enough information about the C*-correspondence, which we do in the case of quantum edge correspondences. This allows us to treat some examples of quantum graphs and gauge actions on local quantum Cuntz–Krieger algebras. Joint work with Manish Kumar.

Peter Zeman (Technical University of Denmark)

NPA Hierarchy for Quantum Isomorphism and Homomorphism Indistinguishability

Mančinska and Roberson [FOCS'20] showed that two graphs are quantum isomorphic if and only if they are homomorphism indistinguishable over the class of planar graphs. Atserias et al. [JCTB'19] proved that quantum isomorphism is undecidable in general. The NPA hierarchy gives a sequence of semidefinite programming relaxations of quantum isomorphism. Recently, Roberson and Seppelt [ICALP'23] obtained a homomorphism indistinguishability characterization of the feasibility of each level of the Lasserre hierarchy of semidefinite programming relaxations of graph isomorphism. We prove a quantum analogue of this result by showing 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. By combining the convergence of the NPA hierarchy with the fact that the union of these graph classes is the set of all planar graphs, we are able to give a new proof of the result of Mančinska and Roberson [FOCS'20] that avoids the use of the theory of quantum groups. This homomorphism indistinguishability characterization also allows us to give a randomized polynomial-time algorithm deciding exact feasibility of each fixed level of the NPA hierarchy of SDP relaxations for quantum isomorphism.