Holant problems and quantum information theory

Holant problems are a family of counting problems on graphs, parameterised by sets of complex-valued functions of Boolean inputs. While the Holant framework was originally inspired by ideas from quantum computation, this connection has not been exploited before to analyse their complexity.

I will introduce some basic quantum information theory and show how to apply ideas from this area to the analysis of Holant problems. This is made possible by a bijection between n-ary complex-valued functions of Boolean inputs on the one hand and states of n qubits (i.e. quantum bits), which are described by complex vectors of length 2^n, on the other hand. Under this bijection, many interesting families of functions in the Holant framework correspond to families of quantum states that are of independent interest in quantum information theory. I will explain how these ideas lead to two new Holant dichotomies, whose proofs make use of methods and knowledge from the theory of quantum entanglement. One of the new results, the full dichotomy for Holant^c, solves a long-standing open problem.

This talk is based on arXiv:1702.00767 and arXiv:1704.05798.