University of Birmingham > Talks@bham > Combinatorics and Probability seminar > Counting complexity and quantum information theory

Counting complexity and quantum information theory

Add to your list(s) Download to your calendar using vCal

If you have a question about this talk, please contact M.Jenssen.

In computational counting problems, the goal of a computation is to determine the number of solutions to some problem specified by a number of constraint functions. More generally, each constraint function may be weighted, and the goal is to determine the total weight of all solutions. The holant framework formalises a broad family of such counting problems in order to analyse their computational complexity. In this talk, I show how some of the mathematical properties of constraint functions that determine the complexity of a holant problem are equivalent to properties of quantum states that are of independent interest in quantum information theory. I then use results from quantum theory to classify the (classical, i.e. non-quantum) complexity of several families of holant problems.

This talk is part of the Combinatorics and Probability seminar series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.


Talks@bham, University of Birmingham. Contact Us | Help and Documentation | Privacy and Publicity.
talks@bham is based on from the University of Cambridge.