Quantum Complexity of Kronecker Coefficients

Kronecker coefficients appear in representation of the symmetric group in the decomposition of tensor products of irreducible representations. They are notoriously difficult to compute and it is a long standing problem to find a combinatorial expression for them. 

We study the problem of computing Kronecker coefficients from quantum computational perspective. First, we show that the coefficients can be expressed as a dimension of a subspace given by intersection of two commuting, efficiently implementable projectors and relate their computation to the recently introduced quantum approximate counting class (QAPC). Using similar construction, we show that deciding positivity of Kronecker coefficients is contained in QMA. We give similar results for a related problem of approximating row sums in a character table of the symmetric group and show that its decision variant is in QMA. We then discuss two quantum algorithms - one that samples a distribution over squared characters and another one that approximates normalized Kronecker coefficients to inverse-polynomial additive error. We show that under a conjecture about average-case hardness of computing Kronecker coefficients, the resulting distribution is hard to sample from classically. 

Our work explores new structures for quantum algorithms and improved characterization of the quantum approximate counting.

Joint work with David Gossett, Sergey Bravyi, Anirban Chowdhury and Guanyu Zhu 

Zoom link:  https://pitp.zoom.us/j/95976938016?pwd=eDV3TXZReHo5UHdvZ0hIbkhXOFcxQT09