Kostka, Littlewood-Richardson, Plethysm, and Kronecker coefficients are the multiplicities of irreducible representations in the decomposition of representations of the symmetric group that play an important role in representation theory, geometric complexity, and algebraic combinatorics. We study the complexity of computing these multiplicity coefficients through the lens of quantum algorithm theory and give quantum algorithms for their computation that are efficient whenever the ratio of dimensions of the input representations is polynomial. We show that there is an efficient classical algorithm for computing the Kostka numbers under this restriction and conjecture the existence of an analogous algorithm for the Littlewood-Richardson coefficients. We argue why a similar classical algorithm does not straightforwardly work for the Plethysm and Kronecker coefficients which lead us to conjecture that our quantum algorithms lead to superpolynomial speedups. While the conjecture about Kronecker coefficients was subsequently disproved by Panova, a peculiar polynomial gap in quantum vs classical computational complexity remains for an integer parameter k.