Abstract

It is folklore that the Gottesman-Knill theorem has been re-proved several times in different contexts. One of the non-quantum proofs of this result is the polynomial-time computability of computational counting problems constrained by so-called “affine functions”. Counting problems are computational problems where, rather than finding a solution satisfying a set of constraints, the goal is to count the number of solutions. Each constraint can also be associated with weights, in which case the goal is to compute the total weight of all solutions. Examples are the problem of counting the number of perfect matchings on a graph, or computing the amplitude associated with a certain output of a quantum computation.

Indeed the Gottesman-Knill theorem is not the only connection between quantum computing and computational counting problems. I will show how results about entanglement and universal gate sets for quantum circuits can be applied to gain insight into the classical computational complexity of counting.

This is based on the papers https://doi.org/10.1145/3381425 and https://doi.org/10.1137/20M1311557