{"id":"0205707f-5d83-4117-98a2-4e70416f3301","arxiv_id":"2607.08841","paper_version":2,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":6.5,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Partially-commutative monoids yield native, compact SDP relaxations for polynomial optimization under arbitrary pairwise commutation relations, unifying and tightening NPA-style hierarchies.","lead":"The paper defines partially-commutative polynomial optimization (PCPO), an SDP hierarchy framework that natively encodes selective commutation relations via partially-commutative monoids. This produces smaller moment matrices for quantum-information problems such as multipartite Bell scenarios without extra linear constraints.","discovery_kind":"new_method","skeptic_critique":{"model":"grok-4.5","headline":"No significant objection identified","rationale":"The manuscript is a methods paper whose strongest claim is algebraic and constructive rather than empirical. All steps from free-algebra NCPO through binomial quotients, PC monoids, circuit/wire representations, and the hybrid SDP construction are proved; the only practical caveat (infinite Gröbner bases for non-transitive graphs) is handled by the O(r^{2}) lex algorithm and linear-time wire operations that the paper supplies. The companion numerical paper is deferred, but that does not affect the correctness of the hierarchy itself. The reader’s weakest assumption correctly flags the computational practicality issue without elevating it to a correctness risk; I therefore leave the ACCEPT / high-confidence verdict unchanged.","tokens_in":43464,"tokens_out":458,"duration_ms":5373,"concrete_test":"Independently re-derive the factorization (46) and the inclusion JB \\subseteq IR igcap PB∗B for a small non-transitive example (e.g., the pentagon of Lemma 10) using only the wire-tuple product and involution of §4.4–4.5; confirm that the resulting moment matrix is a principal submatrix of the free-algebra matrix and that the SDP value is at least as large.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim is that PC monoid representations (especially wire tuples) yield SDP relaxations that absorb partial commutations into the monomial basis, are at least as tight as free-algebra formulations with explicit linear constraints, and are typically more compact. The algebraic development (quotient by binomial relations, isomorphism to the monoid algebra, hybrid treatment of remaining equalities, circuit/wire operations, and the careful non-monoid treatment of cyclic classes for TPCPO) is internally consistent and fully proved. The reader’s weakest assumption—tractability of the chosen representations for non-transitively-orientable graphs—is a genuine practical limitation, but it is already stated by the paper (Lemmas 9–10, Algorithms 2–5) and does not undermine correctness of the hierarchy or the tightness claim. No hidden inconsistency or unproved step appears in the load-bearing argument.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.5","summary":"The paper introduces partially-commutative polynomial optimization (PCPO) and its tracial variant (TPCPO) as a common framework that interpolates between commutative and non-commutative polynomial optimization by allowing arbitrary pairwise commutation relations. It develops the algebraic foundation via partially-commutative monoids (trace monoids), proves that the free-algebra quotient by binomial commutation relations is the monoid algebra, and constructs SDP hierarchies in which those relations are absorbed into the monomial indexing rather than imposed as linear constraints. Concrete representations (lexicographic normal forms, left-justified circuits, wire/clique projections) and algorithms for multiplication, involution, and cyclic equivalence are given, together with a hybrid treatment of remaining polynomial equalities. The resulting relaxations are shown to be at least as tight as the free-algebra formulations and typically more compact.","tokens_in":43687,"tokens_out":740,"duration_ms":6422,"significance":"The work fills a genuine gap between the fully commutative Lasserre hierarchy and the fully non-commutative NPA hierarchy. Partial commutations arise systematically in multipartite quantum scenarios (Bell, routed Bell, many-body systems), so a native monoid-based treatment is of clear practical value. The algebraic development is careful and complete: the monoid-algebra isomorphism, the Gröbner-basis description for classwise-lex orders, the bijection between left-justified circuits and pc-monomials, the projection theorem, and the non-monoid treatment of cyclic classes for TPCPO are all proved. The companion open-source implementation (PCPOP.jl) further strengthens the contribution by making the constructions immediately usable. The paper is therefore a solid methodological advance for the quantum-information and non-commutative-optimization communities.","major_comments":[],"minor_comments":[{"comment":"Several typographical slips appear throughout (e.g., “polyomials”, “litterature”, “leftrg⊸tlne” artefacts in reduction diagrams, “corresponing”). A careful copy-edit pass would improve readability.","section":null},{"comment":"In §3.2 the discussion of naive substitution pitfalls is excellent, but a short forward pointer to the monoid-algebra isomorphism of §3.5.2 would help the reader see immediately how the later theory resolves the ambiguities.","section":null},{"comment":"Lemma 10 asserts that the pentagon is the smallest graph without a transitive orientation; a one-sentence reference or elementary verification would make the claim self-contained.","section":null},{"comment":"The wire-representation implementation sketch in §4.5 is clear, yet a brief remark on how the degree of a multi-wire letter is cached (or recomputed) would remove a small ambiguity for implementers.","section":null},{"comment":"In the TPCPO section the distinction between the vector-space quotient K[W^cyc_G] and a monoid algebra is correctly emphasised; a single sentence reminding the reader that moment-matrix indices remain ordinary pc-monomials (while entries are cyclic classes) would further reduce the risk of mis-implementation.","section":null}],"recommendation":"accept","confidential_remarks":"The manuscript is long and somewhat encyclopaedic, but the material is well organised and the algebraic claims are load-bearing rather than ornamental. I see no reason to request a major condensation; the companion implementation paper already separates the numerical benchmarks. Fit for a methods-oriented quantum-information or mathematical-programming venue is excellent."},"author_rebuttal":null,"desk_editor":{"model":"grok-4.5","letter":"This is the paper that finally puts partial commutations inside the NPA hierarchy the right way. Instead of padding the free algebra with linear constraints for every commuting pair, they work directly in the monoid algebra of a partially-commutative monoid (trace monoid). The resulting SDP is at least as tight and usually much smaller, because the commutation relations are already baked into the indexing of the moments.\n\nWhat is new is not the monoids themselves (Cartier–Foata, Mazurkiewicz, Diekert are classical). What is new is the systematic placement of those monoids inside the NPA/Lasserre framework, the explicit warning that naïve substitution rules (still used by packages such as ncpol2sdpa) can miss equivalences or produce ambiguous reductions, and the concrete, implementable representations—lex normal forms, left-justified circuits, and especially wire/clique projections—together with the algorithms that make them usable. The hybrid quotient construction (commutation relations absorbed, remaining equalities kept as linear constraints) and the careful non-monoid treatment of cyclic classes for the tracial case are both done cleanly. All the load-bearing algebraic claims are proved: the isomorphism to the monoid algebra, the Gröbner basis for classwise-lex orders, the projection theorem, the bijection with left-justified circuits, and the cyclic-equivalence criterion.\n\nSoft spots are minor and already flagged by the authors. For graphs without a transitive orientation the Gröbner basis is infinite, so one must rely on the O(r^{2}) greedy lex algorithm or the linear-time wire operations; that is a practical limitation, not a correctness hole. Numerical benchmarks are deferred to the companion package paper, which is fine for a methods manuscript. Convergence still rests on the usual archimedeanity assumptions.\n\nThis is for anyone who builds or uses NPA-type hierarchies for multipartite Bell scenarios, device-independent protocols, or any quantum problem with overlapping supports. The citation pattern is appropriate and the math is solid. I would send it to referees without hesitation; it deserves a place in the literature and I expect to cite the framework when I next need a compact multipartite relaxation.","headline":"Solid methods paper that correctly embeds partial commutations into the NPA monomial basis via PC monoids; algebra is clean and the software gap it fills is real.","tokens_in":44285,"tokens_out":544,"would_cite":true,"duration_ms":7343,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.5","headline":"Partial commutations can be built into the monomials of an SDP hierarchy, yielding smaller, tighter quantum-information relaxations.","keywords":["partially commutative monoids","noncommutative polynomial optimization","SDP hierarchies","quantum correlations","moment matrices","trace monoids","Bell scenarios"],"falsifier":"For a fixed multipartite Bell or routed-Bell instance, build the degree-d PCPO moment matrix via wire tuples and the ordinary free NPA matrix of the same degree with explicit commutation constraints; if the PCPO matrix is not strictly smaller or yields a strictly weaker bound, the claimed compactness/tightness fails.","tokens_in":44381,"feed_emoji":"⚛️","tokens_out":811,"duration_ms":9322,"temperature":0.7,"pith_summary":"Many quantum-information problems involve operators that commute with some variables but not others, not the pure extremes of fully commutative or fully free variables. Standard non-commutative SDP hierarchies can encode those relations only as extra linear constraints, which bloats the moment matrices. This paper defines partially-commutative polynomial optimization (PCPO) and shows that the correct algebraic object is a partially-commutative monoid. By indexing moments with canonical representatives of that monoid (lexicographic words, left-justified circuits, or wire tuples), every allowed commutation is already absorbed into the basis itself. The resulting SDPs are smaller, free of redundant equality constraints, and at least as tight as the unconstrained free-algebra formulations. The same construction extends to the tracial setting used for many multipartite correlation problems.","feed_headline":"Partial commutations shrink quantum SDP hierarchies","feed_subtitle":"Monomials that already know who commutes with whom replace extra linear constraints","key_machinery":"The partially-commutative monoid (trace monoid) WG associated with a commutation graph G, together with its concrete representations (especially the injective wire/clique-projection map) that turn multiplication, involution and equality testing into operations on tuples of ordinary words.","core_discovery":"Partial commutation relations generate a partially-commutative monoid; representing the monoid algebra by any of its standard normal forms (lex words, left-justified circuits, or clique-wire projections) produces SDP moment relaxations in which those relations are native to the monomial indexing rather than imposed afterwards as linear constraints, and the resulting programs dominate ordinary free-algebra truncations.","pith_inferences":["Wire-based indexing should combine cleanly with existing symmetry and sparsity reductions already used for multipartite NPA hierarchies.","The same monoid language could absorb other common quantum equalities (projectors, unitaries) once suitable Gröbner or normal-form tools exist inside the PC monoid.","For graphs that admit transitive orientations the Gröbner basis collapses to the original degree-two relations, giving an especially cheap implementation path."],"forward_implications":["Bell, multipartite and routed-Bell hierarchies can drop all inter-party commutation equalities from the SDP constraint list.","Moment-matrix size grows only with the number of distinct partially-commutative monomials, not with free words.","The same monoid indexing extends immediately to tracial (cyclic) PCPO used for entanglement and quantum-graph bounds.","Hybrid formulations remain available: quotient by partial commutations while retaining other polynomial equalities as ordinary linear constraints."],"fun_headline_variants":["Partially-commutative monoids shrink SDP hierarchies natively","Monoid normal forms embed partial commutations in SDP moments","Partial commutes yield compact free-algebra SDP relaxations","Native monoid monomials replace extra SDP linear constraints","Partially-commutative monoids compactify quantum opt SDPs"],"cache_read_input_tokens":32896,"weakest_assumption_plain":"The chosen monoid representation stays computationally cheap for the commutation graphs that actually arise; for some graphs the Gröbner basis is infinite, so the method leans on the practicality of the greedy lex or linear-time wire algorithms.","fun_headline_variants_meta":{"raw":{"variants":["Partially-commutative monoids shrink SDP hierarchies natively","Monoid normal forms embed partial commutations in SDP moments","Partial commutes yield compact free-algebra SDP relaxations","Native monoid monomials replace extra SDP linear constraints","Partially-commutative monoids compactify quantum opt SDPs"]},"model":"grok-4.5","effort":"low","cost_usd":0.007764,"raw_usage":{"total_tokens":1842,"prompt_tokens":726,"num_sources_used":0,"completion_tokens":82,"cost_in_usd_ticks":77640000,"prompt_tokens_details":{"text_tokens":726,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":1034,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":726,"tokens_out":82,"duration_ms":7404,"temperature":1.0,"reasoning_tokens":1034,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-14T15:27:34.030725+00:00","model_set":{"reader":"grok-4.5"},"falsifier":"For a fixed multipartite Bell or routed-Bell instance, build the degree-d PCPO moment matrix via wire tuples and the ordinary free NPA matrix of the same degree with explicit commutation constraints; if the PCPO matrix is not strictly smaller or yields a strictly weaker bound, the claimed compactness/tightness fails.","supporting_citations":[],"review_version":2}