The Holant problem and classical simulation of quantum computations

The Holant problem is a classical counting complexity problem defined on graphs. This problem is of interest in classical computer science because it is simultaneously general enough to encompass many widely-studied counting problems on graphs -- like counting matchings or counting vertex covers -- and specific enough to allow the derivation of dichotomy theorems.

                

I will show how, from a quantum perspective, the Holant framework can be understood as a generalisation of quantum circuits, and how many of the existing results are closely related to well-known quantum concepts. I will also present some work in progress on using knowledge from quantum theory to derive new results about the Holant problem.