Counting complexity and quantum information theory

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

• Miriam Backens (Birmingham)
• Thursday 06 May 2021, 16:00-17:00
• https://bham-ac-uk.zoom.us/j/86238837160.

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.

This talk is included in these lists:

• https://bham-ac-uk.zoom.us/j/86238837160
• Combinatorics and Probability seminar
• School of Mathematics events

Note that ex-directory lists are not shown.