University of Cambridge > Talks.cam > CQIF Seminar > Quantum computing and the classical complexity of computational counting

Quantum computing and the classical complexity of computational counting

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

If you have a question about this talk, please contact Damian Pitalua-Garcia.

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

This talk is part of the CQIF Seminar series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.

 

© 2006-2022 Talks.cam, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity