Quantum computing and the classical complexity of computational counting

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

• Miriam Backens, School of Computer Science, University of Birmingham
• Thursday 27 January 2022, 14:15-15:15
• MR2 Centre for Mathematical Sciences.

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.

This talk is included in these lists:

• All CMS events
• CMS Events
• CQIF Seminar
• DAMTP info aggregator
• Hanchen DaDaDash
• Interested Talks
• MR2 Centre for Mathematical Sciences
• bld31

Note that ex-directory lists are not shown.