Workshop: Quantum Generalizations of Graph Theory

The aim of this focused workshop is to bring together some of the experts that work on quantum generalizations of graph theory. Such generalizations naturally arise in quantum information and communication scenarios, and provide a novel perspective on graph theoretical quantities. This novel viewpoint already led to the discovery of various non-commutative generalization of standard graph theoretical notions, such as the adjacency matrix, graph isomorphism or the Lovász theta number. While there has been significant progress in the understanding of these notions, there are still numerous open questions and further directions to explore. In order to find the right perspective and the appropriate language for the problems it is essential to combine insights from both discrete mathematics and quantum information.
The goal of the workshop is to bring together experts from both quantum information and discrete mathematics in order to discuss the state of the art, to share ideas and to identify and tackle relevant questions.

The workshop will feature an open problem sessions and several thematic discussions around selected topics on top of regular talks. In order to keep the discussions informal and focused we aim at bringing together about a dozen participants.

Organizer: András Gilyén (Rényi Institute)

Invited Speakers:

• Martino Lupini (Victoria University of Wellington, New Zealand)
• David Earl Roberson, (Technical University of Denmark)
• Dan Stahlke
• Ivan Todrov (University of Delaware)
• Márió Szegedy (Rutgers University)
• Péter Vrana (Budapest University of Technology and Economics)

Participants:

• Miklós Abért (Rényi Institute)
• Péter Frenkel (Eötvös University, Budapest)
• Katalin Friedl (Budapest University of Technology and Economics)
• Mahya Ghandehari (University of Delaware)
• András Gilyén (Rényi Institute)
• László Lovász (Rényi Institute)
• Milán Mosonyi (Budapest University of Technology and Economics)
• Balázs Szegedy (Rényi Institute)
• Tamás Tasnádi (Budapest University of Technology and Economics)
• Mihály Weiner (Budapest University of Technology and Economics)
• Zoltán Zimborás (Wigner Research Center for Physics)

Schedule

Abstracts

Martino Lupini - Quantum automorphism groups of finite graphs

abstract:
The notion of quantum group has been introduced and studied using methods from operator algebras as the natural analogue of a classical group in quantum physics and noncommutative mathematics. In this context, Banica has developed the theory of quantum automorphism groups of finite graphs. From a different perspective, quantum isomorphisms between finite graphs have been studied in quantum information theory.
In this talk I will present a joint work with Mancinska and Roberson that created a bridge between these two approaches by showing that the notions of quantum isomorphism between graphs from the information theory and quantum group literature coincide. I will explain how this insight allowed us to introduced new tools in the study of quantum automorphism groups of graphs, including the notions of quantum orbits and orbitals and the quantum orbital algebra, and to answer several questions from
the quantum group literature.


David Earl Roberson - A quantum analog of a theorem of Lovász

abstract:
In the  \(G,H\)-isomorphism game, two cooperating players (Alice and Bob) attempt to convince a referee that the graphs \(G\) and \(H\) are isomorphic. This game can be won with probability one if and only if the graphs \(G\) and \(H\) are indeed isomorphic. This motivates the definition of quantum isomorphic graphs: those for which it is possible to win the isomorphism game with probability one using “quantum strategies”, i.e., strategies in which Alice and Bob are allowed to share a quantum state and perform local quantum measurements on this state. Surprisingly, it can be shown that two graphs are quantum isomorphic if and only if they admit the same number of homomorphisms from any planar graph. This is an analog of a result of Lovász from 1967 which states that two graphs are isomorphic if and only if they admit the same number of homomorphisms from any graph. We will discuss this unexpected result and its proof which uses the theory of quantum groups.


Ivan Todrov - Non-commutative graph theoretic parameters

abstract:
Following Duan-Severini-Winter, I will view operator systems in matrix algebras as non-commutative counterparts of graphs. I will present quantisations of several graph-theoretic parameters associated with such operator systems, including Lovász theta number, chromatic and fractional chromatic numbers. I will discuss non-commutative convex corners and, using a quantum version of the second anti-blocker theorem, I will show that the fractional chromatic and the fractional clique number of a non-commutative graph coincide. I will discuss applications of the discussed parameters to bounding the zero-error capacity of quantum channels. The talk will be based on joint work with Gareth Boreland and Andreas Winter.

Dan Stahlke - Weighted theta functions for non-commutative graphs

abstract:
I will define and explore a weighted version of the Duan-Severini-Winter theta on non-commutative graphs, generalizing to non-commutative graphs most of the properties of the classical weighted theta from Grötschel-Lovász-Schrijver, and leading to a discussion of perfect graphs.  The geometry of quantum convex corners, specifically their vertices and facets, will be investigated.


Péter Vrana - Non-commutative generalizations of graph parameters

abstract:
Upper bounds on the independence number play an important role in the study of the Shannon capacity of graphs and various quantum versions of the zero-error capacity. Many of these capacities admit dual characterizations in terms of additive, multiplicative and monotone graph parameters, which have been proved based on the theory of asymptotic spectra. Moreover, the theory implies relations between the respective sets of parameters, including an extension property asserting that any bound of this type on the entanglement-assisted capacity of graphs has at least one extension to noncommutative graphs, with similar properties. However, no similar results are known about the unassisted capacity of noncommutative graphs. The aim of this talk is to explain some difficulties and partial results around this problem.


Márió Szegedy - Quantum random circuits and the averaging process

abstract:
Google supremacy experiments have raised new statistical questions about random quantum circuits. After presenting some of these, we delve into questions related to a particular random process, the so-called averaging process, which is studied at least from the 80s. Recently Sourav Chatterjee, Persi Diaconis, Allan Sly and Lingfu Zhang have established a sharp convergence cutoff of 1/(2∗log2)∗n∗logn+O(n∗ sqrt(logn)), when we run the process on the complete graph. We prove that the complete graph is an extreme case: we cannot get a quicker convergence on any other graph. We also resolve a conjecture of Sam Spiro: the convergence in the case of the the cycle graph occurs in time Θ(n^3). We also make several other observations about the process. Joint with Ramis Movassagh and Guanyang Wang.