Friday, September 14, 2007
3:30 pm, MC 5158

Maarten can den Nest
Institute for Quantum Optics and Quantum Information

Width Parameters of Graphs and Codes, and Tree Tensor Networks

In this talk we will consider recent results, where we find that certain problems in graph theory can be linked to problems in quantum information theory (QIT), and that mathematical techniques recently developed in QIT can subsequently be used to investigate the initial graph problems. We will focus on polynomials associated with graphs and codes, such as the Tutte polynomial and weight enumerators. We show that these polynomials can be reformulated in terms of inner products between large tensors, and that this reformulation allows one to use the mathematical machinery of QIT in order to study the properties of these polynomials. The techniques involve multilinear algebra, stabilizer groups and tree tensor networks in particular. We show that this approach leads to an efficient algorithm to evaluate weight enumerators and the Tutte polynomial for all graphs and codes of bounded branch-width (thereby re-deriving known results).

The talk is intended for an audience of non-physicists. The aim of the presentation is to explain the mathematics behind the approach, without going into the physics. The emphasis is fully on the graph theory and the mathematical concepts.

Joint work with W. Duer and H. Briegel.