  Kostka, Littlewood-Richardson, Plethysm and Kronecker coefficients are
multiplicities of irreducible representations (irreps) of the symmetric group
in restrictions and products of irreps. They play an important role in
representation theory and are notoriously hard to compute. We give quantum
algorithms that efficiently compute these coefficients whenever the ratio of
dimensions of the representations is polynomial. Using that the Kostka numbers
admit combinatorial interpretation, we show that there is an efficient
classical algorithm for polynomially-bounded Kostka numbers and conjecture
existence of a similar algorithm for the Littlewood-Richardson coefficients. We
argue why the same classical algorithm does not straightforwardly work for the
Plethysm and Kronecker coefficients, give evidence on how our quantum algorithm
may avoid some hardness obstructions in their computation, and conjecture that
the problem could lead to superpolynomial quantum speedups on some inputs. We
finally use Frobenius reciprocity to derive another quantum algorithm that
estimates these coefficients using induction and has a different cost-to-input
dependence.
