pith. sign in

arxiv: 2509.02309 · v2 · submitted 2025-09-02 · 🪐 quant-ph

Picking NPA constraints from a randomly sampled quantum moment matrix

G. Viola , A. Chaturvedi , P. Mironowicz This is my paper

Pith reviewed 2026-05-18 19:34 UTC · model grok-4.3

classification 🪐 quant-ph
keywords quantum correlationsSDP relaxationsNPA hierarchymoment matricesquantum nonlocalityrandom sampling
0
0 comments X

The pith

Randomly sampled quantum moment matrices supply equality constraints for SDP relaxations that bound quantum correlations.

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

The paper introduces a method to generate semi-definite programming relaxations for bounding quantum correlations by pulling equality constraints out of randomly sampled moment matrices. This replaces the usual manual construction of constraints with a sampling procedure. The result is a flexible way to approximate the quantum set in many different operational scenarios. A reader would care because the technique lowers the effort required to compute bounds on non-classical correlations across varied setups.

Core claim

We describe a simple and flexible method for implementing semi-definite programming relaxations for bounding the set of quantum correlations. The method relies on obtaining equality constraints from randomly sampled moment matrices and hence allows the user to easily access the set of quantum behavior in diverse operational scenarios.

What carries the argument

Random sampling of quantum moment matrices to extract the equality constraints that define each SDP relaxation.

If this is right

  • The procedure lets users bound quantum correlations in many operational scenarios without deriving the full constraint set by hand for each case.
  • It supports direct implementation of SDP relaxations that approximate the quantum set from sampled data.
  • The approach extends naturally to different choices of moment matrix size and sampling density.

Where Pith is reading between the lines

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

  • If sampling proves reliable, the same random-extraction idea could be tried on other hierarchies or correlation polytopes beyond the NPA case.
  • One could measure how the quality of the bound changes with sample size and compare it against deterministic constraint selection.
  • The method might combine with existing numerical tools to automate bound computation for new Bell-like experiments.

Load-bearing premise

That the equality constraints extracted from randomly sampled moment matrices are sufficient to produce valid SDP relaxations that correctly bound the quantum set without missing essential constraints or adding extraneous ones.

What would settle it

Run the procedure on the CHSH scenario and verify whether the resulting SDP upper bound equals the known Tsirelson value of 2*sqrt(2); any deviation would indicate that the sampled constraints are incomplete or incorrect.

read the original abstract

We describe a simple and flexible method for implementing semi-definite programming relaxations for bounding the set of quantum correlations. The method relies on obtaining equality constraints from randomly sampled moment matrices and hence allows the user to easily access the set of quantum behavior in diverse operational scenarios.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript proposes a simple method for generating equality constraints in NPA-style SDP relaxations of quantum correlations. It extracts these constraints as the common linear dependencies (kernel) of randomly sampled quantum moment matrices, with the goal of allowing flexible access to outer approximations of the quantum set in diverse operational scenarios without manual derivation of the full constraint set.

Significance. If the sampled constraints provably recover the exact codimension of the quantum moment cone at the target level, the technique would offer a practical, scenario-agnostic implementation route for SDP bounds. The approach could reduce the barrier to exploring non-standard Bell scenarios, provided it is accompanied by reproducible code or explicit validation against known NPA levels.

major comments (2)
  1. [Method / Algorithm] The central construction (presumably §3 or the algorithm description) extracts equality constraints from the numerical kernel of finitely many random moment matrices. No proof or error analysis is supplied showing that this kernel coincides with the exact linear span of all quantum behaviors at the chosen hierarchy level; finite sampling plus floating-point arithmetic can miss independent relations or retain approximate ones, directly affecting whether the resulting SDP outer-approximates the quantum set without extraneous restrictions or looseness.
  2. [Numerical validation] Table or numerical example (if present in §4): the manuscript should report the rank of the sampled kernel versus the analytically known codimension of the NPA moment matrix at the same level, together with a comparison of the obtained bound to a standard NPA implementation on a known scenario (e.g., CHSH). Absence of such a check leaves the claim that the SDP correctly bounds the quantum set unverified.
minor comments (2)
  1. [Abstract] The abstract is terse and does not mention any validation, error analysis, or comparison to existing NPA solvers; a sentence summarizing the numerical evidence would improve clarity.
  2. [Notation / Implementation details] Notation for the sampled moment matrices and the extracted kernel should be defined once and used consistently; floating-point tolerance used to decide linear dependence should be stated explicitly.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their constructive report and for highlighting important points regarding the theoretical justification and empirical validation of our sampling-based approach to generating NPA constraints. We have revised the manuscript to incorporate additional discussion and numerical checks as detailed below.

read point-by-point responses

  1. Referee: [Method / Algorithm] The central construction (presumably §3 or the algorithm description) extracts equality constraints from the numerical kernel of finitely many random moment matrices. No proof or error analysis is supplied showing that this kernel coincides with the exact linear span of all quantum behaviors at the chosen hierarchy level; finite sampling plus floating-point arithmetic can miss independent relations or retain approximate ones, directly affecting whether the resulting SDP outer-approximates the quantum set without extraneous restrictions or looseness.

    Authors: We agree that a complete proof guaranteeing exact recovery of the kernel for arbitrary finite samples would be desirable. Our approach is presented as a practical, scenario-agnostic heuristic that has been observed to recover the expected constraints in tested cases. In the revised manuscript we have added a dedicated subsection on numerical stability, including a brief probabilistic argument based on the dimension of the moment matrix and the use of double-precision arithmetic with a small tolerance threshold for rank computation. We also provide a simple heuristic for the minimal number of samples needed to stabilize the kernel. A general rigorous proof of exact codimension recovery remains beyond the scope of the current work. revision: partial

  2. Referee: [Numerical validation] Table or numerical example (if present in §4): the manuscript should report the rank of the sampled kernel versus the analytically known codimension of the NPA moment matrix at the same level, together with a comparison of the obtained bound to a standard NPA implementation on a known scenario (e.g., CHSH). Absence of such a check leaves the claim that the SDP correctly bounds the quantum set unverified.

    Authors: We accept this criticism. The original manuscript contained only informal checks; we have now added a new table in Section 4 that reports the numerical rank of the sampled kernel for increasing numbers of random samples at NPA level 2, directly compared against the analytically known codimension for the CHSH scenario. We further include a side-by-side comparison of the SDP upper bounds obtained via our method and via a standard NPA implementation, confirming agreement to within 10^{-8} for the maximal CHSH violation. revision: yes

Circularity Check

0 steps flagged

No circularity: method extracts constraints from external quantum moment matrices

full rationale

The paper proposes a numerical procedure that samples random quantum moment matrices (generated from standard quantum states and measurements) and extracts their linear dependencies as equality constraints for NPA-style SDP relaxations. This construction directly implements the definition of the quantum set rather than deriving a result that reduces to its own fitted inputs or self-citations. No load-bearing step equates an output to an input by construction, and the approach remains self-contained against the external benchmark of quantum theory.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract-only review yields no explicit free parameters, axioms, or invented entities. The central claim implicitly assumes that random sampling of moment matrices produces valid equality constraints for quantum SDP relaxations.

pith-pipeline@v0.9.0 · 5558 in / 1064 out tokens · 26162 ms · 2026-05-18T19:34:08.716901+00:00 · methodology

discussion (0)

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

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

34 extracted references · 34 canonical work pages · 3 internal anchors

  1. [1]

    When r = 1, the algorithm generatesn rank-1 projectors in a d = n dimensional system, forming a standard projective measurement

    work page

  2. [2]

    When r = 2, the same algorithm considers a2n-dimensional system, generates 2n random rank-1 projectors, and then groups them in pairs: Pj = |v2j−1⟩⟨v2j−1| + |v2j⟩⟨v2j|. (A4)

    work page

  3. [3]

    More generally, for any rankr, one considers arn-dimensional system, partitions the eigenvectors into blocks of r elements, and sums them to obtain the required rank-r projectors. This construction guarantees that the resulting projectors are random (distributed according to the Haar measure) while satisfying the required positivity, orthogonality and res...

    work page

  4. [4]

    Party assignment: for each j, P (i) j acts only onH(i)

    work page

  5. [5]

    Fixed rank: each projectorP (i) j has rank exactlyr in the space on which it acts; 7

    work page

  6. [6]

    We define the associatedscenario operatoras ˆP = P (1) 1 ...P (1) J0 ⊗

    Independence: the projectors {P (i) j }j are linearly independent, i.e., no projector can be expressed as a linear combination of the others. We define the associatedscenario operatoras ˆP = P (1) 1 ...P (1) J0 ⊗ .... ⊗ P (m) 1 ...P (m) Jm (B2) acting on the Hilbert spaceH = H(1) ⊗ ... ⊗ H(m). In the context of randomly generated quantum states and measur...

    work page

  7. [7]

    non-orthogonal, i.e.,P (i) j P (i) j+1 ̸= 0

    work page

  8. [8]

    If P(i) is simplified, then we call it thei-th block of projectorsof the scenario sequenceP

    non-identical, i.e.,P (i) j ̸= P (i) j+1. If P(i) is simplified, then we call it thei-th block of projectorsof the scenario sequenceP. We denote byP (i) j the j-th projector in this block. Note thatP (i) j refers to thej-th element of thei-th block, and not to thej-th projector in the full scenario sequence P. The condition of simplification implies that ...

    work page

  9. [9]

    A0 = B0 and An−1 = Bn−1

    work page

  10. [10]

    MNIP" is the maximum number of independent projectors which appear in the same side of the first equality in (E17),

    C(A(i)) = C(B(i)) as multisets. 8 The following example illustrates the notion of homogeneous blocks. Example 1.Consider the following two simplified blocks of projectors, where we omit party index for simplicity, of length 5: P = (P0, P1, P0, P2, P0), (B6) P′ = (P0, P2, P0, P1, P0). (B7) The multiset of consecutive pairs forP is: C(P) = {(P0, P1), (P1, P...

    work page

  11. [11]

    Quantum cryptography with imperfect apparatus,

    D. Mayers and A. Yao, “Quantum cryptography with imperfect apparatus,” inProceedings 39th Annual Symposium on Foundations of Computer Science (Cat. No. 98CB36280) , pp. 503–509, IEEE, 1998

    work page 1998

  12. [12]

    The future of secure communications: device independence in quantumkey distribution,

    S. A. Ghoreishi, G. Scala, R. Renner, L. L. Tacca, J. Bouda, S. P. Walborn, and M. Pawłowski, “The future of secure communications: device independence in quantumkey distribution,”arXiv preprint arXiv:2504.06350v2 , 2025

    work page arXiv 2025

  13. [13]

    Quantum entanglement,

    R. Horodecki, P. Horodecki, M. Horodecki, and K. Horodecki, “Quantum entanglement,”Reviews of modern physics, vol. 81, no. 2, p. 865, 2009

    work page 2009

  14. [14]

    Bounding the set of quantum correlations,

    M. Navascués, S. Pironio, and A. Acín, “Bounding the set of quantum correlations,”Physical Review Letters, vol. 98, no. 1, p. 010401, 2007

    work page 2007

  15. [15]

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

    M. Navascués, S. Pironio, and A. Acín, “A convergent hierarchy of semidefinite programs characterizing the set of quantum correlations,”New Journal of Physics , vol. 10, no. 7, p. 073013, 2008

    work page 2008

  16. [16]

    Random numbers certified by bell’s theorem,

    S. Pironio, A. Acín, S. Massar, A. B. de La Giroday, D. N. Matsukevich, P. Maunz, S. Olmschenk, D. Hayes, L. Luo, T. A. Manning, et al., “Random numbers certified by bell’s theorem,”Nature, vol. 464, no. 7291, pp. 1021–1024, 2010

    work page 2010

  17. [17]

    Applications of semi-definite optimization in quantum information protocols

    P. Mironowicz, “Applications of semi-definite optimization in quantum information protocols,” arXiv preprint arXiv:1810.05145, 2018. 14

    work page internal anchor Pith review Pith/arXiv arXiv 2018

  18. [18]

    Algorithm 950: Ncpol2sdpa—sparse semidefinite programming relaxations for polynomial optimization prob- lems of noncommuting variables,

    P. Wittek, “Algorithm 950: Ncpol2sdpa—sparse semidefinite programming relaxations for polynomial optimization prob- lems of noncommuting variables,”ACM Transactions on Mathematical Software (TOMS) , vol. 41, no. 3, pp. 1–12, 2015

    work page 2015

  19. [19]

    Semi-device-independent security of one-way quantum key distribution,

    M. Pawłowski and N. Brunner, “Semi-device-independent security of one-way quantum key distribution,”Physical Review A, vol. 84, no. 1, p. 010302, 2011

    work page 2011

  20. [20]

    Properties of dimension witnesses and their semidefinite programming relaxations,

    P. Mironowicz, H.-W. Li, and M. Pawłowski, “Properties of dimension witnesses and their semidefinite programming relaxations,”Physical Review A, vol. 90, no. 2, p. 022322, 2014

    work page 2014

  21. [21]

    Bounding the set of finite dimensional quantum correlations,

    M. Navascués and T. Vértesi, “Bounding the set of finite dimensional quantum correlations,”Physical review letters , vol. 115, no. 2, p. 020501, 2015

    work page 2015

  22. [22]

    Quantum-inspired hierarchy for rank-constrained optimization,

    X.-D. Yu, T. Simnacher, H. C. Nguyen, and O. Gühne, “Quantum-inspired hierarchy for rank-constrained optimization,” PRX Quantum, vol. 3, no. 1, p. 010340, 2022

    work page 2022

  23. [23]

    A newton-like method for solving rank constrained linear matrix inequalities,

    R. Orsi, U. Helmke, and J. B. Moore, “A newton-like method for solving rank constrained linear matrix inequalities,” Automatica, vol. 42, no. 11, pp. 1875–1882, 2006

    work page 2006

  24. [24]

    Rank-constrained optimization and its applications,

    C. Sun and R. Dai, “Rank-constrained optimization and its applications,”Automatica, vol. 82, pp. 128–136, 2017

    work page 2017

  25. [25]

    Can quantum-mechanical description of physical reality be considered complete?,

    A. Einstein, B. Podolsky, and N. Rosen, “Can quantum-mechanical description of physical reality be considered complete?,” Physical review, vol. 47, no. 10, p. 777, 1935

    work page 1935

  26. [26]

    On the einstein podolsky rosen paradox,

    J. S. Bell, “On the einstein podolsky rosen paradox,”Physics Physique Fizika , vol. 1, no. 3, p. 195, 1964

    work page 1964

  27. [27]

    Proposed experiment to test local hidden-variable theories,

    J. F. Clauser, M. A. Horne, A. Shimony, and R. A. Holt, “Proposed experiment to test local hidden-variable theories,” Physical review letters, vol. 23, no. 15, p. 880, 1969

    work page 1969

  28. [28]

    Experimental tests of realistic local theories via bell’s theorem,

    A. Aspect, P. Grangier, and G. Roger, “Experimental tests of realistic local theories via bell’s theorem,”Physical review letters, vol. 47, no. 7, p. 460, 1981

    work page 1981

  29. [29]

    Bell inequalities and Entanglement

    R. F. Werner and M. M. Wolf, “Bell inequalities and entanglement,”arXiv preprint quant-ph/0107093 , 2001

    work page internal anchor Pith review Pith/arXiv arXiv 2001

  30. [30]

    Quantum Matching Theory (with new complexity theoretic, combinatorial and topological insights on the nature of the Quantum Entanglement)

    L. Gurvits, “Quantum matching theory (with new complexity theoretic, combinatorial and topological insights on the nature of the quantum entanglement),”arXiv preprint quant-ph/0201022 , 2002

    work page internal anchor Pith review Pith/arXiv arXiv 2002

  31. [31]

    Detecting multipartite entanglement,

    A. C. Doherty, P. A. Parrilo, and F. M. Spedalieri, “Detecting multipartite entanglement,”Physical Review A , vol. 71, no. 3, p. 032333, 2005

    work page 2005

  32. [32]

    Entangled games are hard to approximate,

    J. Kempe, H. Kobayashi, K. Matsumoto, B. Toner, and T. Vidick, “Entangled games are hard to approximate,”SIAM Journal on Computing , vol. 40, no. 3, pp. 848–877, 2011

    work page 2011

  33. [33]

    S. P. Boyd and L. Vandenberghe,Convex optimization. Cambridge university press, 2004

    work page 2004

  34. [34]

    A new polynomial-time algorithm for linear programming,

    N. Karmarkar, “A new polynomial-time algorithm for linear programming,” inProceedings of the sixteenth annual ACM symposium on Theory of computing , pp. 302–311, 1984

    work page 1984