# The Holant problem and classical simulation of quantum computations

Miriam Backens ( University of Bristol )

- 14:00 18th November 2016 ( week 6, Michaelmas Term 2016 )Lecture Theatre B

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.