REVIEW 2 major objections 7 minor 65 references
A Julia package turns partial commutations into faster, smaller SDP relaxations for quantum information problems.
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 →
T0 review · grok-4.5
2026-07-14 15:13 UTC pith:2HXG4ZR3
load-bearing objection Solid, usable software paper: specialized partial-commutativity data structures that measurably shrink and speed up NPA-style SDPs for the QI problems that actually use them. the 2 major comments →
PCPOP.jl: A Julia package for partially commutative polynomial optimization
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
The central claim is that a clique-representation arithmetic for partially commutative monoids, together with built-in reductions for projectors, unitaries, unipotents and cyclic equivalence, produces valid and substantially smaller semidefinite relaxations for the non-commutative, tracial, trace and state polynomial optimization problems that arise in quantum information.
What carries the argument
Clique representation of partially commutative words: each word is stored as its projections onto the maximal cliques of the dependence graph; multiplication, involution, division and cyclic equivalence then reduce to ordinary non-commutative operations on those projections, automatically incorporating the algebraic relations that appear in Bell and contextuality scenarios.
Load-bearing premise
That the clique projections plus the built-in projector/unitary reductions correctly identify every pair of words that are equivalent under the given partial commutations, so the resulting moment matrix is still a valid relaxation of the original problem.
What would settle it
On any of the benchmark problems (n-cycle CHSH, bilocal Mermin, conditional entropy bounds) construct the same level of the hierarchy with a complete Gröbner basis or an independent package and check whether the optimal values differ beyond solver tolerance, or whether an intermediate product of two clique words fails to equal the product computed by free monoid reduction.
If this is right
- Standard Bell, contextuality and network hierarchies can be built at higher levels or with more parties before the SDP becomes intractable.
- Device-independent entropy and key-rate bounds that previously required custom substitution rules become one-line calls that exploit the native partial-commutativity arithmetic.
- Exact-arithmetic pipelines (Gröbner + Wedderburn + rational SDP rounding) become routine for the same quantum-information problems.
- Graph-product monoids give a compact algebraic language for multi-partite scenarios with overlapping measurement supports.
Where Pith is reading between the lines
- The same clique arithmetic could be grafted onto existing sparsity or chordal-completion techniques to obtain hybrid reductions that neither package currently offers.
- Because cyclic equivalence is decided in linear time, tracial and free-probability hierarchies become practical for alphabets that previously forced exponential Gröbner bases.
- If the companion theory paper’s correctness proof holds, any future quantum-information SDP that can be written with partial commutations and projector relations can safely drop its hand-crafted substitution tables.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The manuscript presents PCPOP.jl, a Julia package for building and solving moment/SOS semidefinite relaxations of non-commutative, tracial, trace, and state polynomial optimization problems. Its distinguishing contribution is a specialized partially commutative monoid implementation (clique/graph-product representations with built-in projector, unitary, unipotent, and orthogonality reductions, plus a linear-time cyclic-equivalence test) aimed at quantum-information problems. The paper supplies mathematical background (§1), feature and implementation descriptions (§2–3), a tutorial with runnable examples (§4), a broad applications chapter (Bell scenarios, contextuality, conditional entropies, networks, uncertainty relations, almost qudits, information capacity; §5), and benchmarks against Ncpol2sdpa, QuantumNPA, Moment, and OSCAR (§6).
Significance. If the reported normal forms are correct and the package is maintained, this is a useful, practical contribution for the quantum-information community: it unifies several NPA-style hierarchies in one Julia interface, adds exact-arithmetic and symmetry/Jordan reductions, and—most importantly—exploits partial commutativity in a way that yields smaller, faster SDPs on standard QI benchmarks (notably n-cycle contextuality and related scenarios in Tables 3–4). Strengths include reproducible tutorial code, recovery of known tight values (CHSH, KCBS, bilocal Mermin, etc.), side-by-side SDP-size and timing tables against independent packages, and an open feature comparison (§2.7). Correctness of the core clique arithmetic is appropriately deferred to the companion theory paper [40] and the cyclic algorithm of [34]; the present manuscript’s role is software design, interface, and empirical performance.
major comments (2)
- The central performance claim rests on the clique/graph-product normal forms (and built-in projector/unitary/unipotent reductions) producing valid, complete equivalence classes for the moment matrices (§2.1, §3.2). Correctness is deferred to [40] and [34]. The manuscript should state this dependency more explicitly near the main claim (abstract/§2.1) and list, in one place, the known tight values recovered in §5 as empirical validation that the resulting SDPs remain valid relaxations. Without that short, load-bearing clarification, a reader cannot assess the risk that a missed or spurious identification would invalidate a relaxation.
- Reproducibility of the software claim: the installation snippet (§4.1) uses Pkg.add("PCPOP"), but the manuscript does not give a version pin, repository URL/DOI, or commit corresponding to the §6 timings (20-core i7-12700, 64 GB). For a package paper whose main result is comparative performance (Tables 1–4), a fixed release identifier and a short note on solver versions (Mosek) and floating-point vs exact modes used in the tables are needed so that the reported speed-ups can be re-run.
minor comments (7)
- Several tutorial/application snippets leave variables undefined or unused (e.g. §5.4 prints val without assigning objective_value(model); §5.3 mixes npa_dual/model_new_obj with the pcpop API of §4.2). Align examples with the documented public API or mark internal helpers.
- §4.3 CHSH code uses a[2,0] b[2,0] with Unipotent and objective a[1]*b[1]+… while the displayed problem (25) indexes a0,a1,b0,b1; the indexing is consistent in 1-based Julia but the prose/equation labels should match the code arrays to avoid confusion.
- Table 1 caption says SDP size, #cons, and #vars are the same for all packages, yet the narrative in §6.2 notes implementation differences in how equivalence constraints are counted (PCPOP vs others). Clarify when counts are forced equal vs when PCPOP’s single-PSD formulation reduces #cons (as in Table 3).
- §2.7 compares features with NCTSSOS and SumOfSquares but §6 benchmarks only Ncpol2sdpa, QuantumNPA, Moment, and OSCAR. A one-sentence note that NCTSSOS sparsity was out of scope for this release would prevent a missing-baseline objection.
- Typos and polish: “Gr¨ obner” spacing throughout; “semidefinitze” (§4.10); “optimzation” (§5.1); “Paw/suppress lowski” and similar bibliography encoding artifacts; “Beno ˆ ıt” in acknowledgements. Clean UTF-8 and LaTeX accents.
- Figure 1–3 axes use Time (ns) with log scale; state the number of random trials and whether times include monoid build or only multiply+reduce, so the OSCAR vs PCPOP comparison is unambiguous.
- §1.6 lists three SDP encodings; default choices (primal=true, canonical matrix variables) are stated later in §4.2. Cross-reference defaults once in §1.6 for readers who skip the tutorial.
Circularity Check
No significant circularity: software-performance claims rest on independent third-party benchmarks; self-citation of companion theory paper [40] is legitimate background, not a definitional loop.
specific steps
-
self citation load bearing
[Abstract; §2.1; §3.2; reference [40]]
"As a distinguished feature, PCPOP implements a specialized framework for polynomial computations in partially commutative variables that provides significant computational advantages for problems appearing in quantum information. ... PCPOPimplements a specialized framework for partially commutative polynomial optimization [40] ... The clique representation is specially suitable for our computational implementation ..."
Correctness of the clique projections, multiplication/division algorithms, and internal projector/unitary reductions is not proved in the present manuscript; it is imported wholesale from the authors’ companion theory paper [40]. This is a mild self-citation dependency for the algebraic validity of the resulting moment matrices. It is not circular for the performance claims, which are independently measured against third-party solvers on standard problems.
full rationale
PCPOP.jl is a package paper whose central claim is empirical computational advantage of clique-representation arithmetic (plus built-in projector/unitary/unipotent reductions and the cyclic test of [34]) on quantum-information problems. Correctness of the normal forms is deferred to the authors’ companion theory paper [40] and is not re-derived here; that is ordinary software-engineering practice, not circular construction of a result. The reported speed-ups and smaller SDPs are measured against independent packages (Ncpol2sdpa, QuantumNPA, Moment) on publicly stated problems (CHSH, n-cycle contextuality, conditional entropy, etc.) that recover known tight values. There are no fitted parameters renamed as predictions, no uniqueness theorems imported solely from the authors to forbid alternatives, and no self-definitional identities. The single self-citation of [40] is load-bearing only for the algebraic correctness premise, which is externally falsifiable by the package’s exact-arithmetic tutorials and recovery of standard bounds; it does not force the performance numbers. Hence score 1 (minor self-citation that is not load-bearing for the headline claim).
Axiom & Free-Parameter Ledger
axioms (3)
- standard math Under mild boundedness assumptions the NPA / tracial / state / trace moment-SOS hierarchies converge to the true optimum of the corresponding polynomial optimization problem.
- standard math Clique projections furnish a canonical form for free partially commutative monoids, and the linear-time algorithm of Liu–Wrathall–Zeger decides cyclic equivalence.
- domain assumption The specialized reductions for projectors, unitaries, unipotents and orthogonality preserve the ideal membership and therefore yield valid SDP relaxations.
invented entities (1)
-
GraphProductMonoid / PCMonomial clique-representation data structures with edge_l / edge_r fields
no independent evidence
read the original abstract
Here we present PCPOP, a Julia package for polynomial optimization that supports non-commutative optimization, tracial polynomial optimization, trace polynomial optimization and state polynomial optimization. PCPOP fully supports exact arithmetic computations and incorporates convenient functionalities such as algebraic reductions based on Gr\"obner basis methods, automatized symmetrization via Wedderburn decompositions, and Jordan algebra reductions. As a distinguished feature, PCPOP implements a specialized framework for polynomial computations in partially commutative variables that provides significant computational advantages for problems appearing in quantum information.
Figures
Reference graph
Works this paper leans on
-
[1]
Ac ´ ın, T
A. Ac ´ ın, T. Fritz, A. Leverrier, and A. B. Sainz. A combinatorial approach to nonlocality and contextuality.Communications in Mathematical Physics, 334:533– 628, 2015
2015
-
[2]
Adhikary, A
R. Adhikary, A. Mishra, and R. Rahaman. Self-testing of genuine multipartite en- tangled states without network assistance.Physical Review A, 110(1):L010401, 2024
2024
-
[3]
Ara´ ujo, M
M. Ara´ ujo, M. T. Quintino, C. Budroni, M. T. Cunha, and A. Cabello. All non- contextuality inequalities for then-cycle scenario.Physical Review A, 88(2):022118, 2013
2013
-
[4]
Ate¸ s, E
F. Ate¸ s, E. G. Karpuz, C. Kocapınar, and A. S. C ¸ evik. Gr¨ obner–Shirshov bases of some monoids.Discrete Mathematics, 311(12):1064–1071, 2011
2011
-
[5]
Boghiu, E
E.-C. Boghiu, E. Wolfe, and A. Pozas-Kerstjens. Inflation: a Python library for classical and quantum causal compatibility.Quantum, 7:996, 2023
2023
-
[6]
Brosch and E
D. Brosch and E. de Klerk. Jordan symmetry reduction for conic optimization over the doubly nonnegative cone: theory and software.Optimization Methods and Software, 37(6):1987–2006, 2022
1987
-
[7]
Brown, H
P. Brown, H. Fawzi, and O. Fawzi. Device-independent lower bounds on the condi- tional von Neumann entropy.Quantum, 8:1445, 2024
2024
-
[8]
Burgdorf, K
S. Burgdorf, K. Cafuta, I. Klep, and J. Povh. The tracial moment problem and trace- optimization of polynomials.Mathematical programming, 137(1):557–578, 2013
2013
-
[9]
Burgdorf, I
S. Burgdorf, I. Klep, and J. Povh.Optimization of polynomials in non-commuting variables, volume 2 ofSpringerBriefs in Mathematics. Springer, 2016
2016
-
[10]
Cartier and D
P. Cartier and D. Foata.Applications probabilistes, volume 85 ofLecture Notes on Mathematics. Springer, 1969
1969
-
[11]
Chaturvedi, G
A. Chaturvedi, G. Viola, and M. Paw/suppress lowski. Extending loophole-free nonlocal cor- relations to arbitrarily large distances.NPJ Quantum Information, 10(1):7, 2024
2024
-
[12]
J. F. Clauser, M. A. Horne, A. Shimony, and R. A. Holt. Proposed experiment to test local hidden-variable theories.Phys. Rev. Lett., 23:880–884, 1969
1969
-
[13]
A. V. da Costa. Graph products of monoids. InSemigroup Forum, volume 63, pages 247–277. Springer, 2001. 47
2001
-
[14]
Dandan and V
Y. Dandan and V. Gould. On graph products of monoids.Journal of Algebra, 620:113–156, 2023
2023
-
[15]
Devetak and A
I. Devetak and A. Winter. Distillation of secret key and entanglement from quantum states.Proceedings of the Royal Society A, 461(2053):207–235, 2005
2053
-
[16]
Diekert and Y
V. Diekert and Y. M´ etivier.Partial Commutation and Traces, pages 457–533. Springer Berlin Heidelberg, 1997
1997
-
[17]
C. Duboc. On some equations in free partially commutative monoids.Theoretical Computer Science, 46:159–174, 1986
1986
-
[18]
A. J. P. Garner and M. Ara´ ujo. Introducing Moment: A toolkit for semi-definite programming with moment matrices. 2024. A vailable athttps://github.com/ ajpgarner/moment
2024
-
[19]
Gatermann and P
K. Gatermann and P. A. Parrilo. Symmetry groups, semidefinite programs, and sums of squares.Journal of Pure and Applied Algebra, 192(1-3):95–128, 2004
2004
-
[20]
Helton and S
J. Helton and S. McCullough. A Positivstellensatz for non-commutative polynomials. Transactions of the American Mathematical Society, 356(9):3721–3737, 2004
2004
-
[21]
Ioannou and D
M. Ioannou and D. Rosset. Noncommutative polynomial optimization under sym- metry, 2022
2022
-
[22]
Kaluba, P
M. Kaluba, P. W. Nowak, and N. Ozawa. Aut(F 5)has property (T).Mathematische annalen, 375(3):1169–1191, 2019
2019
-
[23]
Karmarkar
N. Karmarkar. A new polynomial-time algorithm for linear programming. InPro- ceedings of the sixteenth annual ACM symposium on Theory of computing, pages 302–311, 1984
1984
-
[24]
I. Klep, V. Magron, and J. Povh. Sparse noncommutative polynomial optimization. Mathematical Programming, 193(2):789–829, 2022
2022
-
[25]
I. Klep, V. Magron, and J. Volˇ ciˇ c. Optimization over trace polynomials. InAnnales Henri Poincar´ e, volume 23, pages 67–100. Springer, 2022
2022
-
[26]
I. Klep, V. Magron, J. Volˇ ciˇ c, and J. Wang. State polynomials: positivity, optimiza- tion and nonlinear Bell inequalities.Mathematical Programming, 207(1):645–691, 2024
2024
-
[27]
A. A. Klyachko, M. A. Can, S. Binicio˘ glu, and A. S. Shumovsky. Simple test for hidden variables in spin-1 systems.Physical Review Letters, 101(2):020403, 2008
2008
-
[28]
D. E. Knuth and P. B. Bendix. Simple word problems in universal algebras. In Computational Problems in Abstract Algebra, pages 263–297. Elsevier, 1970
1970
-
[29]
La Scala and V
R. La Scala and V. Levandovskyy. Letterplace ideals and non-commutative Gr¨ obner bases.Journal of Symbolic Computation, 44(10):1374–1393, 2009
2009
-
[30]
J. B. Lasserre. Global optimization with polynomials and the problem of moments. SIAM Journal on Optimization, 11(3):796–817, 2001. 48
2001
-
[31]
Legat, C
B. Legat, C. Coey, R. Deits, J. Huchette, and A. Perry. Sum-of-squares optimization in Julia. InThe First Annual JuMP-dev Workshop, 2017
2017
-
[32]
Leijenhorst and D
N. Leijenhorst and D. de Laat. Solving clustered low-rank semidefinite programs arising from polynomial optimization.Mathematical Programming Computation, 16(3):503–534, 2024
2024
-
[33]
L. T. Ligthart and D. Gross. The inflation hierarchy and the polarization hierarchy are complete for the quantum bilocal scenario.Journal of Mathematical Physics, 64(7), 2023
2023
-
[34]
H.-N. Liu, C. Wrathall, and K. Zeger. Efficient solution of some problems in free partially commutative monoids.Information and Computation, 89(2):180–198, 1990
1990
-
[35]
E. P. Lobo, J. Pauwels, and S. Pironio. Certifying long-range quantum correlations through routed Bell tests.Quantum, 8:1332, 2024
2024
-
[36]
Magron and J
V. Magron and J. Wang.Sparse Polynomial Optimization: Theory and Practice. World Scientific, 2022
2022
-
[37]
Mazurkiewicz
A. Mazurkiewicz. Concurrent program schemes and their interpretations.DAIMI Report Series, (78), 1977
1977
-
[38]
N. D. Mermin. Simple unified form for the major no-hidden-variables theorems. Physical Review Letters, 65(27):3373, 1990
1990
-
[39]
C. A. Miller and Y. Shi. Universal security for randomness expansion from the spot-checking protocol.SIAM Journal on Computing, 46(4):1304–1335, 2017
2017
-
[40]
Mishra, M
A. Mishra, M. B. Mor´ an, and S. Pironio. Partially-commutative polynomial opti- mization, 2026
2026
-
[41]
T. Mora. An introduction to commutative and noncommutative Gr¨ obner bases. Theoretical Computer Science, 134(1):131–173, 1994
1994
-
[42]
M. B. Mor´ an and F. Huber. Uncertainty relations from state polynomial optimiza- tion.Physical Review Letters, 132(20):200202, 2024
2024
-
[43]
M. B. Mor´ an, A. Pozas-Kerstjens, and F. Huber. Bell inequalities with overlapping measurements.Physical Review Letters, 131:080201, 2023
2023
-
[44]
Murota, Y
K. Murota, Y. Kanno, M. Kojima, and S. Kojima. A numerical algorithm for block- diagonal decomposition of matrix∗-algebras with application to semidefinite pro- gramming.Japan Journal of Industrial and Applied Mathematics, 27(1):125–160, 2010
2010
-
[45]
Nesterov and A
Y. Nesterov and A. Nemirovskii.Interior-Point Polynomial Algorithms in Convex Programming. Society for Industrial and Applied Mathematics, 1994
1994
-
[46]
A vaiable athttps://github.com/oscar-system/Oscar.jl
OSCAR – Open Source Computer Algebra Research system, Version 1.7.3, 2026. A vaiable athttps://github.com/oscar-system/Oscar.jl
2026
-
[47]
Pauwels, S
J. Pauwels, S. Pironio, E. Woodhead, and A. Tavakoli. Almost qudits in the prepare- and-measure scenario.Physical Review Letters, 129:250504, Dec 2022. 49
2022
-
[48]
A. Peres. Incompatible results of quantum measurements.Physics Letters A, 151(3- 4):107–108, 1990
1990
-
[49]
Permenter and P
F. Permenter and P. A. Parrilo. Dimension reduction for semidefinite programs via Jordan algebras.Mathematical Programming, 181(1):51–84, 2020
2020
-
[50]
Pironio, M
S. Pironio, M. Navascu´ es, and A. Ac ´ ın. Convergent relaxations of polynomial opti- mization problems with noncommuting variables.SIAM Journal on Optimization, 20(5):2157–2180, 2010
2010
-
[51]
Pozas-Kerstjens, R
A. Pozas-Kerstjens, R. Rabelo, /suppress L. Rudnicki, R. Chaves, D. Cavalcanti, M. Navascu´ es, and A. Ac ´ ın. Bounding the sets of classical and quantum correlations in networks. Physical Review Letters, 123(14):140503, 2019
2019
-
[52]
Renou, X
M.-O. Renou, X. Xu, and L. T. Ligthart. Two convergent NPA-like hierarchies for the quantum bilocal scenario.Journal of Mathematical Physics, 67(1), 2026
2026
-
[53]
I. D. Smith, E. Wolfe, and R. W. Spekkens. Fully quantum inflation: quantum marginal problem constraints in the service of causal inference.PRX Quantum, 7(1):010351, 2026
2026
-
[54]
Tavakoli, E
A. Tavakoli, E. Z. Cruzeiro, E. Woodhead, and S. Pironio. Informationally restricted correlations: a general framework for classical and quantum systems.Quantum, 6:620, 2022
2022
-
[55]
Tavakoli, A
A. Tavakoli, A. Pozas-Kerstjens, M.-X. Luo, and M.-O. Renou. Bell nonlocality in networks.Reports on Progress in Physics, 85(5):056001, 2022
2022
-
[56]
J. Uffink. Quadratic Bell inequalities as tests for multipartite entanglement.Physical Review Letters, 88(23):230406, 2002
2002
-
[57]
Vandenberghe and S
L. Vandenberghe and S. Boyd. Semidefinite programming.SIAM Review, 38(1):49– 95, 1996
1996
-
[58]
J. Wang. NCTSSOS, 2021. A vailable athttps://github.com/wangjie212/ NCTSSOS
2021
-
[59]
Weisser, B
T. Weisser, B. Legat, C. Coey, L. Kapelevich, and J. P. Vielma. Polynomial and moment optimization in julia and JuMP. InJuliaCon, 2019
2019
-
[60]
P. Wittek. Algorithm 950: Ncpol2sdpa—sparse semidefinite programming relax- ations for polynomial optimization problems of noncommuting variables.ACM Transactions on Mathematical Software, 41(3):1–12, 2015
2015
-
[61]
P. Wittek. Ncpol2sdpa, 2017. A vailable athttps://github.com/peterwittek/ ncpol2sdpa
2017
-
[62]
Wolfe, A
E. Wolfe, A. Pozas-Kerstjens, M. Grinberg, D. Rosset, A. Ac ´ ın, and M. Navascu´ es. Quantum inflation: A general approach to quantum causal compatibility.Physical Review X, 11(2):021043, 2021
2021
-
[63]
Wolfe, R
E. Wolfe, R. W. Spekkens, and T. Fritz. The inflation technique for causal inference with latent variables.Journal of Causal Inference, 7(2):20170020, 2019. 50
2019
-
[64]
Woodhead
E. Woodhead. QuantumNPA.jl, 2021. A vailable athttps://github.com/ ewoodhead/QuantumNPA.jl
2021
-
[65]
Xiu.Non-commutative Gr¨ obner bases and applications
X. Xiu.Non-commutative Gr¨ obner bases and applications. PhD thesis, Universit¨ at Passau, 2012. 51
2012
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.