Machine learning on graphs induces correlations between unconnected nodes. How can non-local quantum resources enhance performance? We shall develop strategies for distributed measurement and (neural) message-passing for quantum machine learning, based on quantum random walks on graphs, where `creative' learning scenarios are developed and assessed. Shannon capacity is a graph-theoretic method to assess the ability of a channel to transmit messages. It is a celebrated problem to determine the Shannon capacity of a graph - the Shannon capacity of the simple 7-cycle remains open for 56 years now, reflecting the importance of the problem. Recent results identify that the Lovasz number, an upper bound on Shannon capacity, evaluates the quantum advantage of performing quantum measurements on a system as opposed to classical measurements and is central to the notion of quantum contextuality. Our project proposes to investigate generalisations of Shannon capacity and Lovasz - the edge of a graph usually connects mutually exclusive propositions, and we generalise so that connected propositions are exclusive to within some probability. We also associate to each edge a probabilistic message allowing us to consider generalised Shannon capacities and Lovasz numbers of graph and hypergraph-based message-passing algorithms. A further generalisation is to replace with generalised measurement strategies based on, say, tight frames or other non-orthogonal sequence sets. Moreover we shall classify graphs according to generalisations and variations of their Shannon capacity, Lovasz number, and fractional packing number. We plan to consider message-passing algorithms on non-bipartite, mixed, and dynamic graph and hypergraph scenarios, both in classical and quantum contexts. The project team comprises 2 international partners - see: http://personal.us.es/adan/home.htm and http://www.ucl.ac.uk/~ucapsse/ and 1 national expert and the project leader, and we apply for 1 postdoc and 1 PhD.
Project leader: Matthew Parker
Institution: Institutt for informatikk