{"id":"2693501e-a039-44b5-b435-d50ac23749f4","arxiv_id":"2602.08441","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Plethysm coefficients and general branching multiplicities for products of general linear groups are computable in #BQP.","lead":"This paper proves that computing plethysm coefficients — multiplicities that arise when one symmetrized matrix representation is substituted into another — is possible with a quantum counting algorithm, placing them in the complexity class #BQP. It also places positivity of these coefficients in QMA and gives classical polynomial-time algorithms when certain parameters are fixed.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The #BQP algorithm assumes the computational/Fourier basis identification is free; no circuit is given for the isotypic measurement or the isometry from C^{d_i} to the GT basis, so the polynomial-time claim is incomplete.","rationale":"The paper's central claim is credible: the Schur-embedding strategy is sound in outline, and the use of the recent high-dimensional Schur transform [8] is appropriate for the exponentially large local dimensions. The weakest point is the unproven assumption that identifying the computational basis with the H-Fourier basis is free. This is load-bearing because it appears in every algorithm and the dimensions involved are exponential. The reader flagged exactly this in Section 5.2 Step 3; I agree, and note the same issue already affects the plethysm algorithm in Section 5.1. The gap is likely fixable by standard tableau-ranking algorithms, but the paper does not supply the required circuits or even state the ranking problem. Thus the correct verdict is CONDITIONAL: the main theorem is plausible and probably true, but the submitted proof is incomplete as written. No formal verification exists, so an explicit circuit construction or a precise appeal to existing tableau-ranking results is needed.","tokens_in":25925,"tokens_out":26556,"duration_ms":298337,"concrete_test":"Construct an explicit uniform circuit family for the isometry U_{n,ν}: C^{dim{ν}_n} → (C^n)^{⊗|ν|} that maps the computational basis of the defining module to the Gelfand-Tsetlin basis of {ν}_n in the encoding of [8]—e.g., implement a reversible ranking/unranking of semistandard Young tableaux of shape ν with entries ≤ n—and wire it into the plethysm algorithm between Steps 1 and 2 of Section 5.1 and into the isotypic measurement of Section 5.2 Step 3. Verify the total gate count is poly(|ν|, log n); if it is super-polynomial in log d_i, Theorems 1.2 and 1.3 are not established.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central algorithm (Section 5.2, and already the plethysm case in Section 5.1) relies on identifying the computational basis of each defining module C^{d_i} with the H-Fourier (Gelfand-Tsetlin) basis, per Definition 2.3. This identification is not merely notational: to measure the H-isotypic component in Step 3 without collapsing the within-component superposition, and then to feed the post-measurement state into the inverse Schur transforms of Steps 4–5, one needs an efficient coherent implementation of the isometry U_i: C^{d_i} → ⊕_j {ν(i,j)}_H ⊗ C^{m_ij}, expressed in the qubit encoding used by the Schur-transform circuit of [8]. Since d_i is exponential in the input size, a generic basis change would be too costly; the paper asserts 'we can freely operate full Fourier sampling' but gives no circuit-level construction and no proof that the required ranking/unranking maps (e.g., SSYT↔integer) are computable by poly(log d_i, |ν|)-size reversible circuits. The same gap affects the simpler plethysm algorithm: Step 1 identifies the computational basis of C^{dν} with the GT basis of {ν}_n, and Step 2 applies S^{-1} to each register, which presupposes an efficient isometry from C^{dν} into (C^n)^{⊗|ν|}. Without this, Theorem 5.1's complexity analysis ('we perform a polynomial amount of measurements') does not establish membership in #BQP.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proves that a broad class of representation-theoretic branching multiplicities for products of general linear groups, including all plethysm coefficients, is in #BQP, and consequently that positivity of these multiplicities lies in QMA. The quantum algorithm embeds the relevant Weyl module into a tensor product space via multiple layers of inverse Schur transforms, performs intermediate isotypic measurements, and concludes with strong Schur sampling; the dimension of the accepting subspace is shown to equal the desired multiplicity. The paper also gives a GapP containment for these multiplicities and fixed-parameter classical algorithms for plethysm coefficients when the number of rows of λ and the size of μ are fixed.","tokens_in":26364,"tokens_out":30546,"duration_ms":302205,"significance":"If correct, the central result resolves a notable open problem by showing that plethysm coefficients, whose membership in #P is unknown, are in #BQP. The approach unifies prior quantum algorithms for Kronecker and special plethysm coefficients and introduces a general framework (Appendix A) that captures both Schur-transform and generalized-phase-estimation methods. The paper also provides a GapP upper bound and classical fixed-parameter algorithms, which are of independent interest. The high-level construction is elegant, and the analysis of the accepted-subspace dimension is coherent. However, the proof of the #BQP claim currently omits a load-bearing circuit-level ingredient: the efficient implementation of the basis identification and the associated isometries.","major_comments":[{"comment":"The algorithm assumes that the computational basis of each defining module C^{d_i} can be identified with the H-Fourier basis, making the isotypic measurement a standard basis measurement. However, the Schur transform circuit [8] used in Steps 2, 4, and 5 operates in the standard basis of C^{d_i}. If the computational basis is instead identified with the GT basis of the H-decomposition, the paper must provide a polynomial-size circuit for the basis change U_i (or for the ranking/unranking maps between GT labels and standard indices). No such construction is given. This gap is load-bearing for Theorem 5.1: without it, the isotypic measurement on an exponentially large qudit and the subsequent inverse Schur embeddings of single H-irreducible registers are not justified. The same issue affects Section 5.1, where Step 1 identifies C^{d_ν} with the GT basis of {ν}_n.","section":"Section 5.2, Step 3; Definition 2.3"},{"comment":"After Step 1, the state is in ({ν}_n)^{⊗|μ|}, where each register is a qudit of dimension dim{ν}_n. Step 2 applies an inverse Schur transform to each register to embed it into (C^n)^{⊗|ν|}. However, the inverse Schur transform circuit from [8] is a unitary on the full tensor product space (C^n)^{⊗|ν|}; it does not act on a single qudit. The algorithm needs an isometry V: {ν}_n → (C^n)^{⊗|ν|}, which is not supplied. The sentence 'by Schur–Weyl duality' plus adding ancillas does not specify how V is implemented coherently. Without a polynomial-size circuit for V, the complexity analysis of Theorem 5.1 does not establish membership in #BQP.","section":"Section 5.1, Step 2"}],"minor_comments":[{"comment":"Typo: 'to each of the |λ| registers' should read 'to each of the |μ| registers', since Step 1 produces |μ| registers before the second embedding.","section":"Section 5.1, Step 2"},{"comment":"The notation 'λ⊢ d n' is nonstandard and ambiguous; it should be written as λ ∈ P_d(n) or λ ⊢_d n.","section":"Section 2.1"},{"comment":"Several spacing issues in the abstract, e.g., 'in#BQP' and 'inGapP' should be 'in #BQP' and 'in GapP'.","section":"Abstract"},{"comment":"In the complexity analysis, 'the Schur transforms in Steps 5 and 7 are transforms on H' should say 'on the representation spaces for H', since H is the group, not a Hilbert space.","section":"Theorem 5.1 proof"}],"recommendation":"major_revision","confidential_remarks":"The missing basis-change/isometry construction is the main obstacle. If the authors can supply a rigorous polynomial-size circuit for the isotypic measurement in the standard basis, or prove that the identification with the H-Fourier basis is efficiently implementable, the central #BQP claim would be substantiated. The high-level framework and the GapP/fixed-parameter results are valuable; I am not recommending rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper gives the first #BQP algorithm for general plethysm coefficients, and wraps it in a branching-multiplicity framework that also covers Kronecker, LR, and Kostka coefficients. That is a real step forward and the high-level idea is right: embed the G-module into a tensor power via inverse Schur transforms, then strong Schur sample. The recent high-dimensional Schur transform with polylog dependence on local dimension is the correct tool, and the dimension-counting argument in the completeness proof checks out.\n\nThe GapP result (Theorem 6.1) and the fixed-parameter classical algorithms (Theorem 6.2) are useful complements, and the paper is honest about what depends on what. Lemma 2.2 correctly reduces the choice of homomorphism to the decomposition data of the defining modules.\n\nNow the soft spot. The algorithm asserts, in Definition 2.3 and Step 2 of Section 5.1 / Step 3 of Section 5.2, that the computational basis of each defining module C^{d_i} is the Gelfand-Tsetlin basis, and that we can therefore 'freely operate full Fourier sampling' and apply inverse Schur transforms. That is not a free operation. The inverse Schur transform circuit from [8] acts on a tensor power (C^n)^{⊗|ν|}, not on a single compact qudit of dimension d_i. To carry out the embedding, you need an explicit, efficient isometry from the compact qudit basis to the tensor product space (with ancillas for the symmetric-group labels). Since d_i is exponential, this is not automatic. The paper does not construct this isometry or prove it has a poly-size circuit. This is a genuine gap in the proof of polynomial-time implementability, and it affects both the plethysm and general branching algorithms. I suspect it is repairable—there probably are efficient reversible circuits for converting GT patterns to words—but the authors need to show it.\n\nThe GapP section has a minor hand-wave about truncating to finitely many variables, but that is a standard fix.\n\nOverall: this is a serious paper with a real but identifiable gap. The main theorem is likely true; the paper just does not yet fully support the complexity claim. It deserves a rigorous referee who can pin down the isometry construction. I would send it to review.","headline":"General plethysm in #BQP is a real advance, but the algorithm as written assumes an unconstructed basis-change isometry.","tokens_in":26798,"tokens_out":9129,"would_cite":true,"duration_ms":99346,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05E05","05E10","20C30","68Q12"],"pacs":["03.67.Ac"],"model":"deepseek-v4-flash","headline":"This paper proves that every plethysm coefficient is the count of accepted witnesses of a polynomial-size quantum circuit — so plethysm is in #BQP and deciding positivity is in QMA.","keywords":["plethysm coefficients","#BQP","QMA","branching multiplicities","Schur transform","Schur-Weyl duality","Kronecker coefficients","representation-theoretic multiplicities"],"falsifier":"The claim is settled by whether the intermediate isotypic measurement can be implemented by a circuit of size polynomial in log d_i: exhibiting explicit such circuits for the exponentially large local dimensions would confirm the theorem, whereas a superpolynomial lower bound on that basis change for any family of instances would refute the claimed polynomial runtime.","tokens_in":25865,"feed_emoji":"⚛️","tokens_out":5997,"duration_ms":61567,"temperature":0.7,"pith_summary":"The paper's central claim is that a broad class of representation-theoretic multiplicities — branching multiplicities for products of general linear groups, including plethysm, Kronecker, Littlewood-Richardson, and Kostka coefficients — can be computed by quantum counting circuits, placing them in the class #BQP. For the plethysm coefficient a^λ_{μν}, the paper exhibits a quantum verifier whose acceptance subspace has dimension exactly that coefficient, so telling whether the coefficient is positive lands in QMA. A sympathetic reader should care because these numbers have resisted combinatorial interpretations for decades; the result shows that quantum computers could certify them even if no positive formula exists. The proof works by embedding the relevant representation into a tensor power using inverse Schur transforms and then performing strong Fourier sampling. If correct, it unifies previously known quantum-complexity results for Kronecker and special plethysm coefficients into one framework.","feed_headline":"Quantum circuit counts every plethysm coefficient","feed_subtitle":"Even without combinatorial formulas, quantum verification certifies these long-studied multiplicities.","key_machinery":"The load-bearing object is the branching multiplicity for products of general linear groups: the multiplicity of an irreducible H-module in the restriction of an irreducible G-module along a succinctly specified homomorphism, specified by how the defining modules of G decompose over H. The argument is carried by the quantum Schur transform, the unitary change of basis from the computational basis of (C^d)^{⊗N} to the Schur basis indexed by a partition, a basis vector of the Weyl module, and a basis vector of the Specht module. The key mechanism is a two-step recipe: embed the representation to be decomposed into a model representation (a tensor power) via inverse Schur transforms, then stron","core_discovery":"The central claim is constructive: the plethysm coefficient a^λ_{μν} equals the dimension of the accepting subspace of a polynomial-size quantum circuit, so computing plethysm coefficients is in #BQP. The circuit embeds the restricted module into (C^n)^{⊗|ν||μ|} via two layers of inverse Schur transforms, applies a Schur transform to the whole space, and accepts on measurement outcome (λ, p0). Every operation is equivariant, so the accepted subspace is exactly the λ-isotypic component. The same construction, with an intermediate isotypic measurement for defining modules that reduce nontrivially over H, handles arbitrary branching multiplicities for products of general linear groups; positivi","pith_inferences":["Editorial extension: the embedding-plus-strong-Fourier-sampling recipe suggests a template for other multiplicity problems — such as fusion coefficients of compact Lie groups or multiplicities in tensor categories — whenever a model representation with efficient strong Fourier sampling exists.","Editorial extension: for the fermionic N-representability case (μ=(m), ν=(1^d)), a quantum verifier for the plethysm coefficient offers a route toward quantum-certifiable consistency of fermionic reduced density matrices.","Editorial extension: if the high-dimensional Schur transform can later be implemented exactly, the same framework would likely upgrade the QMA statement to a perfect-completeness version, since the circuit structure itself is a projective measurement."],"forward_implications":["Computing plethysm coefficients is in #BQP: there is a polynomial-size quantum circuit whose accepted-witness subspace has dimension exactly a^λ_{μν}.","Deciding whether a plethysm coefficient is positive is in QMA, so a quantum verifier can certify nonzero coefficients.","The same holds for the general branching problem for products of general linear groups, subsuming Kronecker, Littlewood-Richardson, and Kostka coefficients.","Restriction coefficients of the symmetric group inside GL(n) are in #BQP as an immediate corollary.","If plethysm later turns out not to be in #P, the theorem would imply a separation between #P and #BQP, sharpening the stakes of the open combinatorial-interpretation problem."],"fun_headline_variants":["Quantum circuits count all plethysm coefficients","Plethysm coefficients now provably in #BQP","Counting plethysm: quantum circuit does it","Plethysm in #BQP, no formulas needed","Plethysm coefficients join #BQP"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The polynomial runtime rests on the assumption that the isotypic measurement in the general algorithm — which identifies the computational basis of each exponentially large defining module with the Fourier basis for H — can be performed efficiently; the paper asserts this basis identification without giving a circuit-level construction, and if implementing it costs more than poly(log d_i) the algorithm is no longer polynomial time.","fun_headline_variants_meta":{"raw":{"variants":["Quantum circuits count all plethysm coefficients","Plethysm coefficients now provably in #BQP","Counting plethysm: quantum circuit does it","Plethysm in #BQP, no formulas needed","Plethysm coefficients join #BQP"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000482,"raw_usage":{"total_tokens":2220,"prompt_tokens":749,"completion_tokens":1471,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":493,"completion_tokens_details":{"reasoning_tokens":1409}},"tokens_in":493,"tokens_out":1471,"duration_ms":11300,"temperature":1.0,"reasoning_tokens":1409,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-03T03:17:07.417382+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"The claim is settled by whether the intermediate isotypic measurement can be implemented by a circuit of size polynomial in log d_i: exhibiting explicit such circuits for the exponentially large local dimensions would confirm the theorem, whereas a superpolynomial lower bound on that basis change for any family of instances would refute the claimed polynomial runtime.","supporting_citations":[],"review_version":1}