Plethysm is in # ​ 𝖡𝖰𝖯 \#\mathsf{BQP} Matthias Christandl, Aram W. Harrow, Greta Panova, Pietro M. Posta, Michael Walter Abstract 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 # ​ 𝖯 \#\mathsf{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 # ​ 𝖡𝖰𝖯 \#\mathsf{BQP} . In particular, our result implies that the plethysm coefficients are in # ​ 𝖡𝖰𝖯 \#\mathsf{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 # ​ 𝖡𝖰𝖯 \#\mathsf{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 𝖦𝖺𝗉𝖯 \mathsf{GapP} and obtain polynomial-time classical algorithms when certain parameters are fixed. 1 Introduction Computing multiplicities is a central problem in representation theory and algebraic combinatorics, and is directly relevant to quantum information theory and geometric complexity theory. In most cases, no closed-form formulas are known. A natural and fruitful question is to ask whether these multiplicities count combinatorial objects. If so, then one obtains positive combinatorial interpretation . Stanley stated the problem of finding such interpretations for important representation-theoretic multiplicities in his influential paper [ 54 ] . Specific multiplicities of interest include: the Littlewood-Richardson (LR) coefficients , discussed in 1934 [ 39 ] , giving the multiplicity of an irreducible representation of the general linear group \GL(n) in the tensor product of two others; the Kronecker coefficients of the symmetric group, defined in 1938 [ 42 ] , giving the multiplicity of an irreducible representation of the symmetric group S_{n} in the tensor product of two others; and the plethysm coefficients , first mentioned by Littlewood in 1936 [ 37 ] and defined formally in Ref. [ 38 ] , which gives the multiplicity of an irreducible \GL(n) -representation in the composition of two irreducible \GL -representations (see Section 1.3 ). By Schur-Weyl duality, the Kronecker coefficients can also be defined in terms of the general linear group, and the LR and plethysm coefficients can also be defined in terms of the symmetric group. Multiplicities arise naturally across a broad range of areas and applications in mathematics, physics, and computer science, and accordingly they have a long history of study using different methods, from representation theory and invariant theory, to geometry and algebraic combinatorics. For the plethsym coefficients in particular, initial properties were understood via geometric means, notably their stability [ 7 ] . The combinatorial investigations started with the unfulfilled hope of finding an interpretation as counting integer points in polytopes (as is known for the LR coefficients, see below), see e.g. the works of Kahle and Michalek [ 31 ] . Approaches via tableaux combinatorics were developed by many groups, see e.g. Refs. [ 22 , 21 , 43 ] . The general goal is to give an interpretation as counts of some simple-to-describe but exponentially large set. Ultimately, however, combinatorial formulas are only known in very special situations, see Refs. [ 23 , 44 , 47 ] for some of the known cases. 1.1 The complexity of computing multiplicities While the notion of “positive combinatorial interpretation” is not a priori formally defined, the modern interpretation formalizes it as “proving the computational problem is in \#\mathsf{P} , and deciding positivity is in \mathsf{NP} ”, see Refs. [ 45 , 49 ] . Indeed, the complexity class \#\mathsf{P} captures the problem of counting gadgets (witnesses) of which there might be many but which can be recognized efficiently (in polynomial time). This perspective uncovered surprising connections between mathematics and computer science and led to new insights in both fields. The LR coefficients turn out to be in \#\mathsf{P} , as they admit an interpretation as certain tableaux and integer points in polytopes, whereas their positivity is even decidable in \mathsf{P} [ 41 , 13 ] as a consequence of the Knutson-Tao proof of the saturation conjecture [ 34 ] . In contrast, the problems for Kronecker and plethysm coefficients are still wide open [ 50 ] . We know that both coefficients are \#\mathsf{P} -hard to compute and \mathsf{NP} -hard to decide positivity of, see Refs. [ 27 , 24 ] . However, it is not known whether they are in \#\mathsf{P} , that is, whether they admit a positive combinatorial interpretation, or whether their positivity is in \mathsf{NP} . 1 1 1 However, it is known that, for a broad class multiplicities, a natural asymptotic version of the positivity problem is in \mathsf{NP}\cap\mathsf{coNP} [ 10 ] . As representation-theoretic multiplicities are linear-algebraic quantities defined in high dimensions, it is natural to study their complexity from the perspective of quantum computation. In particular, their very definition as the dimension of the space of multiplicities of some irreducible representation, gives the hope that one could place them in the quantum complexity class \#\mathsf{BQP} , the quantum analogue of \#\mathsf{P} , by the intuition that these multiplicities might count the dimension of easy-to-recognize subspaces in some bigger vector space. Indeed, in Ref. [ 6 ] it was shown that deciding positivity of Kronecker coefficients is in \mathsf{QMA} , the quantum analogue of \mathsf{NP} , and computing a certain multiple of these coefficients is in \#\mathsf{BQP} . Shortly after, it was shown in Ref. [ 29 ] that computing the Kronecker coefficients, as well as certain special plethysm coefficients (see below), is in \#\mathsf{BQP} . See also Ref. [ 17 ] . In certain parameter regimes, efficient quantum algorithms for computing these multiplicities were proposed in Ref. [ 36 ] , however many of those cases were later shown to be polynomial-time computable by classical algorithms as well [ 51 ] , see also Ref. [ 16 ] . Thus the quantum and classical complexity of representation-theoretic multiplicities is subtle even in special cases. Here we consider this problem from a general perspective, motivated by the outstanding problem of characterizing the complexity of the plethysm coefficients. 1.2 Relevance in algebraic complexity theory and quantum information theory In algebraic complexity theory, geometric complexity theory (GCT) is a program that seeks to establish lower bounds, such as separating \mathsf{VNP} from \mathsf{VP} , by exploiting the symmetries of the universal polynomials, for example the permanent and determinant of a symbolic matrix. One approach via algebraic geometry and representation theory goes via so-called multiplicity obstructions . Namely, decompose the coordinate rings of the \GL -orbit closures of a \mathsf{VNP} -complete polynomial (usually the permanent) into irreducible components, and compare the multiplicities of these components to the ones corresponding to a universal polynomial for \mathsf{VP} (usually the determinant). The plethysm coefficients (as well as the Kronecker coefficients) play a natural and significant role in such computations, for example as upper bounds or even as part of explicit formulas for such multiplicities, see Refs. [ 9 , 12 , 14 , 15 , 23 , 28 ] . The GCT program can also be adapted to other situations, such as finding lower bounds for the complexity of the matrix multiplication problem [ 12 ] , and representation-theoretic multiplicities again turn out to be crucial. In quantum physics, representation-theoretic multiplicities are ubiquitous since the state of quantum systems are described by (unit) vectors in high-dimensional complex vector spaces, which are acted upon (unitarily) by symmetry groups. In some situations (e.g., high energy physics) the groups and representations of interest are fixed, in quantum information and computation one naturally considers sequences of groups and representations. One important setting is the one-body quantum marginal problem. Indeed, the compatibility of the one-body marginals with an overall pure state is guided by the Kronecker coefficients [ 18 , 19 , 32 ] , while the plethysm coefficients appear in the fermionic version of the problem [ 1 ] , known as the one-body N -representability problem in quantum chemistry [ 20 ] , which has been studied at least since the early 1970s [ 5 ] . 1.3 Summary of contributions We now present our main results, starting with the quantum complexity of plethysm coefficients. We first give a brief definition of plethysms (see Section 2 for more detail). Let V\cong\mathbbm{C}^{n} be a finite-dimensional complex vector space. Recall that the irreducible polynomial complex representations of the general linear group \GL(V) are labeled by integer partitions with no more than n parts. Given such a partition \nu , we denote by \rho_{\GL(V),\nu}\colon\GL(V)\to\GL(\{\nu\}_{\GL(V)}) the corresponding irreducible representation, where \{\nu\}_{\GL(V)} denotes the representation space, called Weyl module . If \nu has more than n parts, we define \rho_{\GL(V),\nu} as the zero-dimensional representation. We abbreviate H\coloneqq\GL(V) , and consider the group G\coloneqq\GL(\{\nu\}_{H}) along with one of its polynomial representations \rho_{G,\mu} , where \mu is again an integer partition. Then the composition \rho_{G,\mu}\circ\rho_{H,\nu}\colon H\to\GL(\{\mu\}_{G}) (1.1) is a representation of H=\GL(V) . We shall denote the corresponding representation space by \{\mu\}\!\!\downarrow^{\GL(\{\nu\}_{H})}_{H} to remember that we regard it as a module of H , by restriction along the irreducible representation \rho_{H,\nu}\colon H\to G=\GL(\{\nu\}_{H}) . In general, the representation ( 1.1 ) is reducible and hence it decomposes into irreducible H -representations. Thus: \displaystyle\{\mu\}\!\!\downarrow^{\GL(\{\nu\}_{H})}_{H}\;\cong\;\bigoplus_{\lambda}\underbrace{\{\lambda\}_{H}\oplus\dots\oplus\{\lambda\}_{H}}_{a^{\lambda}_{\mu,\nu}}\;\cong\;\bigoplus_{\lambda}\{\lambda\}_{H}\otimes\mathbbm{C}^{a^{\lambda}_{\mu,\nu}}. (1.2) The plethysm coefficient a^{\lambda}_{\mu,\nu} is defined as the multiplicity of the irreducible module \{\lambda\}_{H} in this decomposition. Here we assume that \lambda has no more than n=\dim(V) parts, in which case the coefficient does not depend on the choice of n but only on the three partitions \lambda,\mu,\nu . Problem 1.1 (Plethysm coefficients) . Input: Three partitions \lambda , \mu , \nu , encoded as lists of positive integers, in unary. Task: Compute the plethysm coefficient a^{\lambda}_{\mu,\nu} . Encoding the partitions in unary is a standard convention in the literature. Thus the input size is \Theta(\lvert\lambda\rvert+\lvert\mu\rvert+\lvert\nu\rvert) . We give two concrete examples of plethysm coefficients: • If both \mu=(m) and \nu=(d) are partitions with a single part, then \{\mu\}\!\!\downarrow^{\GL(\{\nu\}_{H})}_{H}=\Sym^{m}(\Sym^{d}(V)) can be interpreted as the space of homogeneous polynomials of degree m in variables that are coefficients on the space of homogeneous polynomials of degree d . this space is central in geometric complexity theory and is the main object in the Foulkes conjecture [ 25 ] . • If \mu=(m) and \nu=(1^{d})=(1,\dots,1) , then \{\mu\}\!\!\downarrow^{\GL(\{\nu\}_{H})}_{H}=\Sym^{m}(\Alt^{d}(V)) corresponds to the space of polynomials in the coefficients of a wavefunction of d fermions, each having Hilbert space V . This is directly relevant to the N -representability problem in quantum chemistry [ 1 , 33 ] . The general case is a major problem in algebraic combinatorics as stated in Ref. [ 54 , Problem 9] . Prior work [ 29 ] showed that the former example is in \#\mathsf{BQP} , but already the latter example was out of reach for earlier methods. Here we prove that the general plethysm problem is in \#\mathsf{BQP} : Theorem 1.2 . 1.1 is in \#\mathsf{BQP} . As a consequence, the problem of deciding if a plethysm coefficient is positive, a^{\lambda}_{\mu\nu}>0 , is in \mathsf{QMA} . The corresponding quantum algorithm is sketched in Fig. 1 and we describe its main ideas in Section 1.4 . The above also implies an analogous result for the restriction coefficients r_{\lambda}^{\mu} , defined as the multiplicy of an irreducible S_{n} -representation (Specht module) in the restriction of an irreducible \GL(n) -representation (Weyl module) to the subgroup S_{n}\subset\GL(n) of permutation matrices. Indeed, the restriction coefficients can be expressed as a positive sum of plethysms: using symmetric functions (see Section 2.1 for definitions), we have r_{\lambda}^{\mu}=\langle s_{\mu},s_{\lambda}[1+h_{1}+h_{2}+\cdots]\rangle . Thus, computing restriction coefficients is in \#\mathsf{BQP} and their positivity is in \mathsf{QMA} , as an immediate corollary of 1.2 . We obtain 1.2 by specialization of a general theorem that applies to a broad class of multiplicities known as branching multiplicities (or coefficients) . They are defined as follows: We consider groups G and H , together with a group homomorphism \varphi\colon H\to G . Any representation \pi\colon G\to\GL(W) of G then restricts to a representation of H by composition with \varphi , i.e., \pi\circ\varphi\colon H\to\GL(W) . The corresponding branching multiplicities are defined as the multiplicities of irreducible H -representation in the restriction \pi\circ\varphi . Here we consider branching multiplicites in the setting where G and H are products of general linear groups , and where the group homomorphism \varphi and the G -representation \pi are specified succinctly in terms of representation-theoretic data. See 2.1 for the formal definition. This encompasses, among others, all coefficients studied in prior work: Kostka numbers, LR coefficients, and Kronecker coefficients, see Section 3 (of course, the first two are even in \#\mathsf{P}\subset\#\mathsf{BQP} , while for the latter this is an open problem). It is known that computing branching multiplicities can be done in classical polynomial time when G and H are fixed . This holds not just for products of general linear groups, but more generally in the setting of complex reductive (or compact connected) Lie groups [ 16 ] . In contrast, here we allow the groups (as well as the representations) to be part of the input. This is substantially more difficult since it involves representations that in general have dimensions that are exponential in the input size. Theorem 1.3 . Computing branching multiplicities for products of general linear groups ( 2.1 ) is in \#\mathsf{BQP} . As a consequence, deciding their positivity is in \mathsf{QMA} . We prove 1.3 as 5.1 by giving a quantum algorithm that is perfectly sound and complete (if the gate set is such that the circuit can be implemented perfectly), similarly to the algorithms in Refs. [ 6 , 29 ] . In particular, this shows that the positivity problem is in \mathsf{QMA}_{1} if there exists a universal gate set such that the high-dimensional version of the quantum Schur transform on (\mathbbm{C}^{d})^{\otimes N} can be implemented exactly for any choice of N and d . We discuss the main technical ideas behind our quantum algorithms in Section 1.4 . Moreover, in Appendix A , we describe a general approach for showing that representation-theoretic multiplicities are in \#\mathsf{BQP} that subsumes the quantum algorithms of this paper as well as those of the prior works [ 6 , 29 ] and explains their relation. As discussed, the plethysm coefficients and in fact most representation-theoretic coefficients are \#\mathsf{P} -hard, and it is a central open question to determine when they are in \#\mathsf{P} , see Refs. [ 45 , 49 ] . By 1.2 , a negative answer to this question would imply a breakthrough separation between the complexity classes \#\mathsf{P} and \#\mathsf{BQP} . To gain further insight into their computational complexity, we complement our quantum results by showing that the branching multiplicities are also in \mathsf{GapP} , see Section 6 , extending earlier results in Refs. [ 11 , 46 , 48 ] . Theorem 1.4 . Computing branching multiplicities for products of general linear groups ( 2.1 ) is in \mathsf{GapP} . We prove 1.4 as 6.1 . We also present a more specialized algorithm for computing the plethysm coefficients, see 6.2 . In particular, we obtain a polynomial time algorithm when the number of parts of \lambda and the size of \mu are fixed, extending the results of Ref. [ 51 ] . 1.4 Methods {\lx@inpgf@ignorespaces\vdots} {\lx@inpgf@ignorespaces\vdots} {\lx@inpgf@ignorespaces\vdots} {\lx@inpgf@ignorespaces\vdots} \ket{\nu} \mathcal{S}^{-1} \mathcal{S}^{-1} \mathcal{S} \mathcal{S} \ket{\mu} \mathcal{S}^{-1} \mathcal{S}^{-1} A \ket{\psi_{\nu}} witness A \ket{\nu} \mathcal{S}^{-1} \mathcal{S}^{-1} \ket{\psi_{\mu}} \ket{\psi_{\nu}} Embedding |\nu| |\nu|\cdot|\mu| Strong Fourier sampling |\mu| |\nu| Figure 1 : Quantum circuit for the plethysm coefficient a^{\lambda}_{\mu,\nu} ( 1.2 ). The witness is input in the space \{\mu\}_{\GL(\{\nu\}_{H})} . The first inverse Schur transform embeds it into \lvert\mu\rvert registers, each isomorphic to \{\nu\}_{H} . The second layer of inverse Schur transforms embeds each register into \lvert\nu\rvert registers of dimension n . After the final Schur transform, we measure the registers corresponding to the partition and the Weyl module. We accept if and only if the former returns outcome \lambda and the latter p_{0} , where \ket{p_{0}}\in\{\lambda\}_{H} is an arbitrary fixed basis state of the Weyl module. We briefly discuss the main ideas behind our results, focusing on the special case of plethysm coefficients for concreteness ( 1.2 ). Quantum algorithm for plethysm coefficients The algorithm in this case is sketched in Fig. 1 and formally described in Section 5.1 . Let \lambda,\mu,\nu be partitions and V=\mathbbm{C}^{n} . We may assume that the number of parts of the partitions and n are such that the corresponding Weyl modules are nonzero, otherwise the plethysm coefficient a^{\lambda}_{\mu,\nu}=0 . Our approach uses Schur-Weyl duality to embed the H -module \{\mu\}\!\!\downarrow^{G}_{H} inside V^{\otimes\lvert\nu\rvert\cdot\lvert\mu\rvert} , where G=\GL(\{\nu\}_{H}) and H=\GL(V) as before. This is achieved as follows: We first embed the G -module \{\mu\}_{G} in a tensor power of \{\nu\}_{H} , which is the defining module of G=\GL(\{\nu\}_{H}) . We then consider each \{\nu\}_{H} as a H -module and embed it into a tensor power of V , which is the defining module of H=\GL(V) . Since \{\mu\}\!\!\downarrow^{G}_{H} is nothing but the restriction of the G -module \{\mu\}_{G} to H , we obtain the following chain of H -equivariant inclusions \displaystyle\{\mu\}\!\!\downarrow^{G}_{H}\;\hookrightarrow\;\left\lparen\{\nu\}_{H}\right\rparen^{\otimes\lvert\mu\rvert}\;\hookrightarrow\;V^{\otimes|\nu|\cdot|\mu|}. (1.3) In order to implement these embeddings, we employ inverse quantum Schur transforms, as these allow us to map from the Schur basis of the tensor power spaces to the standard basis (blue box in Fig. 1 ). After the embeddings, we implement a final (forward) quantum Schur transform on all \lvert\nu\rvert\cdot\lvert\mu\rvert registers and measure in the Schur basis – accepting if and only if we obtain the partition \lambda , meaning that the input state was in the \lambda -isotypic component of \{\mu\}\!\!\downarrow^{G}_{H} , and if we obtain an arbitrary but fixed basis state p_{0} on the Weyl module register (green box in Fig. 1 ). As inclusions are H -equivariant, they preserve the dimension of the isotypic component, and they act as the identity on the Weyl module. As such, the entire circuit implements a projective measurement, and the dimension of the space of witnesses that are accepted with probability one (assuming the quantum Schur transform is implemented exactly) is exactly the multiplicity of \{\lambda\}_{H} in \{\mu\}\!\!\downarrow^{G}_{H} . By Eq. 1.2 , this multiplicity is exactly the plethysm coefficient a_{\mu,\nu}^{\lambda} . Generalization to branching multiplicities Our result for the branching problem for products of general linear groups ( 2.1 and 1.3 ) is based a natural generalization of this idea. The quantum algorithm is described in Section 5.2 and analyzed in 5.1 . One conceptual contribution is to identify an appropriate definition of the computational problem. This is subtle, as it involves objects that will in general be exponentially large and hence need to be succinctly specified in order to obtain a nontrivial computational problem that captures the plethysm coefficients and other classical coefficients as special cases (see 2.1 and 2.4 ). On the algorithmic side, we employ a similar sequence of embeddings as before, this time on products of tensor powers of the defining modules, and implemented by a sequence of parallel quantum circuits. In our general setting, the defining modules for G need no longer be irreducible as H -modules, requiring us to implement intermediate measurements in order to realize the subsequent embeddings. See Section 5.2 for further details. Comparison with prior work Previous results on the quantum computation of Kronecker and special plethysm coefficient employed the formulation of these coefficients in terms of the symmetric group S_{n} and rely on Beals’ quantum Fourier transform for S_{n} [ 4 ] . In principle, any plethysm coefficient can be computed as branching multiplicities of representations of wreath products of symmetric groups. However, as pointed out in Ref. [ 36 ] , a direct use of Beals’ quantum Fourier transform leads to an exponential blowup in general. As such it is not immediately clear how to generalize the symmetric group approach to the general plethysm problem ( 1.1 ). We overcome this challenge by working with the representation theory of the general linear group. In this regard we may view this approach as the “Schur-Weyl dual” of prior approaches to treat representation-theoretic multiplicities. We emphasize that the local dimensions in our setting (such as the dimension of \{\nu\}_{H} ) can be exponentially large . Accordingly, we require a version of the quantum Schur transform that only depends polylogarithmically on the local dimensions. This has recently been achieved in Ref. [ 8 ] , see also Ref. [ 26 ] . In contrast, for the Kronecker coefficients the relevant local dimension are polynomial and hence the original quantum Schur transform suffices. We discuss quantum algorithms for the Schur transform in more detail in Section 4.2 . Unified approach towards multiplicities Despite the difference between these approaches there is a unified picture that captures both and which applies even more broadly, to the general problem of the multiplicity of an irreducible H -module V_{\lambda} in an H -module V , for some group H . Consider the following two-step procedure: 1. Embed the H -module V we wish to decompose into an H -module V_{\text{model}} . 2. Apply strong Fourier sampling for V_{\text{model}} and accept if the outcome consists of is the label of the irreducible representation V_{\lambda} , together with a fixed basis state \ket{p}\in V_{\lambda} . It is clear that if these two steps can be efficiently implemented, then the multiplicity problem is in \#\mathsf{BQP} , and the corresponding decision problem is in \mathsf{QMA} . Remarkably, this captures both the approach of this work and the prior works: • For the plethysm problem, V=\{\mu\}\!\!\downarrow^{G}_{H} and V_{\text{model}}=(\mathbbm{C}^{n})^{\otimes\lvert\nu\rvert\cdot\lvert\mu\rvert} . The first (embedding) step is achieved by the two layers of inverse Schur transforms (blue box in Fig. 1 ), while the second (strong Fourier sampling) step is achieved by the (forward) Schur transform and subsequent measurements (green box in Fig. 1 ). Our more general algorithm for the branching problem of products of general linear groups likewise fits this picture. • The key ingredient of Refs. [ 6 , 29 ] is the generalized phase estimation circuit [ 26 ] , which likewise admits a natural interpretation in this framework. Here, V_{\text{model}}=\mathbbm{C}[H]\otimes V , where \mathbbm{C}[H] is the group ring and H acts on \mathbbm{C}[H] but not on V , the first (embedding) step is realized using the controlled group action of V (that is, the unitary \ket{h}\ket{\psi}\mapsto\ket{h}\ket{h\cdot\psi} on \mathbbm{C}[H]\otimes V ), and the second (strong Fourier sampling) step is implemented using the Fourier transform of the group. 2 2 2 In Ref. [ 6 ] the authors use weak Fourier sampling and therefore prove membership in \#\mathsf{BQP} for a scaled version of the Kronecker coefficients (namely, the Kronecker coefficients multiplied by the dimension of corresponding irreducible representations). This procedure applies whenever the controlled group action and the Fourier transform of the group can be efficiently implemented, see A.6 . We can also combine these two ideas. For example, the restriction coefficients r_{\lambda}^{\mu} can be captured by an embedding step that first uses an inverse Schur transform (as in the first bullet point) to realize \{\lambda\}_{\GL(n)} in V=(\mathbbm{C}^{n})^{\otimes\lvert\lambda\rvert} , following by GPE (as in the second bullet point), noting that the controlled group action of S_{n} on \mathbbm{C}^{n} can be efficiently implemented. We expand on this general perspective in Appendix A . 2 Preliminaries and problem description In this section we provide the notation and definitions that we use throughout this manuscript, as well as two definitions of the general branching problem. 2.1 General notation We will use standard notions from combinatorial representation theory and refer the reader to Refs. [ 52 , 53 , 30 ] for background. Partitions A partition of a positive integer n into d parts is denoted \lambda\vdash_{d}n , is a weakly decreasing sequence of d non-negative integers \lambda=(\lambda_{1},\ldots,\lambda_{d}) such that \lambda_{1}+\cdots+\lambda_{d}=n . We write |\lambda|=\lambda_{1}+\cdots+\lambda_{d} for the size of \lambda and \ell(\lambda) for the number of nonzero parts (note that \ell(\lambda)\leq d) . A partition is often depicted visually as a Young diagram . We note that in our use of partitions and diagrams, we will have to keep track of the zero parts (zero rows) to be consistent with their role as highest weights . The set of partitions of n with at most d parts is denoted by \mathcal{P}_{d}(n):=\{\lambda\vdash_{d}n\} . The set of all partitions with at most d parts is \mathcal{P}_{d}=\cup_{n>0}\mathcal{P}_{d}(n) . We let \mathcal{P}(n) be the set of all partitions of n (disregarding trailing 0s), and \mathcal{P}=\cup_{n\geq 0}\mathcal{P}(n) be the set of all possible partitions. Irreducible modules Let \GL(d) be the general linear group of d\times d complex matrices. Its irreducible modules are the Weyl modules , indexed by dominant weights. Throughout the manuscript, we restrict to polynomial representations, in which case the dominant weights can be identified with partitions \lambda\in\mathcal{P}_{d} . We will denote the irreducible Weyl module indexed by \lambda as \{\lambda\}_{d} . For a tuple \bm{\mathbf{\lambda}}=(\lambda^{1},\dots,\lambda^{r})\in\mathcal{P}_{d_{1}}\times\cdots\times\mathcal{P}_{d_{r}} , the corresponding irreducible \GL(d_{1})\times\cdots\times\GL(d_{r}) -module is denoted \{\bm{\mathbf{\lambda}}\}_{d_{1},\dots,d_{r}}=\{\lambda^{1}\}_{d_{1}}\otimes\cdots\otimes\{\lambda^{r}\}_{d_{r}} , or simply \{\bm{\mathbf{\lambda}}\}_{G} if G:=\GL(d_{1})\times\cdots\times\GL(d_{r}) . The irreducible modules of the symmetric group S_{n} are the Specht modules , indexed by \lambda\in\mathcal{P}(n) . We will denote them by [\lambda] . The characters of S_{n} are denoted by \chi^{\lambda} and are evaluated at partitions \alpha\in\mathcal{P}(n) , which correspond to the conjugacy classes of S_{n} , denoted C_{\alpha} , consisting of all permutations of cycle type \alpha . Symmetric functions and tableaux The characters of \{\lambda\}_{d} are the Schur polynomials s_{\lambda}(x_{1},\ldots,x_{d}) . As d\to\infty , these become the Schur functions, which form a basis for the ring of symmetric functions \Lambda . Other notable bases for this ring are the homogeneous \{h_{\lambda}\} , elementary \{e_{\lambda}\} , power sum \{p_{\lambda}\} , and monomial symmetric functions \{m_{\lambda}\} , with \lambda\in\mathcal{P}(n) for the degree n component. The Schur functions can be defined as the generating function of semistandard Young tableaux (SSYT) , which are assignments of integers in the Young diagram of \lambda that are weakly increasing along rows and strictly increasing down columns. See Refs. [ 53 , 40 ] for background on symmetric functions. The dimension of the Weyl module \{\lambda\}_{d} is the number d_{\lambda} of semistandard Young tableaux of shape \lambda with entries in \{1,\dots,d\} , is a polynomial in d of degree |\lambda| , and can be efficiently (in \log(d) and |\lambda| ) computed via the hook-content formula : \dim(\{\lambda\}_{d})=\prod_{(i,j)\in\lambda}\frac{d+c_{\lambda}(i,j)}{h_{\lambda}(i,j)}, (2.1) where the product is over all boxes (i,j) in the Young diagram of \lambda , c(i,j)=j-i is the content of the box and h(i,j) is the hook length of the box. It is upper-bounded by d^{|\lambda|} and |\lambda|^{d(d-1)/2} . The dimension of the Specht module [\lambda] is given by the number f^{\lambda} of standard Young tableaux (SYT) , which are SSYT of shape \lambda with each integer 1,\ldots,|\lambda| appearing exactly once, and can be efficiently computed via the hook length formula : f^{\lambda}=|\lambda|!\prod_{(i,j)\in\lambda}\frac{1}{h_{\lambda}(i,j)}. (2.2) 2.2 Main representation-theoretic multiplicities We give equivalent definitions for the main representation-theoretic multiplicities, in terms of multiplicities of irreducible representations as well as in term of decomposition of symmetric functions. Plethysm coefficients The plethysm coefficients a^{\lambda}_{\mu,\nu} were originally defined in Ref. [ 38 ] as the multiplicity of the irreducible \GL(n) -module \{\lambda\}_{n} in the plethystic composition of \GL -modules indexed by \mu and \nu , as in Equation 1.2 , whenever n\geq\max(\ell(\lambda),\ell(\nu)) and \dim\{\nu\}_{n}\geq\ell(\mu) . Understanding decompositions of representations is often done through characters in practice, as the ring of symmetric functions captures all relevant information and can allow us to extract multiplicities as coefficients in polynomial expansions. In the language of symmetric functions, see Refs. [ 53 , 40 ] , the plethysm of two symmetric functions f and g , where g has nonnegative integer coefficients and so can be written as a sum of monomials g=x^{\alpha^{1}}+x^{\alpha^{2}}+\cdots , is defined as f[g]=f(x^{\alpha^{1}},x^{\alpha^{2}},\cdots) . The plethysm of Schur functions then decomposes as: s_{\mu}[s_{\nu}]=\sum_{\lambda}a^{\lambda}_{\mu,\nu}s_{\lambda}. In terms of symmetric group characters, the plethysm coefficients can be computed using the formula: a^{\lambda}_{\mu,\nu}=\sum_{\alpha\vdash m}\sum_{\gamma^{1},\gamma^{2},\ldots\vdash k}\frac{\chi^{\mu}(\alpha)}{z_{\alpha}}\frac{\chi^{\nu}(\gamma^{1})}{z_{\gamma^{1}}}\frac{\chi^{\nu}(\gamma^{2})}{z_{\gamma^{2}}}\cdots\chi^{\lambda}(\alpha_{1}\gamma^{1},\alpha_{2}\gamma^{2},\cdots), where the sum is over partitions \alpha,\gamma^{1},\gamma^{2},\ldots , the last character is evaluated at the partition obtained by scaling each partition \gamma^{i} ’s parts by \alpha_{i} and concatenating those integers to form a partition of n=mk . Here z_{\theta}=\prod i^{m_{i}}m_{i}! where \theta=(1^{m_{1}},2^{m_{2}},\ldots) . Kronecker coefficients The Kronecker coefficients g_{\lambda,\mu,\nu} , for |\lambda|=|\mu|=|\nu| , are defined as the multiplicities of the \GL(d_{1})\times\GL(d_{2}) irreducible module \{\nu\}_{d_{1}}\otimes\{\lambda\}_{d_{2}} in the \GL(d_{1}\cdot d_{2}) module \{\mu\}_{d_{1}\cdot d_{2}} . \{\mu\}_{d_{1}\cdot d_{2}}\downarrow^{\GL(d_{1}\cdot d_{2})}_{\GL(d_{1})\times\GL(d_{2})}=\bigoplus_{\begin{subarray}{c}\nu,\lambda\end{subarray}}\{\nu\}_{d_{1}}\otimes\{\lambda\}_{d_{2}}\otimes\mathbbm{C}^{g_{\lambda,\mu,\nu}}. where the restriction is given by the inclusion \GL(d_{1})\times\GL(d_{2})\rightarrow\GL(d_{1}\cdot d_{2}):(g_{1},g_{2})\mapsto g_{1}\otimes g_{2} . They can also be defined as the decomposition coefficients for the tensor product of symmetric group representations: [\mu]\otimes[\nu]=\bigoplus_{\lambda}[\lambda]\otimes\mathbbm{C}^{g_{\lambda,\mu,\nu}}. In terms of symmetric functions, they are defined via the internal product of Schur functions: s_{\lambda}(\mathbf{x}\cdot\mathbf{y})=\sum_{\mu,\nu}g_{\lambda,\mu,\nu}s_{\mu}(\mathbf{x})s_{\nu}(\mathbf{y}), where \mathbf{x}\cdot\mathbf{y} denotes the set of pairwise products of variables (x_{1}y_{1},x_{1}y_{2},\ldots,x_{2}y_{1},\ldots) . Littlewood-Richardson coefficients The Littlewood-Richardson coefficients c^{\lambda}_{\mu\nu} are the decomposition coefficients for the product of Schur functions. They are defined as the multiplicities in the decomposition of the tensor product of two Weyl modules: \{\mu\}_{d}\otimes\{\nu\}_{d}\cong\bigoplus_{\lambda}\{\lambda\}_{d}\otimes\mathbbm{C}^{c^{\lambda}_{\mu\nu}}. Equivalently, in terms of Schur functions, they are defined by the product rule: s_{\mu}s_{\nu}=\sum_{\lambda}c^{\lambda}_{\mu\nu}s_{\lambda}. Kostka numbers The Kostka numbers K_{\lambda\mu} are defined as the dimension of the weight space of weight \mu in the \GL(d) -module \{\lambda\}_{d} . Equivalently, they count the number of semistandard Young tableaux of shape \lambda and content \mu (i.e., the number of entries equal to i is \mu_{i} ). In the ring of symmetric functions, they serve as the transition coefficients between the Schur, monomial, and homogeneous symmetric function bases: s_{\lambda}=\sum_{\mu}K_{\lambda\mu}m_{\mu}\qquad\text{and}\qquad h_{\mu}=\sum_{\lambda}K_{\lambda\mu}s_{\lambda}. 2.3 Branching problem description In the following, we describe the computational problem we study in this manuscript. This can be considered as a generalization of the main representation-theoretic multiplicities discussed above. Let G=\GL(d_{1})\times\cdots\times\GL(d_{r_{G}}) and H=\GL(n_{1})\times\cdots\times\GL(n_{r_{H}}) be products of general linear groups, for some positive integers {r_{G}},{r_{H}},d_{1},\dots,d_{r_{G}},n_{1},\dots,n_{r_{H}} . Given a group homomorphism \varphi:H\to G , any representation of G can be viewed as a representation of H by composition, in which case we say that the corresponding G -module restricts to H . When an irreducible G -module \{\bm{\mathbf{\mu}}\}_{G} is restricted to H we denote it by \{\bm{\mathbf{\mu}}\}\!\!\downarrow^{G}_{H}(\varphi) , or \{\bm{\mathbf{\mu}}\}\!\!\downarrow^{G}_{H} , omitting the dependency on \varphi when the choice is clear. Such a module is generally reducible, decomposing into a direct sum of irreducible H -modules: \{\bm{\mathbf{\mu}}\}\!\!\downarrow^{G}_{H}\;\cong\;\bigoplus_{\bm{\mathbf{\lambda}}}\{\bm{\mathbf{\lambda}}\}_{H}\otimes\mathbbm{C}^{m_{\bm{\mathbf{\mu}},\bm{\mathbf{\lambda}}}}. (2.3) The sum is over all partition tuples \bm{\mathbf{\lambda}}\in\mathcal{P}_{n_{1}}\times\cdots\times\mathcal{P}_{n_{r_{H}}} corresponding to irreducible representations of H . The non-negative integers m_{\bm{\mathbf{\mu}},\bm{\mathbf{\lambda}}}(\varphi) , or simply m_{\bm{\mathbf{\mu}},\bm{\mathbf{\lambda}}} , are called the branching multiplicities of H in G (with respect to \varphi ). Equivalently, the branching multiplicity m_{\bm{\mathbf{\mu}},\bm{\mathbf{\lambda}}} can be defined as the dimension of the space of H -module homomorphisms ( intertwiners ) from the irreducible module \{\bm{\mathbf{\lambda}}\}_{H} to the restricted module \{\bm{\mathbf{\mu}}\}\!\!\downarrow^{G}_{H} : m_{\bm{\mathbf{\mu}},\bm{\mathbf{\lambda}}}(\varphi):=\dim\left(\text{Hom}_{H}(\{\bm{\mathbf{\lambda}}\}_{H},\{\bm{\mathbf{\mu}}\}\!\!\downarrow^{G}_{H})\right). We can therefore define the branching problem for products of \GL : Problem 2.1 (Branching problem for products of \GL ) . Input: • The specification of the groups H=\GL(n_{1})\times\dots\times\GL(n_{r_{H}}) and G=\GL(d_{1})\times\cdots\times\GL(d_{r_{G}}) 3 3 3 In fact, we will see that the dimensions d_{1},\dots,d_{r_{G}} can be inferred from the specification of the group homomorphism, as such they need not be specified explicitly in this step, and we can assume that they are not given to our quantum algorithm. • The specification of a group homomorphism \varphi\colon H\to G • The specification of irreducible representations \{\bm{\mathbf{\lambda}}\}_{H} and \{\bm{\mathbf{\mu}}\}_{G} for H and G respectively Task: Compute the branching multiplicity m_{\bm{\mathbf{\mu}},\bm{\mathbf{\lambda}}} , defined as the multiplicity of the irreducible module \{\bm{\mathbf{\lambda}}\}_{H} in the restriction \{\bm{\mathbf{\mu}}\}\!\!\downarrow^{G}_{H} along the group homomorphism \varphi\colon H\to G ( Eq. 2.3 ). To rigorously define the computational problem, we still need to specify the encoding for the input of 2.1 . We discuss this in detail in the following. 2.4 Encoding of the input The branching multiplicities, as defined above, depend on three different kind of inputs, being the definition of the groups G and H , the labels of the relative irreducible representations and the specific mapping \varphi:H\rightarrow G . The specification of the groups G=\GL(d_{1})\times\cdots\times\GL(d_{r_{G}}) and H=\GL(n_{1})\times\cdots\times\GL(n_{r_{H}}) admits a natural encoding: we simply provide the list of positive integers representing the ranks: {r_{G}},{r_{H}},d_{1},\dots,d_{r_{G}},n_{1},\dots,n_{r_{H}}, which are encoded in binary. The irreducible representations of H and G are labeled by {r_{H}} -tuples and {r_{G}} -tuples of partitions respectively. Our input therefore includes the tuple \bm{\mathbf{\lambda}}=(\lambda^{1},\dots,\lambda^{r_{H}}) for H and \bm{\mathbf{\mu}}=(\mu^{1},\dots,\mu^{r_{G}}) for G , where: \bm{\mathbf{\lambda}}\in\mathcal{P}_{n_{1}}\times\cdots\times\mathcal{P}_{n_{r_{H}}}\quad\text{and}\quad\bm{\mathbf{\mu}}\in\mathcal{P}_{d_{1}}\times\cdots\times\mathcal{P}_{d_{r_{G}}}. As is standard for computational problems involving partitions of unbounded length, these labels are provided in unary encoding. That is, for a partition \alpha of size |\alpha|=k , the input size is taken to be \Theta(k) . We also need to keep tracks of the zero parts of the partitions, to be consistent with their role as highest weights. This can be done by adjoining each partition with a natural number, in binary, indexing the number of rows. That is, for the partition \alpha=(5,4,2) labeling an irreducible representation for \GL(6) , the encoding we use is [(00000,0000,00),6] . As for the encoding of the homomorphism \varphi:H\rightarrow G , the matter is more delicate, mainly because we want 2.1 to be a proper generalization of the computation of the standard representation-theoretic multiplicities, and in particular of 1.1 . Consider the plethysm case, where H=\GL(n) , G=\GL(\{\nu\}_{H}) for a irreducible representation of H labeled by \nu\in\mathcal{P}_{n} , and we are interested in representations labeled by \lambda\in\mathcal{P}_{n} and \mu\in\mathcal{P}_{d_{\nu}} , where d_{\nu}=\dim\{\nu\}_{H} is in general exponential in n+|\nu| . The input we are given in the corresponding instance of 2.1 will be composed of the ranks n and d_{\nu} , the labels \lambda and \mu and the description of the representation \varphi=\rho_{\nu}:H\rightarrow G . Whatever encoding of \varphi we choose, in order to properly generalize the plethysm problem, we need to be able to recover the label \nu from \varphi . Moreover we would need the size of the encoding of \varphi to be at most polynomial in \log(n),|\lambda|,|\mu| and |\nu| , in order to be able to transfer our complexity results to the plethysm coefficients problem, 1.1 . In fact since \varphi does not depend on \lambda and \mu , we would need the description of \varphi to be \poly(|\nu|,\log(n)) . All standard ways to specify a homomorphism H\rightarrow G (e.g. giving the Jacobian matrix of the map at the identity, d\varphi:\mathfrak{h}\to\mathfrak{g} ) will scale with the dimensions of H and G , as such, if we use one of these encodings, the size of the input will, in general, be exponential in the size of our inputs, and will therefore not allow us to generalize, for example, the plethysm problem. Instead, we will make use of the fact that the branching multiplicities do not depend on the full details of the homomorphism \varphi and are in fact fully determined by the decomposition of the defining modules for G as H -modules: \mathbbm{C}^{d_{i}}\!\!\downarrow^{G}_{H}\cong\bigoplus_{j=1}^{t_{i}}\{\bm{\mathbf{\nu}}(i,j)\}_{H}\otimes\mathbbm{C}^{m_{ij}}. This is exactly what we needed to generalize the plethysm case, where the only input required was the single partition \nu defining the full decomposition of the defining module \{\nu\}_{H} for G : \mathbbm{C}^{d_{\nu}}\!\!\downarrow^{G}_{H}\cong\{\nu\}_{H}. We make this observation rigorous in the following lemma: Lemma 2.2 . Let H be a reductive group, G=\GL(d_{1})\times\cdots\times\GL(d_{r_{G}}) and \varphi=(\varphi_{1},\dots,\varphi_{r_{G}}),\ \psi=(\psi_{1},\dots,\psi_{r_{G}}) be homomorphisms from H to G , where \varphi_{i},\ \psi_{i}:H\rightarrow\GL(d_{i}) . Suppose for all i=1,\dots,{r_{G}} that \varphi_{i} and \psi_{i} are equivalent as representations of H , then the branching multiplicities of H in G with respect to \varphi are the same as those with respect to \psi . Proof. Suppose we are given two homomorphisms \varphi,\ \psi as in the statement of the lemma, we need to prove that for any irreducible G -module \{\bm{\mathbf{\mu}}\}_{G} , the restricted H -modules are equivalent: \{\bm{\mathbf{\mu}}\}\!\!\downarrow^{G}_{H}(\varphi)\cong_{H}\{\bm{\mathbf{\mu}}\}\!\!\downarrow^{G}_{H}(\psi) . For the module \{\bm{\mathbf{\mu}}\}_{G}=\{\mu^{1}\}_{d_{1}}\otimes\cdots\otimes\{\mu^{r_{G}}\}_{d_{r_{G}}} , let \rho_{\bm{\mathbf{\mu}}} be the corresponding representation. By Schur-Weyl duality (see Section 4.2 ) applied to each tensor factor separately, we can embed this as a subrepresentation on the G -module (\mathbbm{C}^{d_{1}})^{\otimes|\mu^{1}|}\otimes\cdots\otimes(\mathbbm{C}^{d_{r_{G}}})^{\otimes|\mu^{r_{G}}|} . As the components \varphi_{i} and \psi_{i} of \varphi and \psi are equivalent representations, then for each i=1,\dots,{r_{G}} there exists an intertwiner f_{i}\in\GL(d_{i}) such that \forall x\in H,\ f_{i}\varphi_{i}(x)=\psi_{i}(x)f_{i} . Then {\left.\kern-1.2ptf_{1}^{\otimes|\mu^{1}|}\otimes\cdots\otimes f_{r_{G}}^{\otimes|\mu^{r_{G}}|}\vphantom{\big|}\right|_{\{\bm{\mathbf{\mu}}\}_{G}}}\in\GL(\{\bm{\mathbf{\mu}}\}_{G}) is an invertible intertwiner for the H -representations \rho_{\bm{\mathbf{\mu}}}\circ\varphi and \rho_{\bm{\mathbf{\mu}}}\circ\psi . Thus the two representations are equivalent, and share the same decomposition into irreducible components. ∎ This allows us to make precise the encoding of the input specifying our group homomorphism: Definition 2.3 (Specification of group homomorphism) . Given H=\GL(n_{1})\times\cdots\times\GL(n_{r_{H}}) and G=\GL(d_{1})\times\cdots\times\GL(d_{r_{G}}) , we will specify a group homomorphism by the following data: • natural numbers t_{i}\in\mathbbm{N} for i\in\{1,\dots,{r_{G}}\} . • natural number m_{ij}\in\mathbbm{N} for i\in\{1,\dots,{r_{G}}\} and j\in\{1,\dots,t_{i}\} , and • partition tuples \bm{\mathbf{\nu}}(i,j)\in\mathcal{P}_{n_{1}}\times\dots\times\mathcal{P}_{n_{r_{H}}} for i\in\{1,\dots,{r_{G}}\} and j\in\{1,\dots,t_{i}\} such that d_{i}=\sum_{j=1}^{t_{i}}m_{ij}\dim\{\bm{\mathbf{\nu}}(i,j)\}_{H} . This data determines a group homomorphism \varphi\colon H\to G , as follows: For i=1,\dots,{r_{G}} , define the H -modules V_{i}:=\bigoplus_{j=1}^{t_{i}}\{\bm{\mathbf{\nu}}(i,j)\}_{H}\otimes\mathbbm{C}^{m_{ij}} . Identify V_{i}\cong\mathbbm{C}^{d_{i}} , to obtain group homomorphisms \varphi_{i}\colon H\to\GL(d_{i}) , and define \varphi:=(\varphi_{1},\dots,\varphi_{r_{G}}) . Of course by 2.2 the choice of group the homomorphism \varphi we use in 2.3 could be replaced with any other group homomorphism such that the defining modules of G restrict to H in accordance with the given data, but the one we choose has the advantage of identifying the computational basis of the defining modules of G with the Fourier basis for the action of H on those same modules. This means that we can freely operate full Fourier sampling (i.e. measure partition type, Gelfand-Tsetlin basis and the multiplicity register) for H on any state expressed in the computational basis for \mathbbm{C}^{d_{i}} . We will make use of this in the algorithm in Section 5.2 . Another advantage of defining the branching problem in terms of the decomposition of the defining modules of G is that we can immediately translate the problem in the language of symmetric functions, to define a dimension-independent version: Problem 2.4 (Dimension-independent branching problem) . Input: • Natural numbers {r_{G}} and {r_{H}} . • For each i\in\{1,\dots,{r_{G}}\} , a symmetric function P_{i} , expressed as a linear combination of products of {r_{H}} Schur functions in independent sets of variables. The data therefore consists of a set of {r_{H}} -tuples of partitions \bm{\mathbf{\nu}}(i,j)=(\nu^{1}(i,j),\dots,\nu^{r_{H}}(i,j)),\ \text{for }i\in\{1,\dots,{r_{G}}\},\ j\in\{1,\dots,t_{i}\}, each in \mathcal{P}^{r_{H}} , and corresponding multiplicities \{m_{i,j}\}_{i,j}\subset\mathbbm{N} . This data defines the symmetric functions: P_{i}=\sum_{j=1}^{t_{i}}m_{i,j}s_{\bm{\mathbf{\nu}}(i,j)}(\mathbf{x}^{1},\dots,\mathbf{x}^{r_{H}}), where \mathbf{x}^{1}=(x_{1}^{1},x_{2}^{1},\dots),\dots,\mathbf{x}^{r_{H}}=(x_{1}^{r_{H}},x_{2}^{r_{H}},\dots) are independent sets of variables, s_{\nu^{k}(i,j)} is the Schur function associated to the partition \nu^{k}(i,j) and s_{\bm{\mathbf{\nu}}(i,j)}(\mathbf{x}^{1},\dots,\mathbf{x}^{r_{H}}):=s_{\nu^{1}(i,j)}(\mathbf{x}^{1})\cdots s_{\nu^{r_{H}}(i,j)}(\mathbf{x}^{r_{H}}). • Tuples of partitions \bm{\mathbf{\mu}}=(\mu^{1},\dots,\mu^{r_{G}})\in\mathcal{P}^{r_{G}} and \bm{\mathbf{\lambda}}=(\lambda^{1},\dots,\lambda^{r_{H}})\in\mathcal{P}^{r_{H}} . Partitions are given in unary encoding. Task: Compute the coefficient of s_{\bm{\mathbf{\lambda}}}(\mathbf{x}^{1},\dots,\mathbf{x}^{r_{H}})=s_{\lambda^{1}}(\mathbf{x}^{1})\cdots s_{\lambda^{r_{H}}}(\mathbf{x}^{r_{H}}) in the Schur expansion of the product of plethysms s_{\mu^{1}}[P_{1}](\mathbf{x}^{1},\dots,\mathbf{x}^{r_{H}})\cdots s_{\mu^{r_{G}}}[P_{r_{G}}](\mathbf{x}^{1},\dots,\mathbf{x}^{r_{H}}). This coefficient, denoted using the Hall inner product, is the integer \langle s_{\mu^{1}}[P_{1}](\mathbf{x}^{1},\dots,\mathbf{x}^{r_{H}})\cdots s_{\mu^{r_{G}}}[P_{r_{G}}](\mathbf{x}^{1},\dots,\mathbf{x}^{r_{H}}),s_{\bm{\mathbf{\lambda}}}(\mathbf{x}^{1},\dots,\mathbf{x}^{r_{H}})\rangle. 2.1 and 2.4 are essentially equivalent: in 2.1 , the decomposition of a representation in irreducible components is equivalent to the decomposition of its character in terms of irreducible characters, which in this case are products of Schur polynomial in independent sets of variables. Passing to the ring of symmetric functions \Lambda with an infinite number of variables returns 2.4 . The Hall inner product is defined in \Lambda , however the resulting identities (expansions of the product of Schur function plethysms into regular Schur functions) hold for any choice of variables. In practice, we can then set some of the variables to 0, reduce to polynomial identities and extract coefficients. Formally, this says that for any sets of input partitions \mathcal{I} , there exists a finite number of variables N_{\mathcal{I}} such that the decomposition of s_{\mu^{1}}[P_{1}](\mathbf{x}^{1},\dots,\mathbf{x}^{r_{H}})\cdots s_{\mu^{r_{G}}}[P_{r_{G}}](\mathbf{x}^{1},\dots,\mathbf{x}^{r_{H}}) is equivalent to the decomposition of the corresponding constructions over Schur polynomials, as long as the Schur polynomials have \geq N_{\mathcal{I}} nonzero variables. In Section 6 we show how this is done in practice. The quantum algorithm we develop in Section 5.2 will tackle 2.1 , while in Section 6 we use the formulation of 2.4 . 3 Representation-theoretic multiplicities as branching multiplicities In this section we present how the general branching multiplicities problem described in 2.1 is a natural generalization of the main problems related to representation-theoretic multiplicities. We use the notation developed in Section 2 , and explicitly state when the numbers defining the dimensions of the groups are large enough for 2.1 to be equivalent to the dimension-independent 2.4 . We represent partitions as Young diagrams. Plethysm coefficients The set of inputs for 2.1 to describe the problem of calculating the plethysm coefficient a_{\mu,\nu}^{\lambda} is: • The specification of the groups: {r_{H}}=1,\ n_{1}\in\mathbbm{N}\quad\text{and}\quad{r_{G}}=1,\ d_{1}=\dim\{\nu\}_{n_{1}}. • The specification of the group homomorphism \varphi , as in 2.3 : t_{1}=1,\quad m_{1,1}=1,\quad\text{and}\quad\bm{\mathbf{\nu}}(1,1)=\nu, where \nu is the single partition representing the H -module structure of the defining module of G . • The specification of the representations: \bm{\mathbf{\mu}}=\mu\quad\text{and}\quad\bm{\mathbf{\lambda}}=\lambda, where the partition \mu indexes a G -module, and the partition \lambda indexes an H -module. Here for 2.1 to be dimension-independent we must have n_{1}\geq\max(\ell(\lambda),\ell(\nu)) and such that \dim\{\nu\}_{n_{1}}\geq\ell(\mu) . As the plethysm coefficient a_{\mu,\nu}^{\lambda} is zero whenever |\mu|\cdot|\nu|\neq|\lambda| , we restrict to the case |\mu|\cdot|\nu|=|\lambda| , in which case we can take n_{1}=|\lambda| as an upper bound. Kronecker coefficients The set of inputs for 2.1 to describe the problem of calculating the Kronecker coefficient g_{\lambda^{1},\lambda^{2},\mu} is: • The specification of the groups: {r_{H}}=2,\ n_{1},n_{2}\in\mathbbm{N}\quad\text{and}\quad{r_{G}}=1,\ d_{1}=n_{1}\cdot n_{2}. • The specification of the group homomorphism \varphi , as in 2.3 : t_{1}=1,\quad m_{1,1}=1,\quad\text{and}\quad\bm{\mathbf{\nu}}(1,1)=(\hbox{\vtop{\halign{&\opttoksa@YT={\font@YT}\getcolor@YT{\save@YT{\opttoksb@YT}}\nil@YT\getcolor@YT{\startbox@@YT\the\opttoksa@YT\the\opttoksb@YT}#\endbox@YT\cr\lower 0.39993pt\vbox{\kern 0.19997pt\hbox{\kern 0.39993pt\vbox to8.39996pt{\vss\hbox to8.00003pt{\hss$$\hss}\vss}\kern-8.39996pt\vrule height=8.39996pt,width=0.39993pt\kern 8.00003pt\vrule height=8.39996pt,width=0.39993pt}\kern-0.19997pt\kern-8.39996pt\hrule width=8.7999pt,height=0.39993pt\kern 8.00003pt\hrule width=8.7999pt,height=0.39993pt}\cr}}\kern 345.4pt},\,\hbox{\vtop{\halign{&\opttoksa@YT={\font@YT}\getcolor@YT{\save@YT{\opttoksb@YT}}\nil@YT\getcolor@YT{\startbox@@YT\the\opttoksa@YT\the\opttoksb@YT}#\endbox@YT\cr\lower 0.39993pt\vbox{\kern 0.19997pt\hbox{\kern 0.39993pt\vbox to8.39996pt{\vss\hbox to8.00003pt{\hss$$\hss}\vss}\kern-8.39996pt\vrule height=8.39996pt,width=0.39993pt\kern 8.00003pt\vrule height=8.39996pt,width=0.39993pt}\kern-0.19997pt\kern-8.39996pt\hrule width=8.7999pt,height=0.39993pt\kern 8.00003pt\hrule width=8.7999pt,height=0.39993pt}\cr}}\kern 345.4pt}), where the pair of partitions represents the H -module structure on the defining module of G . • The specification of the representations: \bm{\mathbf{\mu}}=\mu\quad\text{and}\quad\bm{\mathbf{\lambda}}=(\lambda^{1},\lambda^{2}), where the partition \mu indexes a G -module, and the pair of partitions \bm{\mathbf{\lambda}} indexes an H -module. For the problem to be dimension-independent we must have n_{1}\geq\ell(\lambda^{1}),\ n_{2}\geq\ell(\lambda^{2}) and n_{1}\cdot n_{2}\geq\ell(\mu) . A sufficient condition is n_{1},\ n_{2}\geq|\lambda^{1}|=|\lambda^{2}|=|\mu| . Littlewood-Richardson coefficients The set of inputs for 2.1 to describe the problem of calculating the Littlewood-Richardson coefficient c^{\lambda}_{\mu,\nu} is: • The specification of the groups: {r_{H}}=1,\ n_{1}\in\mathbbm{N}\quad\text{and}\quad{r_{G}}=2,\ d_{1}=n_{1},\ d_{2}=n_{1}. • The specification of the group homomorphism \varphi , as in 2.3 : Thesecorrespondtothepartitionsrepresentingthe H -modulestructureonthedefiningmodulesof G .\par\par\vskip 4.0pt\vskip 4.0pt plus 2.0pt minus 1.0pt\itemize@item@Thespecificationoftherepresentations:$$\bm{\mathbf{\mu}}=(\mu,\nu)\quad\text{and}\quad\bm{\mathbf{\lambda}}=\lambda,$$wherethepairofpartitions μ indexesa G -module,andthepartition λ indexesan H -module.\end{itemize}AstheLittlewood-Richardsoncoefficient c^ λ _ μν isnonzeroonlyif | μ |+| ν |=| λ | ,werestricttothiscase.Fortheproblemtobedimension-independentwemusthave n_1 ≥max(ℓ( λ ),ℓ( μ ),ℓ( ν )) .Asufficientconditionis n_1≥| λ | . Kostka numbers The set of inputs for 2.1 to describe the problem of calculating the Kostka number K_{\lambda\mu} is: – The specification of the groups: {r_{H}}=d,\ n_{1}=\dots=n_{d}=1\quad\text{and}\quad{r_{G}}=1,\ d_{1}=d. – The specification of the group homomorphism \varphi , as in 2.3 : t_{1}=d,\quad\text{and for }j\in\{1,\dots,d\}:\quad m_{1,j}=1,\quad\bm{\mathbf{\nu}}(1,j)=e_{j}, where e_{j} corresponds to the tuple of partitions (0,\dots,\hbox{\vtop{\halign{&\opttoksa@YT={\font@YT}\getcolor@YT{\save@YT{\opttoksb@YT}}\nil@YT\getcolor@YT{\startbox@@YT\the\opttoksa@YT\the\opttoksb@YT}#\endbox@YT\cr\lower 0.39993pt\vbox{\kern 0.19997pt\hbox{\kern 0.39993pt\vbox to8.39996pt{\vss\hbox to8.00003pt{\hss$$\hss}\vss}\kern-8.39996pt\vrule height=8.39996pt,width=0.39993pt\kern 8.00003pt\vrule height=8.39996pt,width=0.39993pt}\kern-0.19997pt\kern-8.39996pt\hrule width=8.7999pt,height=0.39993pt\kern 8.00003pt\hrule width=8.7999pt,height=0.39993pt}\cr}}\kern 345.4pt},\dots,0) with the single box at position j (and 0 is the empty partition). These represent the H -module structure of the defining module for G . – The specification of the representations: \bm{\mathbf{\mu}}=\lambda\quad\text{and}\quad\bm{\mathbf{\lambda}}=(\mu_{1},\dots,\mu_{d}), where the partition \lambda indexes a G -module, and the weight \mu indexes an H -module. As the Kostka number K_{\lambda\mu} is zero whenever |\lambda|\neq|\mu| , we restrict to this case. For the problem to be dimension-independent, we must have d\geq\max(\ell(\lambda),\ell(\mu)) . A sufficient condition is d\geq|\lambda| . We therefore have an immediate reduction from the standard computation of representation-theoretic multiplicities to 2.1 : Lemma 3.1 . 2.1 , when specialized on these four families of inputs, is precisely the problem of evaluating the plethysm coefficients, Kronecker coefficients, Littlewood-Richardson coefficients and Kostka numbers for the same inputs. Proof. For each coefficient, compare with the first definition given in Section 2.2 . ∎ 4 Quantum complexity classes and the Schur transform In the following section we give a definition of the complexity classes \mathsf{QMA} and \#\mathsf{BQP} , and discuss the quantum circuit we will use to implement the Schur transform on our quantum algorithm. 4.1 Quantum complexity classes Definition 4.1 ( \mathsf{QMA} – Quantum Merlin-Arthur) . A language (with promise) L\subseteq\{0,1\}^{*} is in the complexity class \mathsf{QMA} if there exists an uniform family of polynomial-time quantum circuits \{V_{n}\}_{n\in\mathbbm{N}} and a polynomial p(n) such that for any input string x of length n respecting the promise: \displaystyle\forall x\in L,\quad\exists\ket{\psi}\in(\mathbbm{C}^{2})^{\otimes p(n)}:\mathop{\bf Pr\/}[V_{n}(\ket{x},\ket{\psi})\text{ accepts}]\geq\frac{2}{3}, \displaystyle\forall x\notin L,\quad\forall\ket{\psi}\in(\mathbbm{C}^{2})^{\otimes p(n)}:\mathop{\bf Pr\/}[V_{n}(\ket{x},\ket{\psi})\text{ accepts}]\leq\frac{1}{3}. Definition 4.2 ( \#\mathsf{BQP} – Counting- \mathsf{BQP} ) . A (partial) function f:\{0,1\}^{*}\to\mathbbm{N} is in \#\mathsf{BQP} if there exists a uniform family of polynomial-size quantum circuits \{V_{n}\}_{n\in\mathbbm{N}} and a polynomial p(n) such that for any input string x of length n , the witness space for V_{n} being \mathcal{H}=(\mathbbm{C}^{2})^{\otimes p(n)} decomposes as \mathcal{H}=\mathcal{H}_{\text{acc}}(x)\oplus\mathcal{H}_{\text{rej}}(x), with \dim\mathcal{H}_{\text{acc}}(x)=f(x) and \displaystyle\forall\ket{\psi}\in\mathcal{H}_{\text{acc}}(x)\quad\mathop{\bf Pr\/}[V_{n}(\ket{x},\ket{\psi})\ \text{accepts}]\geq\frac{2}{3}, \displaystyle\forall\ket{\psi}\in\mathcal{H}_{\text{rej}}(x)\quad\mathop{\bf Pr\/}[V_{n}(\ket{x},\ket{\psi})\ \text{accepts}]\leq\frac{1}{3}. For both 4.1 and 4.2 , the constants 2/3 and 1/3 can be amplified to be exponentially close to 1 and 0, respectively. 4.2 Schur transform Consider the tensor product space (\mathbbm{C}^{d})^{\otimes n} . On this space, we can define commuting actions of the general linear group \GL(d) and the symmetric group S_{n} , as follows: The action of g\in\GL(d) is defined by its simultaneous application to each tensor factor: g\cdot(v_{1}\otimes v_{2}\otimes\cdots\otimes v_{n})=(gv_{1})\otimes(gv_{2})\otimes\cdots\otimes(gv_{n}), for v_{i}\in\mathbbm{C}^{d} . The action of \sigma\in S_{n} is defined by permuting the tensor factors: \sigma\cdot(v_{1}\otimes v_{2}\otimes\cdots\otimes v_{n})=v_{\sigma^{-1}(1)}\otimes v_{\sigma^{-1}(2)}\otimes\cdots\otimes v_{\sigma^{-1}(n)}. By Schur-Weyl duality , these two actions are maximally commuting, and the space decomposes into a multiplicity-free direct sum of irreducible representations of \GL(d)\times S_{n} : (\mathbbm{C}^{d})^{\otimes n}\cong\bigoplus_{\lambda\in\mathcal{P}_{d}(n)}\{\lambda\}_{d}\otimes[\lambda]. Importantly this implies that each irreducible polynomial representation of \GL(d) can be embedded in the tensor product space (\mathbbm{C}^{d})^{\otimes n} as a subrepresentation. This decomposition motivates a unitary change of basis from the computational basis of (\mathbbm{C}^{d})^{\otimes n} to the Schur basis , denoted by \{\ket{\lambda,p,q}\} . A basis vector \ket{\lambda,p,q} is indexed by a partition \lambda\in\mathcal{P}_{d}(n) , a basis state p from an orthonormal basis for the module \{\lambda\}_{d} , and a basis state q from an orthonormal basis for the module [\lambda] . We denote such a transformation \mathcal{S} and we call it the Schur transform . As we could in principle choose different orthonormal bases for \{\lambda\}_{d} and [\lambda] , there are many possible Schur transforms. In this manuscript we utilize the quantum circuit implementation for the Schur transform from Ref. [ 8 ] , for which the bases of the Weyl modules and of the Specht modules are the Gelfand-Tsetlin basis and the Young-Yamanouchi basis, respectively (together commonly referred to as the Gelfand-Tsetlin bases). Particularly for the Weyl modules, it is useful to discuss the encoding of Gelfand-Tsetlin basis vectors as quantum states. Elements of the Gelfand-Tsetlin basis are indexed by GT patterns (or equivalently by semistandard Young tableaux). As the entries of these patterns contain a number in \{1,\dots,n\} , they can be represented by n -dimensional qudits. Those can then be represented as a subspace of the \lceil\log_{2}n\rceil -qubit space. We refer to Ref. [ 8 ] for the details of the encoding. The first quantum circuit to implement a Schur transform on a quantum system required gate complexity \mathcal{O}(nd^{4}\polylog(n,d)) [ 2 ] (see also Ref. [ 8 ] ). This would be a problem for our protocol as we need to apply Schur transforms to spaces with exponentially high local dimensions d . Recent work shows that it can be done in time \mathcal{O}(n^{4}\polylog(n,d)) [ 8 ] building on ideas in Refs. [ 26 ] and [ 35 ] . Theorem 4.3 ( [ 8 ] ) . There exists a quantum circuit that, with error probability \varepsilon , implements a Schur transform \mathcal{S} with respect to the Gelfand-Tsetlin bases of the \GL(d) and S_{n} modules with gate complexity \mathcal{O}(n^{4}\polylog(n,d,\varepsilon^{-1})) . 5 Algorithms description and analysis In this section we prove the main results of the manuscript. We start with describing our algorithm in the simpler case of plethysm coefficients, which represents both the main motivating example and, in some sense, the simplest application of our method. We then present the general algorithm for 2.1 and prove its correctness. The correctness of the algorithm for the plethysm problem can be inferred as a corollary to the more general proof. 5.1 Algorithm for 1.1 Let n\in\mathbbm{N} , and \lambda,\ \mu,\ \nu partitions. Let H=\GL(n),\ G=\GL(d_{\nu}) , where d_{\nu}:=\dim(\{\nu\}_{n}) , we describe a quantum algorithm taking quantum witnesses from the space \{\mu\}_{G} , accepting with high probability elements from a a_{\mu,\nu}^{\lambda} -dimensional subspace, and rejecting with high probability any element in its orthogonal complement. Algorithm description The algorithm proceeds in three steps: 1. We embed the witness, representing an element in \{\mu\}_{d_{\nu}} , into \{\nu\}_{n}^{\otimes|\mu|} by Schur–Weyl duality, and apply an inverse Schur transform \mathcal{S}^{-1} . 2. We embed each register, representing elements in \{\nu\}_{n} , into (\mathbbm{C}^{n})^{\otimes|\nu|} by Schur–Weyl duality, to get the global space ((\mathbbm{C}^{n})^{\otimes|\nu|})^{\otimes|\mu|} and apply |\nu| local inverse Schur transforms \mathcal{S}^{-1}\otimes\dots\otimes\mathcal{S}^{-1} on each register (\mathbbm{C}^{n})^{\otimes|\nu|} . 3. We apply a Schur transform to the global space (\mathbbm{C}^{n})^{\otimes|\nu||\mu|} , and measure both the partition register and \GL(n) -module register, and accept if the outcome is (\lambda,p_{0}) , for some fixed \ket{p_{0}}\in\{\lambda\}_{n} . Let us look at each step in detail: 1. We add two supplementary registers: the partition register and the symmetric module register . The partition register will be initialized in state \ket{\mu} , while the symmetric-module register will be initialized in a fixed state \ket{\psi_{\mu}}\in[\mu] . We then apply an inverse Schur transform on the 3-registers state, to get a |\mu| -register state expressed in the computational basis \{\ket{i_{1}\dots i_{|\mu|}}\},\ i_{j}\in\{1,\dots,d_{\nu}\} . By 2.2 , we can assume that \GL(n) acts on each i_{j} via some fixed, easy to calculate action, that is we identify the computational basis of \mathbbm{C}^{d_{\nu}} with the Gelfand-Tsetlin basis of \{\nu\}_{n} . 2. We add a partition register in state \ket{\nu} and a symmetric-module register in state \ket{\psi_{\nu}} , for some fixed \ket{\psi_{\nu}}\in[\nu] , to each of the |\lambda| registers. The global state is now expressed in the basis \{\ket{\nu\ i_{1}\ \psi_{\nu}}\otimes\dots\otimes\ket{\nu\ i_{|\lambda|}\ \psi_{\nu}}\} . We then apply local inverse Schur transforms on each group of 3 registers, to get an element expressed in the computational basis \{\ket{i_{1,1}\dots i_{1,|\nu|}}\otimes\dots\otimes\ket{i_{|\mu|,1}\dots i_{|\mu|,|\nu|}}\} , where i_{j,k}\in\{1,\dots,n\} . 3. We relabel the indices of the computational basis as \{\ket{i_{1}\dots i_{|\nu||\mu|}}\} , and a apply a Schur transform on the space (\mathbbm{C}^{n})^{\otimes|\nu||\mu|} . The state will now be expressed in the Schur basis \{\ket{\gamma\ p\ q}\} . We subsequently measure the partition register and H -module register. Finally we accept if and only if the outcome of the measurement is (\lambda,p_{0}) , for some fixed \ket{p_{0}}\in\{\lambda\}_{n} . A circuit representation of the full algorithm is in Fig. 1 5.2 Algorithm for 2.1 This algorithm can be seen as a generalization of the previous one. The main ideas are the same, but we need to be more careful as the defining modules for G are not guaranteed to be irreducible as H -representation, as such we employ an intermediate measurement, which we use to implement the subsequent embedding. For the inputs of 2.1 we describe a quantum verifier taking witnesses in the space \{\bm{\mathbf{\mu}}\}_{G} , accepting with high probability for a m_{\bm{\mathbf{\mu}},\bm{\mathbf{\lambda}}} -dimensional subspace and rejecting with high probability from its orthogonal complement. Algorithm description The algorithm proceeds in the following steps: 1. We embed the witness state \ket{\psi}\in\{\bm{\mathbf{\mu}}\}_{G} in the tensor product space \bigotimes_{i=1}^{r_{G}}(\mathbbm{C}^{d_{i}})^{\otimes|\mu^{i}|} . We do this by considering, on each of the {r_{G}} registers the inclusion given by Schur-Weyl duality: \{\mu^{i}\}_{d_{i}}\hookrightarrow(\mathbbm{C}^{d_{i}})^{\otimes|\mu^{i}|}. (5.1) Implementing this requires adding a partition register (initialized to the partition state \ket{\mu^{i}} ) and a permutation register representing any state \ket{q_{0}}\in[\mu^{i}] . 2. We operate a total of {r_{G}} inverse Schur transforms, each on the space (\mathbbm{C}^{d_{i}})^{\otimes|\mu^{i}|} for i=1,\dots,{r_{G}} . This expresses the local state in the computational basis of the corresponding \mathbbm{C}^{d_{i}} space. 3. By 2.2 , and as explained in 2.3 , we can assume the action of H on the computational basis of \mathbbm{C}^{d_{i}} is known. This allows us to use the decomposition: \mathbbm{C}^{d_{i}}\!\!\downarrow^{G}_{H}\cong\bigoplus_{j=1}^{t_{i}}\{\bm{\mathbf{\nu}}(i,j)\}_{H}\otimes\mathbbm{C}^{m_{i,j}}. (5.2) We perform a measurement on each of the \sum_{i=1}^{r_{G}}|\mu^{i}| sub-registers to determine the corresponding H -isotypic component. After measurement, the state now lives in the space \bigotimes_{i=1}^{{r_{G}}}\bigotimes_{s=1}^{|\mu^{i}|}\{\bm{\mathbf{\nu}}(i,j_{i,s})\}_{H}\otimes\mathbbm{C}^{m_{i,j_{i,s}}}, (5.3) where each index j_{i,s}\in\{1,2,\dots,t_{i}\} is an outcome of a measurement. 4. Accordingly to the measurement outcomes, we use Schur-Weyl duality to embed each of the H -irreducible representation registers into its corresponding tensor product space. This involves adding partition and permutation registers based on the outcomes \nu^{k}(i,j_{i,s}) , resulting in the state being in the space: \bigotimes_{i=1}^{r_{G}}\bigotimes_{s=1}^{|\mu^{i}|}\left(\bigotimes_{k=1}^{r_{H}}(\mathbbm{C}^{n_{k}})^{\otimes|\nu^{k}(i,j_{i,s})|}\right)\otimes\mathbbm{C}^{m_{i,j_{i,s}}}. (5.4) 5. We operate a total of {r_{H}}\sum_{i=1}^{r_{G}}|\mu^{i}| inverse Schur transforms on the spaces (\mathbbm{C}^{n_{k}})^{\otimes|\nu^{k}(i,j_{i,s})|} . This expresses the state in the computational basis of the corresponding \mathbbm{C}^{n_{k}} space. 6. We rearrange the tensor product to group terms by the index k . The space can be written as: \displaystyle\bigotimes_{k=1}^{r_{H}}\left(\bigotimes_{i=1}^{r_{G}}\bigotimes_{s=1}^{|\mu^{i}|}(\mathbbm{C}^{n_{k}})^{\otimes|\nu^{k}(i,j_{i,s})|}\otimes\mathbbm{C}^{m_{i,j_{i,s}}}\right) (5.5) \displaystyle\cong \displaystyle\bigotimes_{k=1}^{r_{H}}\left((\mathbbm{C}^{n_{k}})^{\otimes\sum_{i=1}^{r_{G}}\sum_{s=1}^{|\mu^{i}|}|\nu^{k}(i,j_{i,s})|}\otimes\mathbbm{C}^{\prod_{i=1}^{r_{G}}\prod_{s=1}^{|\mu^{i}|}m_{i,j_{i,s}}}\right) (5.6) \displaystyle\cong \displaystyle\left(\bigotimes_{k=1}^{r_{H}}(\mathbbm{C}^{n_{k}})^{\otimes N_{k}}\right)\otimes\mathbbm{C}^{m}, (5.7) where N_{k}:=\sum_{i=1}^{r_{G}}\sum_{s=1}^{|\mu^{i}|}|\nu^{k}(i,j_{i,s})| and m=\prod_{i=1}^{r_{G}}\prod_{s=1}^{|\mu^{i}|}m_{i,j_{i,s}} . 7. We apply {r_{H}} Schur transforms on the spaces (\mathbbm{C}^{n_{k}})^{\otimes N_{k}} for k=1,\dots,{r_{H}} , to get {r_{H}} registers expressed in the Schur basis, and the final register being H -invariant. For each of the first {r_{H}} registers we measure the corresponding partition and \GL(n_{k}) -module subregisters. We accept if and only if the outcome for each register k is (\lambda^{k},p_{k}) for some predetermined fixed state \ket{p_{k}}\in\{\lambda^{k}\}_{n_{k}} (we may for example choose \ket{p_{k}} to be a Gelfand-Tsetlin basis element). We show a circuit representation of the algorithm in Fig. 2 . Figure 2 : A circuit representation of the algorithm for 2.1 . The states \ket{q_{0}} and \ket{\bm{\mathbf{q_{1}}}} are arbitrary states used for embedding purposes, and their specific initialization does not impact the algorithm correctness. The permute gate applies the rearrangement described in Step 6 . For clarity purposes we avoid drawing the registers containing the invariant spaces for the H -representations coming from the decomposition of the defining modules for G from Step 3 and onward. Using this algorithm we can prove: Theorem 5.1 ( 1.3 ) . 2.1 is in \#\mathsf{BQP} and, consequently, the associated decision problem is in \mathsf{QMA} . Proof. We need to prove the completeness and soundness of the algorithm, and that the circuit is polynomial in the input size. As for the completeness and soundness, we claim the algorithm accepts, with a failure probability equal to that of the circuits used to implement the transforms, any witness from the space W:=\ket{\bm{\mathbf{p}}}\otimes\mathbbm{C}^{m_{\bm{\mathbf{\lambda}},\bm{\mathbf{\mu}}}}\subseteq\{\bm{\mathbf{\lambda}}\}_{H}\otimes\mathbbm{C}^{m_{\bm{\mathbf{\lambda}},\bm{\mathbf{\mu}}}}\subseteq\{\bm{\mathbf{\mu}}\}\!\!\downarrow^{G}_{H}\quad(\text{see \lx@cref{creftype\lx@tilde refnum}{eq:restr repeat}}), where \ket{\bm{\mathbf{p}}}:=\ket{p_{1}}\otimes\ket{p_{2}}\otimes\cdots\otimes\ket{p_{{r_{H}}}} , and rejects, with the same probability, each state from its orthogonal complement W^{\perp}\subseteq\{\bm{\mathbf{\mu}}\}\!\!\downarrow^{G}_{H} . Suppose we are given as a witness state \ket{\psi}\in W . Since the inclusions of Step 1 are H -equivariants operations, and the Schur transforms of Step 2 preserve the G -module (and therefore also the H -module) structure, our state will now be living in the \{\bm{\mathbf{\lambda}}\}_{H} -isotypic component of the product space \bigotimes_{i=1}^{{r_{G}}}(\mathbbm{C}^{d_{i}})^{\otimes|\mu^{i}|}, and in fact will still be of the form \ket{\bm{\mathbf{p}}}\otimes\ket{x} for some \ket{x} living in a multiplicity space. Measuring the label of the H -modules in Step 3 does not change this, as it just tells us which specific product of H -modules gives us the copy of \{\bm{\mathbf{\lambda}}\}_{H} the state gets projected into. With Steps 4 - 7 we perform strong Fourier sampling , meaning we measure the irreducible representation label and the basis element for the irreducible module, at the cost of embedding once again the state in a tensor product space. As all operations we executed in the circuit are H -equivariant, by Schur’s lemma the outcome of the last measurement will be exactly (\lambda_{k},p_{k}) on each register, and we will therefore accept. Conversely, suppose the witness is in W^{\perp} , by the same reasoning, by Step 7 of the algorithm, the state will still be orthogonal to the subspace \ket{\bm{\mathbf{p}}}\otimes M , where M represents the multiplicity space for the \{\bm{\mathbf{\lambda}}\}_{H} -isotypic component of the module. As such the the measurement is guaranteed (up to the precision of the circuits for the Schur transform) to reject the measurement result. As for the complexity of the algorithm, in step 1 , the preparation of the auxiliary partition and the permutation register states can be performed efficiently, since we can use the hook length formula to calculate the dimension of the Specht modules [\mu^{i}] and prepare a state of that size. The {r_{G}} inverse Schur transforms in Step 2 , on \bigotimes_{i=1}^{r_{G}}(\mathbbm{C}^{d_{i}})^{\otimes|\mu_{i}|} , have combined gate complexity \mathcal{O}(\sum_{i=1}^{r_{G}}|\mu_{i}|^{4}\polylog(|\mu^{i}|,d_{i})). In order to prove that the d_{i} is at most exponential in the input size (note that this is not needed if we assume d_{i} is given as part of the input), we write d_{i}=\sum_{j=1}^{t_{i}}{m_{i,j}}\dim(\{\bm{\mathbf{\nu}}(i,j)\}_{H}), and, as \dim\{\nu^{k}(i,j)\}_{n}\leq n^{|\nu^{k}(i,j)|} ), by expanding the definition of \{\bm{\mathbf{\nu}}(i,j)\}_{H} we get \displaystyle d_{i}=\sum_{j=1}^{t_{i}}m_{i,j}\prod_{k=1}^{{r_{H}}}\dim(\{\nu^{k}(i,j)\}_{n_{k}}) \displaystyle\leq \displaystyle\max_{j,k}\ t_{i}\ m_{i,j}(\dim(\{\nu^{k}(i,j)\}_{n_{k}}))^{r_{H}} \displaystyle\leq \displaystyle\max_{j,k}\ t_{i}\ m_{i,j}\ n_{k}^{|\nu^{k}(i,j)|{r_{H}}} \displaystyle\in \displaystyle\,\mathcal{O}(\max_{j,k}\ t_{i}\ m_{i,j}\exp(|\nu^{k}(i,j)|{r_{H}}\log n_{k}))) As a consequence the logarithm of this quantity is polynomial in the input size. In Step 3 we perform a polynomial amount of measurements, then, in Step 4 , for each of the outcomes we prepare the corresponding partition and symmetric-module register. Again this can be done efficiently. The Schur transforms in Steps 5 and 7 are transforms on H , as such they are polylogarithmic in the n_{k} and polynomial in the partitions size, and can therefore be efficiently implemented, as there is only a polynomial amount of them. Finally, still in Step 7 , we perform a polynomial amount of measurements. This shows that each step can be achieved in polynomial time. ∎ 6 Classical algorithms via characters The problems of computing Kostka, Littlewood-Richardson, Kronecker and plethysm coefficients is central in algebraic combinatorics. While most work is focused on finding positive formulas, efficient signed presentations have also been considered. It is clear from general principles that all of these coefficients are in \mathsf{GapP} . Kostka and Littlewood-Richardson coefficients are also equal to the number of integer points in polytopes of dimensions \mathcal{O}(\ell(\lambda)^{2}) , and for them Barvinok’s algorithms can be applied [ 3 ] , see Ref. [ 51 ] for an explicit analysis. The Kronecker coefficients have also been extensively studied, see Refs. [ 16 , 46 , 11 ] . The computation of plethysm coefficients was considered in some more special cases in Ref. [ 24 ] , where it was shown these are in \mathsf{GapP} . We will now investigate the general problem. Theorem 6.1 . Computing the dimension-independent branching multiplicities, 2.4 is in \mathsf{GapP} and can be done in time \mathcal{O}(N^{{r_{H}}dn}) , where N is the input size and d=\sum d_{i} , n=\sum n_{i} . Proof. We are given as input the data P_{i}=\sum_{j=1}^{t_{i}}m_{i,j}s_{\nu(i,j)}(\mathbf{x}^{1},\ldots,\mathbf{x}^{r_{H}}), which is a sum of products of Schur functions s_{\nu^{k}(i,j)}(\mathbf{x}^{k}) . The P_{i} ’s are multivariate polynomials in the {r_{H}} -many sets of variables, which we expand into sums of monomials and plug these monomials as variables in s_{\mu^{i}}[P_{i}] . A general algorithm would run through the following steps. 1. Determine the expansion of P_{i} into monomials as follows. We have that s_{\nu^{k}(i,j)}(\mathbf{x}^{k})=\sum_{\alpha^{k}(i,j)\vdash n_{k}}K_{\nu^{k}(i,j),\alpha^{k}(i,j)}m_{\alpha^{k}(i,j)}(\mathbf{x}^{k}), where m_{\alpha} are the monomial symmetric functions and so P_{i}=\sum_{j=1}^{t_{i}}\sum_{\alpha^{k}(i,j)\vdash n_{k}:k=1..h}m_{i,j}\prod K_{\nu^{k}(i,j),\alpha^{k}(i,j)}m_{\alpha(i,j)}(\mathbf{x}^{1},\ldots,\mathbf{x}^{r_{H}}), where m_{\alpha}(\mathbf{x}^{1},\ldots,\mathbf{x}^{r_{H}})=m_{\alpha^{1}}(\mathbf{x}^{1})m_{\alpha^{2}}(\mathbf{x}^{2})\cdots m_{\alpha^{k}}(\mathbf{x}^{r_{H}}) . The Kostka coefficients can be computed in \mathcal{O}(n_{k}^{n_{k}}) time (this upper bound can be significantly reduced depending on the partitions \nu involved). The exponential time algorithm can be more efficiently implemented via Barvinok’s lattice point count. We can thus compute the coefficients M_{\alpha(i,j)} in time \mathcal{O}(n^{{r_{H}}n}) , where n=n_{1}+\cdots is the total size: P_{i}=\sum_{j=1}^{t_{i}}\sum_{\alpha(i,j)}M_{\alpha(i,j)}m_{\alpha(i,j)}(\mathbf{x}^{1},\ldots,\mathbf{x}^{r_{H}}). The total number of partitions \alpha(i,j) to do this for is bounded above by (2^{n})^{n^{2}}=\mathcal{O}(2^{n^{3}}) 2. Compute the expansion of s_{\mu^{i}}[P_{i}] into monomials in each set of variables \mathbf{x}^{1},\mathbf{x}^{2},\ldots . This can be done by expanding s_{\mu^{i}}=\sum_{\beta^{i}\vdash d_{i}}K_{\mu^{i},\beta^{i}}m_{\beta^{i}} in conservatively bounded time \mathcal{O}(2^{d_{i}}d_{i}^{d_{i}}) . Note that if f=\sum_{\alpha^{i}\in R}x^{\alpha^{i}} , where R is a multiset of compositions, then m_{\beta}[f]=\sum_{\sigma}\sum_{i_{1}<\cdots0 is in \mathsf{QMA} (or in \mathsf{QMA}_{1} if the above can be implemented exactly). Proof. This follows by reduction to A.1 , with V_{\text{model}}\coloneqq\mathbbm{C}[G]\otimes V . By assumption, we can efficiently implement the embedding J\colon V\hookrightarrow V_{\text{model}} by following the first two steps of GPE, as discussed above. Strong Fourier sampling for the right regular action on V_{\text{model}} can be implemented by applying \QFT_{G} , measuring the label \mu of the summand V_{\mu}\otimes V_{\mu}^{*} in Eq. A.13 (as in the last two steps of GPE), but outputting \mu^{*} and subsequently measuring the register V_{\mu}^{*} . Thus the claim follows from A.1 (see Fig. 4 , right for the resulting circuit). ∎ We now comment on the approaches of Refs. [ 6 , 29 ] and the relation to A.6 . To capture the Kronecker coefficients g_{\lambda,\mu,\nu} , Ref. [ 6 ] uses weak Fourier sampling on three \mathbbm{C}[S_{n}] registers, accepting if and only if the outcomes are \lambda,\mu,\nu , respectively, which selects the subspace [\lambda]\otimes[\lambda^{*}]\otimes[\mu]\otimes[\mu^{*}]\otimes[\nu]\otimes[\nu^{*}] of V=\mathbbm{C}[S_{n}]\otimes\mathbbm{C}[S_{n}]\otimes\mathbbm{C}[S_{n}] , as is clear from Eq. A.13 . This is followed by ordinary GPE for the diagonal left regular action of S_{n} on V . The corresponding multiplicites are not the Kronecker coefficients, but rather their multiples \dim[\lambda]\dim[\mu]\dim[\nu]\,g_{\lambda,\mu,\nu} . Ref. [ 29 ] observed that a more refined procedure selects a single copy of [\lambda]\otimes[\mu]\otimes[\nu] in V , leading to a \#\mathsf{BQP} -algorithm for the exact Kronecker coefficients. To achieve this they use GPE for the Young subgroups S_{\lambda},S_{\mu},S_{\nu}\subseteq S_{n} . In their setting, this has the same effect as our measurement of the V_{\lambda}^{*} register in the proof of A.6 (see Fig. 3 , right). Example A.7 (Restriction coefficients) . Recall that the restriction coefficients r_{\lambda}^{\mu} are defined as the multiplicities of Specht modules in Weyl modules by embedding S_{n}\subset\GL(n) as permutation matrices. That is, they are defined as the multiplicity of the irreducible S_{n} -representation [\lambda] in \{\mu\}\!\!\downarrow^{\GL(n)}_{S_{n}} . We can first embed \{\mu\}_{\GL(n)}\hookrightarrow(\mathbbm{C}^{n})^{\otimes|\mu|}, by applying an inverse Schur transform (as in the case of plethysms). Since the controlled group action of S_{n} on \mathbbm{C}^{n} can be implemented efficiently, and there is an efficient QFT for the symmetric group S_{n} , we can apply A.6 to see that the restriction coefficients are in \#\mathsf{BQP} .