Abstract
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 verifier, where is the quantum analogue of . This implies that approximating the Kronecker coefficients to within a given relative error is not harder than a certain natural class of quantum approximate counting 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 , complementing a recent -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.
- Received 28 April 2023
- Accepted 17 January 2024
DOI:https://doi.org/10.1103/PRXQuantum.5.010329
Published by the American Physical Society under the terms of the Creative Commons Attribution 4.0 International license. Further distribution of this work must maintain attribution to the author(s) and the published article's title, journal citation, and DOI.
Published by the American Physical Society
Physics Subject Headings (PhySH)
Popular Summary
How hard is it to approximately compute properties of quantum many-body systems in thermal equilibrium? Surprisingly, little is known about this question even though many physicists put a lot of time and effort into computing such things every day. A previous work showed that computing the partition function of quantum many-body Hamiltonians is polynomial-time equivalent (computer science’s technical definition for being of equivalent hardness) to a class of quantum approximate counting problems defined via quantum many-body physics and quantum circuits. In this work, we show that two problems seemingly unrelated to quantum computation are in fact polynomial-time reducible to quantum approximate counting.
Both of these problems involve approximating multiplicities of irreducible representations of the symmetric group. Specifically, these multiplicities include the Kronecker coefficients and the row sums of the symmetric group. The computational complexity of these quantities relates to long-standing open questions in algebraic combinatorics and is not well understood. Our result implies that approximating the Kronecker coefficients and the row sums is no harder than computing the partition function of a quantum many-body Hamiltonian. As a corollary, we also obtain the best-known upper bound on the complexity of deciding positivity of the Kronecker coefficients and row sums. In addition, we describe a polynomial-time quantum algorithm that computes Kronecker coefficients exactly under some restrictions on the problem instance. It computes the coefficients on inputs that, to our best knowledge, currently require classical algorithms with a super polynomial run-time.
