Abstracts & Slides

Wednesday 25
  • Janos Körner: Capacities à la Shannon of graphs and other combinatorial structures.

    Combinatorics is a colourful anthology of simple problems with ingenious solu
    tions. Information theory is a compact theory. The most powerful construction tool in information theory is random choice. Wherever it fails to work, problems remain unsolved. We believe that a happy marriage of these two fields could break this spell. As a first step, we study zero–error problems in information theory. Clearly, this is just combinatorics. The starting point is Shannon’s zero–error capacity of discrete memoryless channels, a famously unsolved question. This can be formulated as a purely graph–theoretic problem, and amounts to the study of the limiting behaviour of basic parameters of simple graphs. Passing from simple graphs to directed graphs (Sperner capacity), hypergraphs and extending the concept to the capacity of finite families of such structures we manage to encompass and in some cases solve classical problems in combinatorics. These new concepts still correspond to the capacity of channels in multi–user information theory. 
    In order to arrive at an information–theoretic framework for the whole of extremal combinatorics, we have begun to study capacity–like concepts without any reference to communication. While in the previous problems one was looking for the largest families of strings from a finite alphabet any pair (or, in more generality, k–tuple for some finite k) of which satisfies a given dissimilarity relation, recently we have begun to study similar problems involving permutations (strings from an infinite alphabet) or even graphs. 

  • Debbie Leung: Entanglement can increase asymptotic rates of zero-error classical communication over classical channels.

    It is known that the number of different classical messages which can be communicated with a single use of a classical channel with zero probability of decoding error can sometimes be increased by using entanglement shared between sender and receiver. It has been an open question to determine whether entanglement can ever increase the zero-error communication rates achievable in the limit of many channel uses. In this paper we show, by explicit examples, that entanglement can indeed increase asymptotic zero-error capacity, even to the extent that it is equal to the normal capacity of the channel. Interestingly, our examples are based on the exceptional simple root systems E7 and E8.
    (Based on arXiv:1009.1195.)

  • Laura Mančinska: Quantum Graph Homomorphisms

    A homomorphism from a graph X to a graph Y is an adjacency preserving mapping f:V(X)->V(Y). We consider a nonlocal game in which Alice and Bob are trying to convince a verifier with certainty that a graph X admits a homomorphism to Y. This generalizes the well-studied graph coloring game. In addition, this framework allows us to introduce and study quantum analogues of various graph parameters such as independence number and odd girth. We will discuss several results on quantum graph parameters such as their computational complexity, separations from classical analogues, and relation to general nonlocal games and zero-error communication.
    (Based on arXiv:1212.1724.)

  • Aida Abiad: Godsil-McKay switching in regular graphs

    It is well known that if a graph G has the same spectrum (eigenvalues) as a strongly regular graph 
    G', then G' is also strongly regular with the same parameters as G. In this talk, we introduce a spectral tool called Godsil-McKay switching, and we show that it can be used to construct new strongly regular graphs from known ones. In particular, we apply Godsil-McKay switching to an important family of strongly regular graphs: the symplectic graphs over the binary field. 
    Similarly, we also apply Godsil-McKay switching to another important family of regular graphs: the orthogonality graphs. In arXiv:1207.1779 it is shown that, under certain constraints, orthogonality graphs exhibit separation between the Shannon and entangled capacities. An interesting problem would be to study whether the switched orthogonality graphs are examples of graphs whose entangled capacity exceeds the Shannon capacity.
    (The first part is joint work with Willem Haemers.)

  • Sabine Burgdorf: A conic approach to quantum graph parameters

    The completely positive semidefinite cone CS+ consists of all the symmetric matrices that admit a Gram representation by positive semidefinite matrices of any size. This cone can be used, e.g., to model quantum graph parameters or, more generally, to characterize the set of bipartite quantum correlations as projection of an affine section of it. 
    We will give an overview of the known structure of the completely positive semidefinite cone. In particular, we will discuss a description of its closure in terms of tracial ultraproducts and a hierarchy of polyhedral cones that form inner approximations covering the interior of the CS+ cone. These polyhedral cones can be used for computing some quantum graph parameters by way of linear programs. 
    (Based on joint work with Monique Laurent and Teresa Piovesan: arXiv:1312.6643.)

  • Carlos Ortiz: Quantum Graph Homorphisms: An Operator Algebraic Approach

    In this talk we will explore quantum graph homomorphisms through the lens of C*-algebras and operator systems. We will start by presenting a way to study these homomorphisms using completely positive maps. We will then utilize these maps to define a possible "quantum core" of a graph.  Next, we will look at a C*-algebra that encodes all the information about these homomorphisms and establish some connections between computational complexity and the representation of these algebras. Finally, we use this C*-algebra to define a new quantum chromatic number.
    (Based on arXiv:1505.00483.)


Thursday 26
  • Nik Weaver: Quantum graphs as quantum relations

    The "noncommutative graphs" which arise in quantum error correction are a special case of a more general notion of "quantum relations". These objects enjoy an abstract characterization which makes various constructions in the theory of quantum error correction conceptually transparent.
    (Based on arXiv:1506.03892.)

  • Dave Roberson: Relaxations of Graph Isomorphism

    We introduce a two player non-local game based on graph isomorphisms. In the (X,Y)-isomorphism game the players aim to convince a referee that there exists an isomorphism between graphs X and Y. Classically, players can win this game with probability one if and only if the graphs are isomorphic. This allows us to define a quantum analog of isomorphism in the same manner as quantum coloring/homomorphism was defined. This notion of "quantum isomorphism" can be expressed in terms of a feasibility program over the recently introduced completely positive semidefinite cone. We can thus give relaxations of quantum isomorphism by considering the same program, but over the positive semidefinite or doubly nonnegative cones. The doubly nonnegative relaxation turns out to be equivalent to a previously defined notion based on coherent algebras associated to graphs. Another relaxation can be obtained by considering general non-signalling strategies for the isomorphism game. Interestingly, this relaxation is equivalent to fractional graph isomorphism. This work is ongoing and the results fairly new, so there has yet to be found a separation between isomorphism and quantum isomorphism.
    (Joint work with Laura Mancinska and Antonios Varvitsiotis.)

  • Miguel Navascués: Characterizing finite-dimensional quantum behavior

    We study and extend the semidefinite programming (SDP) hierarchies introduced in [Phys. Rev. Lett. 115, 020501] for the characterization of the statistical correlations arising from finite dimensional quantum systems. First, we introduce the dimension-constrained noncommutative polynomial optimization (NPO) paradigm, where a number of polynomial inequalities are defined and optimization is conducted over all feasible operator representations of bounded dimensionality. Important problems in device independent and semi-device independent quantum information science can be formulated (or almost formulated) in this framework. We present effective SDP hierarchies to attack the general dimension-constrained NPO problem (and related ones) and prove their asymptotic convergence. To illustrate the power of these relaxations, we use them to derive new dimension witnesses for temporal and Bell-type correlation scenarios, and also to bound the probability of success of quantum random access codes.
    (Based on arXiv:1507.07521.)

  • Ivan Todorov: Estimating quantum chromatic numbers

    We develop further the new versions of quantum chromatic numbers of graphs introduced by the first and fourth authors. We prove that the problem of computation of the commuting quantum chromatic number of a graph is solvable by an SDP and describe an hierarchy of variants of the commuting quantum chromatic number which converge to it. We introduce the tracial rank of a graph, a parameter that gives a lower bound for the commuting quantum chromatic number and parallels the projective rank, and prove that it is multiplicative. We describe the tracial rank, the projective rank and the fractional chromatic numbers in a unified manner that clarifies their connection with the commuting quantum chromatic number, the quantum chromatic number and the classical chromatic number, respectively. Finally, we present a new SDP that yields a parameter larger than the Lov\'asz number and is yet a lower bound for the tracial rank of the graph. We determine the precise value of the tracial rank of an odd cycle.
    (Based on arXiv:1407.6918.)

  • Belén Sainz: A Combinatorial Approach to Nonlocality and Contextuality

    Most work on contextuality so far has focused on specific examples and concrete proofs of the Kochen-Specker theorem, while general definitions and theorems about contextuality are sparse. For example, it is commonly believed that nonlocality is a special case of contextuality, but what exactly does this mean? In this work, that builds on the graph-theoretic approach of Cabello, Severini and Winter, we develop a hypergraph approach to study contextuality and nonlocality in a unified manner. In this talk I will further focus on the relation between some sets of probabilistic models and graph invariants, and show that the set of quantum models cannot be characterized by any such graph-theoretic quantity.
    (Based on arXiv:1212.4084.)
  • Glaucia Murta:  Characterising the Performance of XOR Games and the Shannon Capacity of Graphs

    We study the performance of XOR games, in which two players, Alice and Bob, are asked questions by a referee and they have to output one bit answer, the payoff function depends only on the XOR of their outputs. We present a set of necessary and sufficient conditions such that quantum players of a two-party XOR game cannot perform any better than classical players. With any such game, we associate a graph and examine its zero-error communication capacity. This allows us to specify a broad new class of graphs for which the Shannon capacity can be calculated. The conditions also enable the parametrisation of new families of games which have no quantum advantage.
    (Based on arXiv:1406.0995.)

Friday 27 
  • Runyao Duan: Activated zero-error classical capacity of quantum channels in the presence of quantum no-signalling correlations

    Recently the one-shot quantum no-signalling assisted zero-error classical capacity of a quantum channel has been formulated as a semidefinite programming (SDP) depending only on the Choi-Kraus operator space of the channel. In this talk we further study the activated quantum no-signalling assisted zero-error classical capacity by first allowing the assistance from some noiseless forward classical channel and later paying back the cost of the helper. We show that the one-shot activated capacity can also be formulated as a SDP and is additive under direct sum. As an immediate corollary, we find that one bit noiseless communication is able to fully activate any classical-quantum channel to achieve its asymptotic capacity. Although the one-shot activated capacity is normally strictly larger than the counterpart without activation, both capacities are identical in the asymptotic setting. This fact enables us to construct an explicit channel whose asymptotic no-signalling assisted zero-error capacity is not equal to the semidefinite fractional packing number.
    (Based on a joint work with Xin Wang (UTS): arXiv:1510.05437.) 

  • Florian Speelman: Round elimination in exact communication complexity

    We study two basic graph parameters, the chromatic number and the orthogonal rank, in the context of classical and quantum exact communication complexity. In particular, we consider two types of communication problems that we call promise equality and list problems. For both of these, it was already known that the one-round classical and one-round quantum complexities are characterized by the chromatic number and orthogonal rank of a certain graph, respectively. In a promise equality problem, Alice and Bob must decide if their inputs are equal or not. We prove that classical protocols for such problems can always be reduced to one-round protocols with no extra communication. In contrast, we give an explicit instance of a promise problem that exhibits an exponential gap between the one- and two-round exact quantum communication complexities. Whereas the chromatic number thus captures the complete complexity of promise equality problems, the hierarchy of “quantum chromatic numbers” (starting with the orthogonal rank) giving the quantum communication complexity for every fixed number of communication rounds thus turns out to enjoy a much richer structure. In a list problem, Bob gets a subset of some finite universe, Alice gets an element from Bob’s subset, and their goal is for Bob to learn which element Alice was given. The best general lower bound (due to Orlitsky) and upper bound (due to Naor, Orlitsky, and Shor) on the classical communication complexity of such problems differ only by a constant factor. We exhibit an example showing that, somewhat surprisingly, the four-round protocol used in the bound of Naor et al. can in fact be optimal. Finally, we pose a conjecture on the orthogonality rank of a certain graph whose truth would imply an intriguing impossibility of round elimination in quantum protocols for list problems, something that works trivially in the classical case.
    (Based on this TQC 2015 paper.) 

  • Debbie Leung: Maximum privacy without coherence, zero-error 

    We study the possible difference between the quantum and the private capacities of a quantum channel in the zero-error setting. For a family of channels introduced by arXiv:1312.4989, we demonstrate an extreme difference: the zero-error quantum capacity is zero, whereas the zero-error private capacity is maximum given the quantum output dimension.
    (
    Based on arXiv:1509.01300.)

  • Teresa Piovesan: Multi-party zero-error classical channel coding with entanglement

    We study the effects of entanglement on the performance of two classical zero-error communication tasks among multiple parties. Both tasks are generalizations of the two-party zero-error channel-coding problem, where a sender and a receiver want to perfectly communicate messages through a one-way classical noisy channel. Our results show both advantages and limitations of entanglement-assisted multi-party communication.
    (Based on arXiv:1403.5003.)

  • Antonios Varvitsiotis: On the minimum dimension of a Hilbert space needed to generate a quantum correlation

    Consider a two-party correlation that can be generated by performing local measurements on a bipartite quantum system. A question of fundamental importance is to understand how many resources, which we quantify by the dimension of the underlying quantum system, are needed to reproduce this correlation. In this work we
    identify an easy-to-compute lower bound on the smallest Hilbert space dimension needed to generate an arbitrary two-party quantum correlation. To derive the lower bound, we combine a new geometric characterization for the set of quantum correlations (arXiv:1506.07297) with techniques that were recently used to lower
    bound the PSD-rank of a nonnegative matrix, an important notion to mathematical optimization and quantum communication theory (arXiv:1407.4308). We show that our bound is tight on the correlations generated by optimal quantum strategies for the CHSH and the Magic Square Game and also reprove that a family of PR-boxes cannot be realized using quantum strategies.
    (Joint work with J. Sikora and Z. Wei.)

Ċ
Giannicola Scarpa,
Dec 8, 2015, 7:47 AM
Ċ
Giannicola Scarpa,
Dec 8, 2015, 7:47 AM
Ċ
Giannicola Scarpa,
Dec 8, 2015, 7:47 AM
Ċ
Giannicola Scarpa,
Dec 8, 2015, 7:48 AM
Ċ
Giannicola Scarpa,
Dec 9, 2015, 11:02 AM
Ċ
Giannicola Scarpa,
Dec 8, 2015, 7:48 AM
Ċ
Giannicola Scarpa,
Dec 8, 2015, 7:48 AM
Ċ
Giannicola Scarpa,
Dec 8, 2015, 7:48 AM
Ċ
Giannicola Scarpa,
Dec 8, 2015, 7:48 AM
Ċ
Giannicola Scarpa,
Dec 8, 2015, 7:49 AM
Comments