BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Quantum computing and the classical complexity of computational co
 unting - Miriam Backens\, School of Computer Science\, University of Birmi
 ngham
DTSTART:20220127T141500Z
DTEND:20220127T151500Z
UID:TALK168026@talks.cam.ac.uk
CONTACT:Damian Pitalua-Garcia
DESCRIPTION:It is folklore that the Gottesman-Knill theorem has been re-pr
 oved several times in different contexts. One of the non-quantum proofs of
  this result is the polynomial-time computability of computational countin
 g problems constrained by so-called "affine functions". Counting problems 
 are computational problems where\, rather than finding a solution satisfyi
 ng a set of constraints\, the goal is to count the\nnumber of solutions. E
 ach constraint can also be associated with weights\, in which case the goa
 l is to compute the total weight of all solutions. Examples are the proble
 m of counting the number of perfect matchings on a graph\, or computing th
 e amplitude associated with a certain output of a quantum computation.\n\n
 Indeed the Gottesman-Knill theorem is not the only connection between quan
 tum computing and computational counting problems. I will show how results
  about entanglement and universal gate sets for quantum circuits can be ap
 plied to gain insight into the classical computational complexity of count
 ing.\n\nThis is based on the papers https://doi.org/10.1145/3381425 and ht
 tps://doi.org/10.1137/20M1311557
LOCATION:MR2 Centre for Mathematical Sciences
END:VEVENT
END:VCALENDAR