Pith. sign in

REVIEW 5 minor 45 references

Partial commutations can be built into the monomials of an SDP hierarchy, yielding smaller, tighter quantum-information relaxations.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review

2026-07-14 15:27 UTC pith:YDJT2ECY

load-bearing objection 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.

arxiv 2607.08841 v2 pith:YDJT2ECY submitted 2026-07-09 quant-ph math.OC

Partially-Commutative Polynomial Optimization

Abhishek Mishra , Mois\'es Bermejo Mor\'an , Stefano Pironio This is my paper
classification quant-ph math.OC
keywords partially commutative monoidsnoncommutative polynomial optimizationSDP hierarchiesquantum correlationsmoment matricestrace monoidsBell scenarios
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

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.

Core claim

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.

What carries the argument

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.

Load-bearing premise

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.

What would settle it

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.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

Share X Bluesky LinkedIn Reddit HN

If this is right

  • 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.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

0 major / 5 minor

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.

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.

minor comments (5)
  1. Several typographical slips appear throughout (e.g., “polyomials”, “litterature”, “leftrg⊸tlne” artefacts in reduction diagrams, “corresponing”). A careful copy-edit pass would improve readability.
  2. 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.
  3. 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.
  4. 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.
  5. 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.

Circularity Check

0 steps flagged

No circularity: pure algebraic construction of quotient SDP hierarchies from PC monoids; no fits, no load-bearing self-citation chains, no definitional predictions.

full rationale

The paper defines PCPO as NCPO whose equality set contains the binomial commutation relations RG of a graph G, then constructs the hybrid quotient SDP by working in the monoid algebra K[WG] (isomorphic to P/⟨RG⟩ by the standard binomial argument of §3.5.2) while retaining residual equalities as linear constraints. All subsequent claims—tighter or equal relaxations (via JB ⊆ IR ∩ PB*B), compactness of moment matrices indexed by pc-monomials, correctness of lex/circuit/wire normal forms (Algorithms 2–5, Propositions 8, 14, 15, 20), and the careful non-monoid treatment of cyclic classes for TPCPO—are proved by direct algebraic or graph-theoretic arguments inside the paper. Self-citations are only to the classical NPA hierarchy (PNA10 etc.) and to a companion implementation note; neither is used to force uniqueness or to smuggle an ansatz that would make the present claims tautological. There are no fitted parameters, no empirical predictions, and no renaming of known numerical patterns. The derivation is therefore self-contained and non-circular.

Axiom & Free-Parameter Ledger

0 free parameters · 4 axioms · 2 invented entities

The central construction rests on standard free-algebra and monoid theory plus the usual operator-representation semantics of NPA. No free parameters are fitted. The only ‘invented’ objects are the named framework PCPO itself and the circuit/wire presentations, both of which are re-packagings of classical combinatorial objects for the SDP setting.

axioms (4)
  • standard math The free *-algebra and its operator representations via *-homomorphisms into B(H) (Section 2.2).
    Standard non-commutative polynomial optimization setup used by NPA.
  • domain assumption Archimedeanity (or equivalent Putinar-type conditions) guaranteeing convergence of the moment hierarchy (invoked for both free and quotient formulations).
    Inherited from NPA/Lasserre; not re-proved.
  • domain assumption The commutation graph is compatible with the involution: (x,y) edge iff (x*,y*) edge (Section 4).
    Needed so that the involution descends to the monoid; natural for Hermitian operators but stated as an assumption.
  • standard math Existence of an edge-clique cover of the non-commutation graph that is closed under involution (Subsection 4.3.2).
    Always possible; used only to define the wire representation.
invented entities (2)
  • Partially-commutative polynomial optimization (PCPO) and its tracial variant TPCPO independent evidence
    purpose: Name the intermediate regime between fully commutative and fully non-commutative polynomial optimization and the associated SDP hierarchies.
    The framework is new as a named optimization problem class, even though it is the natural hybrid of existing CPO and NCPO.
  • Left-justified circuit representation of pc-monomials independent evidence
    purpose: Provide a QI-friendly data structure for multiplication, involution and visualization of partially-commutative words.
    Reformulation of classical Foata/heap representations; independent evidence is the classical literature plus the released package.

reviewed 2026-07-14 · how reviews work

0 comments
Cite this review

Pith. "Pith review of Partially-Commutative Polynomial Optimization." pith.science (2026). https://pith.science/paper/YDJT2ECY

@misc{pith2026260708841,
  author       = {Pith},
  title        = {Pith review of: Partially-Commutative Polynomial Optimization},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/YDJT2ECY}},
  note         = {Machine review of arXiv:2607.08841}
}
Share X Bluesky LinkedIn Reddit HN
read the original abstract

Semidefinite programming hierarchies for commutative and non-commutative polynomial optimization represent a powerful computational tool with many applications in quantum information. In such applications, a given variable is typically not either commuting or non-commuting with all other variables, but instead commutes with some variables and does not commute with others, i.e., the variables satisfy some partial commutation relations. While such partial commutation relations can always be incorporated in a fully non-commutative setting through suitable linear constraints in the semidefinite programming relaxations, exploiting their algebraic properties from the onset can result in more compact relaxations. This leads us to introduce partially-commutative polynomial optimization, a framework that encompasses commutative and non-commutative polynomial optimization, allowing for arbitrary commutation relations among the variables. We point out that the underlying algebraic structure is that of a partially-commutative monoid. We present and review several key aspects of such monoids and show how they can be used to build SDP relaxations for partially-commutative polynomial optimization problems in which the partial commutations are natively implemented in the monomial structure, without the need of additional linear constraints.

Review history (2 revisions) →

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

45 extracted references

  1. [1]

    The tracial moment problem and trace-optimization of polynomials

    Sabine Burgdorf, Kristijan Cafuta, Igor Klep, and Janez Povh. The tracial moment problem and trace-optimization of polynomials. Mathematical Programming , 137(1):557--578, 2013

    2013

  2. [2]

    Bell nonlocality

    Nicolas Brunner, Daniel Cavalcanti, Stefano Pironio, Valerio Scarani, and Stephanie Wehner. Bell nonlocality. Reviews of Modern Physics , 86(2):419, 2014

    2014

  3. [3]

    Device-independent lower bounds on the conditional von N eumann entropy

    Peter Brown, Hamza Fawzi, and Omar Fawzi. Device-independent lower bounds on the conditional von N eumann entropy. Quantum , 8:1445, 2024

    2024

  4. [4]

    Sum-of-squares decompositions for a family of C lauser- H orne- S himony- H olt-like inequalities and their application to self-testing

    C \'e dric Bamps and Stefano Pironio. Sum-of-squares decompositions for a family of C lauser- H orne- S himony- H olt-like inequalities and their application to self-testing. Physical Review A , 91(5):052111, 2015

    2015

  5. [5]

    Gr\"obner- S hirshov bases for C oxeter groups

    Leonid Arkadievich Bokut and Li-Sheng Shiao. Gr\"obner- S hirshov bases for C oxeter groups. Communications in Algebra , 29(9):4305--4319, 2001

    2001

  6. [6]

    Applications probabilistes , volume 85 of Lecture Notes on Mathematics

    Pierre Cartier and Dominique Foata. Applications probabilistes , volume 85 of Lecture Notes on Mathematics . Springer, 1969

    1969

  7. [7]

    Toric heaps, cyclic reducibility, and conjugacy in C oxeter groups

    Shih-Wei Chao and Matthew Macauley. Toric heaps, cyclic reducibility, and conjugacy in C oxeter groups. Open Journal of Discrete Mathematics , 9(4):110--143, 2019

    2019

  8. [8]

    The quantum moment problem and bounds on entangled multi-prover games

    Andrew C Doherty, Yeong-Cherng Liang, Ben Toner, and Stephanie Wehner. The quantum moment problem and bounds on entangled multi-prover games. In 2008 23rd Annual IEEE Conference on Computational Complexity , pages 199--210. IEEE, 2008

    2008

  9. [9]

    Partial commutation and traces

    Volker Diekert and Yves M \'e tivier. Partial commutation and traces. In Handbook of Formal Languages: Volume 3 Beyond Words , pages 457--533. Springer, 1997

    1997

  10. [10]

    Toric partial orders

    Mike Develin, Matthew Macauley, and Victor Reiner. Toric partial orders. Transactions of the American Mathematical Society , 368(4):2263--2287, 2016

    2016

  11. [11]

    The book of traces

    Volker Diekert and Grzegorz Rozenberg. The book of traces . World scientific, 1995

    1995

  12. [12]

    On some equations in free partially commutative monoids

    Christine Duboc. On some equations in free partially commutative monoids. Theoretical Computer Science , 46:159--174, 1986

    1986

  13. [13]

    Bounds on entanglement dimensions and quantum graph parameters via noncommutative polynomial optimization

    Sander Gribling, David de Laat, and Monique Laurent. Bounds on entanglement dimensions and quantum graph parameters via noncommutative polynomial optimization. Mathematical Programming , 170(1):5--42, 2018

    2018

  14. [14]

    Connes' embedding problem and T sirelson's problem

    Marius Junge, Miguel Navascu \'e s, Carlos Palazuelos, David P \'e rez-Garc \'i a, Volkher B Scholz, and Reinhard F Werner. Connes' embedding problem and T sirelson's problem. Journal of Mathematical Physics , 52(1), 2011

    2011

  15. [15]

    MIP ^*= RE

    Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, and Henry Yuen. MIP ^*= RE . Communications of the ACM , 64(11):131--138, 2021

    2021

  16. [16]

    Simple word problems in universal algebras

    Donald E Knuth and Peter B Bendix. Simple word problems in universal algebras. In Computational Problems in Abstract Algebra , pages 263--297. Elsevier, 1970

    1970

  17. [17]

    Optimization over trace polynomials

    Igor Klep, Victor Magron, and Jurij Vol c i c . Optimization over trace polynomials. In Annales Henri Poincar \'e , volume 23, pages 67--100. Springer, 2022

    2022

  18. [18]

    State polynomials: positivity, optimization and nonlinear B ell inequalities

    Igor Klep, Victor Magron, Jurij Vol c i c , and Jie Wang. State polynomials: positivity, optimization and nonlinear B ell inequalities. Mathematical Programming , pages 1--47, 2023

    2023

  19. [19]

    Constrained trace-optimization of polynomials in freely noncommuting variables

    Igor Klep and Janez Povh. Constrained trace-optimization of polynomials in freely noncommuting variables. Journal of Global Optimization , 64(2):325--348, 2016

    2016

  20. [20]

    Global optimization with polynomials and the problem of moments

    Jean B Lasserre. Global optimization with polynomials and the problem of moments. SIAM Journal on Optimization , 11(3):796--817, 2001

    2001

  21. [21]

    Sums of squares, moment matrices and optimization over polynomials

    Monique Laurent. Sums of squares, moment matrices and optimization over polynomials. In Emerging Applications of Algebraic Geometry , pages 157--270. Springer, 2008

    2008

  22. [22]

    Algebraic Combinatorics on Words , volume 90 of Encyclopedia of Mathematics and its Applications

    Monsieur Lothaire. Algebraic Combinatorics on Words , volume 90 of Encyclopedia of Mathematics and its Applications . Cambridge University Press, 2002

    2002

  23. [23]

    Certifying long-range quantum correlations through routed B ell tests

    Edwin Peter Lobo, Jef Pauwels, and Stefano Pironio. Certifying long-range quantum correlations through routed B ell tests. Quantum , 8:1332, May 2024

    2024

  24. [24]

    Efficient solution of some problems in free partially commutative monoids

    Hai-Ning Liu, Celia Wrathall, and Kenneth Zeger. Efficient solution of some problems in free partially commutative monoids. Information and Computation , 89(2):180--198, 1990

    1990

  25. [25]

    Concurrent program schemes and their interpretations

    Antoni Mazurkiewicz. Concurrent program schemes and their interpretations. DAIMI Report Series , (78), 1977

    1977

  26. [26]

    PCPOP.jl , 2026

    Mois\'es Bermejo Mor\'an and Abhishek Mishra. PCPOP.jl , 2026. Available at https://github.com/abh1mishra/PCPOP.jl

    2026

  27. [27]

    PCPOP .jl: A julia package for partially commutative polynomial optimization, 2026

    Moisés Bermejo Morán and Abhishek Mishra. PCPOP .jl: A julia package for partially commutative polynomial optimization, 2026

    2026

  28. [28]

    An introduction to commutative and noncommutative G r \"o bner bases

    Teo Mora. An introduction to commutative and noncommutative G r \"o bner bases. Theoretical Computer Science , 134(1):131--173, 1994

    1994

  29. [29]

    Bounding the set of quantum correlations

    Miguel Navascu \'e s, Stefano Pironio, and Antonio Ac \' n. Bounding the set of quantum correlations. Physical Review Letters , 98(1):010401, 2007

    2007

  30. [30]

    A convergent hierarchy of semidefinite programs characterizing the set of quantum correlations

    Miguel Navascu \'e s, Stefano Pironio, and Antonio Ac \' n. A convergent hierarchy of semidefinite programs characterizing the set of quantum correlations. New Journal of Physics , 10(7):073013, 2008

    2008

  31. [31]

    Bounding the set of finite dimensional quantum correlations

    Miguel Navascu \'e s and Tam \'a s V \'e rtesi. Bounding the set of finite dimensional quantum correlations. Physical Review Letters , 115(2):020501, 2015

    2015

  32. [32]

    Semidefinite programming relaxations for semialgebraic problems

    Pablo A Parrilo. Semidefinite programming relaxations for semialgebraic problems. Mathematical Programming , 96:293--320, 2003

    2003

  33. [33]

    Exploiting algebraic structure in sum of squares programs

    Pablo A Parrilo. Exploiting algebraic structure in sum of squares programs. In Positive Polynomials in Control , pages 181--194. Springer, 2005

    2005

  34. [34]

    Convergent relaxations of polynomial optimization problems with noncommuting variables

    Stefano Pironio, Miguel Navascu \'e s, and Antonio Ac \'i n. Convergent relaxations of polynomial optimization problems with noncommuting variables. SIAM Journal on Optimization , 20(5):2157--2180, 2010

    2010

  35. [35]

    On reorienting graphs by pushing down maximal vertices

    Oliver Pretzel. On reorienting graphs by pushing down maximal vertices. Order , 3(2):135--153, 1986

    1986

  36. [36]

    Prepare-and-measure scenarios with photon-number constraints

    Carles Roch i Carceller, Jef Pauwels, Stefano Pironio, and Armin Tavakoli. Prepare-and-measure scenarios with photon-number constraints. Physical Review Letters , 135(14):140802, 2025

    2025

  37. [37]

    Symdpoly: symmetry-adapted moment relaxations for noncommutative polynomial optimization, 2018

    Denis Rosset. Symdpoly: symmetry-adapted moment relaxations for noncommutative polynomial optimization, 2018

    2018

  38. [38]

    Handbook of Formal Languages: Beyonds words , volume 3

    Grzegorz Rozenberg. Handbook of Formal Languages: Beyonds words , volume 3. Springer Science & Business Media, 1997

    1997

  39. [39]

    Semidefinite programming relaxations for quantum correlations

    Armin Tavakoli, Alejandro Pozas-Kerstjens, Peter Brown, and Mateus Ara \'u jo. Semidefinite programming relaxations for quantum correlations. Reviews of Modern Physics , 96(4):045006, 2024

    2024

  40. [40]

    Informationally restricted correlations: a general framework for classical and quantum systems

    Armin Tavakoli, Emmanuel Zambrini Cruzeiro, Erik Woodhead, and Stefano Pironio. Informationally restricted correlations: a general framework for classical and quantum systems. Quantum , 6:620, January 2022

    2022

  41. [41]

    Colloque de combinatoire \'e num \'e rative

    G \'e rard Xavier Viennot. Heaps of pieces I : Basic definitions and combinatorial lemmas. In Combinatoire \'e num \'e rative: Proceedings of the “Colloque de combinatoire \'e num \'e rative”, held at Universit \'e du Qu \'e bec \`a Montr \'e al, May 28--June 1, 1985 , pages 321--350. Springer, 2006

    1985

  42. [42]

    Algorithm 950: Ncpol2sdpa—sparse semidefinite programming relaxations for polynomial optimization problems of noncommuting variables

    Peter Wittek. Algorithm 950: Ncpol2sdpa—sparse semidefinite programming relaxations for polynomial optimization problems of noncommuting variables. ACM Transactions on Mathematical Software (TOMS) , 41(3):1--12, 2015

    2015

  43. [43]

    Exploiting term sparsity in noncommutative polynomial optimization

    Jie Wang and Victor Magron. Exploiting term sparsity in noncommutative polynomial optimization. Computational Optimization and Applications , 80(2):483--521, 2021

    2021

  44. [44]

    QuantumNPA.jl , 2021

    Erik Woodhead. QuantumNPA.jl , 2021. Available at https://github.com/ewoodhead/QuantumNPA.jl

    2021

  45. [45]

    Certifying ground-state properties of many-body systems

    Jie Wang, Jacopo Surace, Ir \'e n \'e e Fr \'e rot, Beno \^ t Legat, Marc-Olivier Renou, Victor Magron, and Antonio Ac \' n. Certifying ground-state properties of many-body systems. Physical Review X , 14(3):031006, 2024

    2024

This paper was first reviewed by grok-4.5 on July 14, 2026.