Quantum counting and the symmetric group

Anirban Chowdhury
University of Waterloo

I will talk about connections between the representation theory of the symmetric group and counting problems inspired by quantum computation and many-body physics. The main result that I will present concerns the Kronecker coefficients, which are the analogs of the Clebsch-Gordon coefficients for the symmetric group. It is an open question whether computing the Kronecker coefficients reduces to a classical counting problem, i.e., whether the Kroneckers can be expressed as the number of solutions to NP-complete problems. I will show that approximating the Kronecker coefficients to within a multiplicative error reduces to approximate versions of quantum counting problems. This is interesting also because the quantum counting problems are questions about the eigenvalues of operators, such as Hamiltonians, POVM elements, or density operators. And spectral properties, specifically of density operators, are closely related to the representation theory of the symmetric group. In this talk I will explain our result and also discuss some of these connections.


Back to Mathematical and Computational Challenges in Quantum Computing