Graphs are among the simplest mathematical objects - by definition, a graph is a set of points called vertices, and a set of edges, each edge connecting a pair of given vertices. If the vertices are labelled by the numbers 1,2,...,n, then each edge is a pair (i,j), where i and j are between 1 and n. Graphs have a large number of applications in computer science, engineering and mathematics itself. It was Shannon in the 1950's who realised that they can be used successfully in the theory of information. If a symbol, say i, is sent through a communication channel, then due to an error that may occur during this transfer, it may be confused by the receiver with another symbol, say j. The pairs (i,j) of symbols that can be confused in such way form the set of edges of a graph, called the confusability graph of the channel. Shannon defined an asymptotic parameter, called the zero-error capacity of the channel (or, equivalently, of the corresponding confusability graph), which measures the extent to which information can be sent through the channel with zero error.
Given a graph G on n vertices, in the 1980's, Pauslen, Power and Smith studied the linear subspace S(G) of the space M_n of all n by n matrices consisting of those elements that have zero i,j-entry when (i,j) is not an edge of G. The space S(G) is an operator system - that is, it is closed under the operation of conjugate transpose and contains the identity matrix - which fully identifies the underlying graph G. Operator systems have an illustrious history and a large number of applications within Analysis, and the aforementioned paper thus opened up an analytical avenue for Graph Theory. We note that not all operator systems in M_n can be obtained from graphs in the described way, and this is a crucial point for the approach used in our proposal.
At present, there are ongoing efforts for the construction of quantum computers. The theoretical science that lies behind these efforts is Quantum Information Theory, a part of the general field of quantum physics. The main feature of quantum, as opposed to classical, physics, is non-commutativity: the mathematical tools behind it use the space M_n and its infinite dimensional generalisations where the commutation rule ab = ba does not hold in general. Non-commutativity features prominently in the study of quantum channels, that is, channels used to transfer quantum information. Recently, Duan, Severini and Winter defined the confusability graph of a quantum channel as a certain operator system in M_n, and showed that every operator system in M_n arises in this way. It is thus natural to call operator systems in M_n non-commutative graphs. The class of operator systems S(G) can be identified in an easy and elegant way as a natural subclass of the class of all non-commutative graphs. Quantum zero-error capacities were introduced, but a number of important questions were left open.
The aim of the present research project is to study of quantum zero-error capacities using methods from Operator Theory - the general branch where the study of operator systems belongs. We plan to obtain new estimates on the quantum version of a parameter known as Lovasz number of a graph (a quantity that provides an easier computable bound for the zero-error capacity), study other parameters such as non-commutative chromatic numbers, and lay the foundations of a "non-commutative graph theory", where basic operations with classical graphs such as passing to a complement, a subgraph and a homomorphic image can be carried out successfully in the context of operator systems. We plan to address a number of questions regarding asymptotic versions of the introduced parameters that are expected to shed light on open problems and conjectures in Graph Theory and Quantum Information.
|