We prove that the computation of the Kronecker coefficients of the symmetric group is contained in the complexity class #BQP. This improves a recent result of Bravyi, Chowdhury, Gosset, Havlicek, and Zhu. We use the same quantum algorithmic tools that are used in their paper, combined with additional classical representation theoretic insights. We also prove the analogous result for the plethysm coefficients and the row sums of the symmetric group character table.
We prove that the computation of the Kronecker coefficients of the symmetric group is contained in the complexity class #BQP. This improves a recent result of Bravyi, Chowdhury, Gosset, Havlicek, and Zhu. We use the same quantum algorithmic tools that are used in their paper, combined with additional classical representation theoretic insights. We also prove the analogous result for the plethysm coefficients and the row sums of the symmetric group character table.
Some representation-theoretic multiplicities, such as the Kostka and the Littlewood-Richardson coefficients, admit a combinatorial interpretation that places their computation in the complexity class #P. Whether this holds more generally is considered an important open problem in mathematics and computer science, with relevance for geometric complexity theory and quantum information. Recent work has investigated the quantum complexity of particular multiplicities, such as the Kronecker coefficients and certain special cases of the plethysm coefficients.
Here, we show that a broad class of representation-theoretic multiplicities is in #BQP. In particular, our result implies that the plethysm coefficients are in #BQP, which was only known in special cases. It also implies all known results on the quantum complexity of previously studied coefficients as special cases, unifying, simplifying, and extending prior work. We obtain our result by multiple applications of the Schur transform. Recent work has improved its dependence on the local dimension, which is crucial for our work. We further describe a general approach for showing that representation-theoretic multiplicities are in #BQP that captures our approach as well as the approaches of prior work. We complement the above by showing that the same multiplicities are also naturally in GapP and obtain polynomial-time classical algorithms when certain parameters are fixed.
Abstract Littlewood-Richardson, Kronecker and plethysm coefficients are fundamental multiplicities of interest in Representation Theory and Algebraic Combinatorics. Determining a combinatorial interpretation for the Kronecker and plethysm coefficients is a major open problem and prompts the consideration of their computational complexity. Recently, it was shown that they behave relatively well with respect to quantum computation, and for some large families there are polynomial-time quantum algorithms (Larocca and Havlicek in Quantum algorithms for representation-theoretic multiplicities, 2024. arXiv:2407.17649 ) (also Bravyi et al. in PRX Quantum 5(1):010329, 2024). In this paper, we show that for many of those cases the Kronecker and plethysm coefficients can also be computed in polynomial time via classical algorithms, thereby refuting some of the conjectures in Larocca and Havlicek (2024). This vastly limits the cases in which the desired superpolynomial quantum speedup could be achieved.
Consider a quantum state vector proportional to any given column of the character table of the symmetric group (Sn), corresponding to a superposition over the irreps weighted by the character values. It was recently argued that sampling from this state is classically hard under reasonable complexity-theoretic assumptions, while there exists an efficient quantum algorithm for preparing this character state using the quantum Fourier transform (QFT) over Sn [arXiv:2501.12579]. We give an alternative, simpler algorithm to prepare this character state with a sequence of Hamiltonian evolutions, as well as an efficient implementation with reconfigurable qubits that uses only nearest-neighbor gates in 1D. The gate complexity, accounting for Hamiltonian simulation errors, depends on the choice of the column: For fixed target state error, the estimated sufficient total gate count ranges from as few as O(n) gates for the n-cycle column, to O(n1.75) gates near the conjecturally classically hard parameter regime, to provably O(n2.5) gates in the worst case. In contrast, the QFT subroutine in the prior approach uses O(n3) gates. Our gate count estimates come from leading-order state-dependent Trotter error analysis, and the proven worst-case bound relies on a QSVT-based Hamiltonian simulation method; numerical benchmarks of the Trotter-based protocol suggest that the estimates are conservative. Furthermore, we generalize our protocol to give an explicit algorithm for the quantum character transform (QCT) over Sn using O(n2.5) gates and O(n) qubits. An application to entanglement entropy of symmetric orbifold conformal field theories is also discussed.
Whether or not the Kronecker coefficients of the symmetric group count some set of combinatorial objects is a longstanding open question. In this work we show that a given Kronecker coefficient is proportional to the rank of a projector that can be measured efficiently using a quantum computer. In other words a Kronecker coefficient counts the dimension of the vector space spanned by the accepting witnesses of a QMA verifier, where QMA is the quantum analogue of NP . This implies that approximating the Kronecker coefficients to within a given relative error is not harder than a certain natural class of problems that captures the complexity of estimating thermal properties of quantum many-body systems. A second consequence is that deciding positivity of Kronecker coefficients is contained in QMA , complementing a recent NP -hardness result of Ikenmeyer, Mulmuley, and Walter. We obtain similar results for the related problem of approximating row sums of the character table of the symmetric group. Finally, we discuss an efficient quantum algorithm that approximates normalized Kronecker coefficients to inverse-polynomial additive error. Published by the American Physical Society 2024
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 give quantum algorithms for computing these coefficients whenever the ratio of dimensions of the 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 such classical algorithm does not straightforwardly work for the Plethysm and Kronecker coefficients and conjecture that our quantum algorithms lead to superpolynomial speedups. The conjecture about Kronecker coefficients was disproved by Panova [Polynomial time classical versus quantum algorithms for representation theoretic multiplicities, arXiv:2502.20253] with a classical algorithm which, if optimal, points to a O(n^{4+2k}) vs Ω[over ˜](n^{4k^{2}+1}) polynomial gap in quantum vs classical computational complexity for an integer parameter k.