Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2407.17649 · Physical Review Letters

Quantum Algorithms for Representation-Theoretic Multiplicities

Martín Larocca, Vojtěch Havlíček

Published May 12, 2025• 15 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1103/k5tx-xtr3

Related papers

Plethysm is in #BQP

Matthias Christandl, Aram W. Harrow, Greta Panova +2 more

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.

quant-pharXiv:2602.08441•Leibniz international proceedings in informatics•Feb 10, 2026•5 citations

Polynomial time classical versus quantum algorithms for representation theoretic multiplicities

Greta Panova

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.

arXiv:2502.20253•Computational Complexity•Dec 18, 2025•7 citations

Kronecker Coefficients in #BQP

Christian Ikenmeyer, Sathyawageeswar Subramanian

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.

arXiv:2307.02389•ACM Transactions on Quantum Computing•Aug 22, 2025•11 citations

Fast quantum algorithms for approximating some irreducible representations of groups

Stephen P. Jordan

We consider the quantum complexity of estimating matrix elements of unitary irreducible representations of groups. For several finite groups including the symmetric group, quantum Fourier transforms yield efficient solutions to this problem. Furthermore, quantum Schur transforms yield efficient solutions for certain irreducible representations of the unitary group. Beyond this, we obtain poly(n)-time quantum algorithms for approximating matrix elements from all the irreducible representations of the alternating group A_n, and all the irreducible representations of polynomial highest weight of U(n), SU(n), and SO(n). These quantum algorithms offer exponential speedup in worst case complexity over the fastest known classical algorithms. On the other hand, we show that average case instances are classically easy, and that the techniques analyzed here do not offer a speedup over classical computation for the estimation of group characters.

arXiv:0811.0562•Nov 4, 2008•16 citations

Quantum Complexity of the Kronecker Coefficients

Sergey B. Bravyi, Anirban Ch Narayan Chowdhury, David Gosset +2 more

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

arXiv:2302.11454•PRX Quantum•Feb 21, 2024•30 citations

Quantum speed-ups for solving semidefinite relaxations of polynomial optimization

Daniel Stilck França, Ngoc Hoang Anh Mai

We study quantum algorithms for approximating Lasserre's hierarchy values for polynomial optimization. Let $f,g_1,\ldots,g_m$ be real polynomials in $n$ variables and $f^\star$ the infimum of $f$ over the semialgebraic set $S(g)=\{x: g_i(x)\ge 0\}$. Let $λ_k$ be the value of the order-$k$ Lasserre relaxation. Assume either (i) $f^\star=λ_k$ and the optimum is attained in the $\ell_1$-ball of radius $1/2$, or (ii) $S(g)$ lies in the simplex $\{x\ge 0: \sum_j x_j\le 1/2\}$, and the constraints define this simplex. After an appropriate coefficient rescaling, we give a quantum algorithm based on matrix multiplicative weights that approximates $λ_k$ to accuracy $\varepsilon>0$ with runtime, for fixed $k$, \[ O(n^k\varepsilon^{-4}+n^{k/2}\varepsilon^{-5}),\qquad O\!\left(s_g\!\left[n^k\varepsilon^{-4}+\!\left(n^{k}+\!\sum_{i=1}^m n^{k-d_i}\right)^{1/2}\!\varepsilon^{-5}\right]\right), \] where $s_g$ bounds the sparsity of the coefficient-matching matrices associated with the constraints. Classical matrix multiplicative-weights methods scale as $O(n^{3k}\mathrm{poly}(1/\varepsilon))$ even in the unconstrained case. As an example, we obtain an $O(n\varepsilon^{-4}+\sqrt{n}\varepsilon^{-5})$ quantum algorithm for portfolio optimization, improving over the classical $O(n^{ω+1}\log(1/\varepsilon))$ bound with $ω\approx2.373$. Our approach builds on and sharpens the analysis of Apeldoorn and Gilyén for the SDPs arising in polynomial optimization. We also show how to implement the required block encodings without QRAM. Under the stated assumptions, our method achieves a super-quadratic speedup in the problem dimension for computing Lasserre relaxations.

quant-pharXiv:2511.14389•Nov 19, 2025•0 citations
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 ˜ polynomial gap in quantum vs classical computational complexity for an integer parameter k.
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.
We consider the quantum complexity of estimating matrix elements of unitary irreducible representations of groups. For several finite groups including the symmetric group, quantum Fourier transforms yield efficient solutions to this problem. Furthermore, quantum Schur transforms yield efficient solutions for certain irreducible representations of the unitary group. Beyond this, we obtain poly(n)-time quantum algorithms for approximating matrix elements from all the irreducible representations of the alternating group A_n, and all the irreducible representations of polynomial highest weight of U(n), SU(n), and SO(n). These quantum algorithms offer exponential speedup in worst case complexity over the fastest known classical algorithms. On the other hand, we show that average case instances are classically easy, and that the techniques analyzed here do not offer a speedup over classical computation for the estimation of group characters.
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
We study quantum algorithms for approximating Lasserre's hierarchy values for polynomial optimization. Let f,g1,…,gmf,g_1,\ldots,g_mf,g1​,…,gm​ be real polynomials in nnn variables and f⋆f^\starf⋆ the infimum of fff over the semialgebraic set S(g)={x:gi(x)≥0}S(g)=\{x: g_i(x)\ge 0\}S(g)={x:gi​(x)≥0}. Let λkλ_kλk​ be the value of the order-kkk Lasserre relaxation. Assume either (i) f⋆=λkf^\star=λ_kf⋆=λk​ and the optimum is attained in the ℓ1\ell_1ℓ1​-ball of radius 1/21/21/2, or (ii) S(g)S(g)S(g) lies in the simplex {x≥0:∑jxj≤1/2}\{x\ge 0: \sum_j x_j\le 1/2\}{x≥0:∑j​xj​≤1/2}, and the constraints define this simplex. After an appropriate coefficient rescaling, we give a quantum algorithm based on matrix multiplicative weights that approximates λkλ_kλk​ to accuracy ε>0\varepsilon>0ε>0 with runtime, for fixed kkk, O(nkε−4+nk/2ε−5),O ⁣(sg ⁣[nkε−4+ ⁣(nk+ ⁣∑i=1mnk−di)1/2 ⁣ε−5]), O(n^k\varepsilon^{-4}+n^{k/2}\varepsilon^{-5}),\qquad O\!\left(s_g\!\left[n^k\varepsilon^{-4}+\!\left(n^{k}+\!\sum_{i=1}^m n^{k-d_i}\right)^{1/2}\!\varepsilon^{-5}\right]\right), O(nkε−4+nk/2ε−5),O(sg​[nkε−4+(nk+∑i=1m​nk−di​)1/2ε−5]), where sgs_gsg​ bounds the sparsity of the coefficient-matching matrices associated with the constraints. Classical matrix multiplicative-weights methods scale as O(n3kpoly(1/ε))O(n^{3k}\mathrm{poly}(1/\varepsilon))O(n3kpoly(1/ε)) even in the unconstrained case. As an example, we obtain an O(nε−4+nε−5)O(n\varepsilon^{-4}+\sqrt{n}\varepsilon^{-5})O(nε−4+n​ε−5) quantum algorithm for portfolio optimization, improving over the classical O(nω+1log⁡(1/ε))O(n^{ω+1}\log(1/\varepsilon))O(nω+1log(1/ε)) bound with ω≈2.373ω\approx2.373ω≈2.373. Our approach builds on and sharpens the analysis of Apeldoorn and Gilyén for the SDPs arising in polynomial optimization. We also show how to implement the required block encodings without QRAM. Under the stated assumptions, our method achieves a super-quadratic speedup in the problem dimension for computing Lasserre relaxations.