Pith. sign in

REVIEW 7 minor 1 cited by

The complexity of compatible measurements

T0 review · 0 major / 7 minor · reviewed 2026-08-14 · deepseek-v4-flash

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

Pith's one-line read For every family of $m$ compatible quantum measurements, a parent measurement exists with at most $d^2(m(o-1)+1)$ outcomes.

desk verdict Skrzypczyk et al. prove a linear-in-m bound on parent-measurement size and certify an exponential small-case example, so the central result is solid and worth refereeing. read the letter →

arxiv 1908.10085 v1 pith:6HUJHLHL submitted 2019-08-27 quant-ph

Paul Skrzypczyk , Matty J. Hoban , Ana Belén Sainz , Noah Linden This is my paper · ORCID
classification quant-ph MSC 81P1552A20 PACS 03.65.Ta
keywords jointmeasurabilityPOVMparentmeasurementincompatibilityCarathéodorytheoremsemidefiniteprogrammingEPRsteeringlocalhiddenstatemodel
topics The Measurement Problem
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

Quantum measurements that can be performed together are called compatible, and a single parent measurement can simulate them by coarse-graining its outcomes. The naive parent has $o^m$ outcomes, one for every combination of the children's outcomes, which grows exponentially with the number $m$ of measurements. This paper proves that such exponential parents are never necessary once $m$ is large: every set of $m$ compatible measurements on $\mathbb{C}^d$ with $o$ outcomes has a parent with at most $d^2(m(o-1)+1)$ non-vanishing POVM elements. It also exhibits small cases where the exponential parent genuinely is required, so the bound is not vacuous but instead marks a transition in how complex compatibility can be.

What carries the argument

The load-bearing object is the joint-measurability cone: the collection of sub-normalised deterministic response functions embedded in $\mathbb{R}^{D}$ with $D=d^2(m(o-1)+1)$. Its extremal rays are exactly the deterministic sub-measurements, and Carathéodory's theorem for cones states that any point in a $D$-dimensional cone is a non-negative combination of at most $D$ extremal rays. The proof repeatedly uses any linear dependence among more than $D$ parent elements to zero one element while preserving the children, terminating with a parent of size at most $D$. A complementary mechanism is the SDP dual: for a fixed sparsity pattern, weak duality produces a witness operator whose negativity certifies that no parent with that pattern exists, which is how the paper proves maximal complexity in the small examples.

What would settle it

Search for a counterexample where the bound is tighter than the canonical parent, for instance $m=5$ binary-outcome measurements on a qubit, where the claimed bound is 24 parent elements and the canonical parent has 32. Checking all sparsity patterns of size 24 with the compatibility SDP and finding a set whose minimal parent has 25 or more non-vanishing elements would refute equation (9).

Watch

Extended reading notes

Core claim

The central discovery is a linear-in-$m$ bound on the complexity of joint measurability. Writing a set of compatible measurements as a point in a real vector space of dimension $D=d^2(m(o-1)+1)$---one coordinate block for each sub-normalised measurement element plus extra coordinates for the normalisation---the paper identifies compatible sets with points in a convex cone whose extremal rays are deterministic sub-measurements. Carathéodory's theorem for cones then implies that any such point is a conic combination of at most $D$ extremal rays, and translating back yields a parent POVM with at most $D$ non-vanishing elements. The same geometric argument gives a corresponding bound on the number of hidden states in local-hidden-state models for EPR steering, since steering assemblages and compatible measurements are in one-to-one correspondence. The paper also constructs maximally complex examples---a pair of qubit measurements requiring all four parent elements and a triple of qutrit measurements requiring all eight---and develops an SDP-duality witness method to certify that no smaller parent exists.

Load-bearing premise

The proof relies on representing a compatible set as a point in a cone of exactly $d^2(m(o-1)+1)$ dimensions, so that any such point is a combination of at most that many special rays; if the normalisation condition requires one more ray, the bound rises by one.

Editorial extensions

If this is right

  • The memory needed to decide joint measurability by semidefinite programming can be capped: instead of storing $o^m$ parent elements, one may search over parents with at most $d^2(m(o-1)+1)$ non-zero elements.
  • Every EPR-steering assemblage that admits a local-hidden-state model has a model with at most $d^2(m(o-1)+1)$ hidden states, because the steering-to-compatibility map preserves the parent size.
  • A single $o$-outcome parent measurement is automatically a parent for many children: all the distinct partitions of its outcomes, of which there are $B_o-2$, the Bell number minus the two trivial partitions.
  • In small cases the upper bound is not tight and exponential parents are genuinely needed: the two-outcome qubit pair needs its full four-element parent, and the three-outcome qutrit triple needs all eight elements.
  • In parameter regimes where the bound is tight, typical interior compatible sets are maximally complex, while on the boundary the sampled complexity is spread over many values, indicating a rich boundary structure.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If the constant $d^2$ can be lowered by using the affine dimension of the joint-measurability set rather than its cone dimension, the linear bound would carry over to those smaller constants; the paper's geometry suggests the bound is not an accident of the particular embedding.
  • The memory-time trade-off indicates a potential parallel strategy: enumerate sparsity patterns independently, so compatibility of large sets could be attacked by many small SDPs running in parallel rather than one huge SDP.
  • The probabilistic-parent example hints at a more general trade-off between randomisation and parent size; one could test whether the minimum deterministic parent size and the minimum probabilistic parent size are separated by a constant factor or grow with $m$.
  • One could use the same SDP-duality witness technique to study complexity beyond the small examples, for instance to map the regions of $m,o,d$ where the bound is tight, which the paper leaves open.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

0 major / 7 minor

Summary. The manuscript investigates the minimal number of non-vanishing POVM elements required for a parent measurement of a set of jointly measurable measurements. The authors recall the canonical parent with o^m outcomes and prove in Appendix B that every set of m measurements with o outcomes on C^d admits a parent with at most d^2(m(o-1)+1) non-vanishing elements (Eq. (9)), a bound linear in m. They exhibit simple cases, including the noisy X/Z qubit pair and a qutrit example with m=3 and o=2, where the maximal number o^m of parent elements is necessary; the latter is certified by dual SDP witnesses. They also construct large compatible sets from partitions of a single parent, report numerical sampling of boundary complexity, translate the parent bound into a bound on hidden states in EPR-steering LHS models, and introduce probabilistic parents that can reduce parent size below the deterministic complexity.

Significance. If the main bound is valid, the result is a significant structural contribution: it replaces the naive exponential upper bound o^m on parent size with a linear-in-m bound, and it gives a concrete upper bound that can guide SDP-based searches for parent measurements. The proof is an elementary, parameter-free Carathéodory reduction, and the paper also provides explicitly checkable dual certificates for the small examples, together with an accompanying notebook for the numerical parts. The steering application is constructive and the resulting LHS bound is a useful byproduct. The paper opens a new set of questions about typical and worst-case parent complexity; the SDP-witness technique for proving lower bounds on parent size is likely to be reusable.

minor comments (7)
  1. [Appendix B, Eqs. (27)-(30)] The proof of the bound should explicitly state that the linear dependence is taken in the full space R^D including the d^2 identity coordinates, and that the vector lambda_a is chosen so that max_a lambda_a > 0. As printed, Eq. (27) displays only the child constraints and Eq. (30) silently assumes a positive maximum; the intended argument is correct, but these details should be made explicit.
  2. [Appendix A, Eq. (21)] The expression for omega^{a*} contains what appears to be a duplicated additive term; as printed, a reader cannot verify the feasibility conditions (23) or the negative values in (25). Please correct the formula and, if space allows, include the explicit verification of the claimed inequalities.
  3. [Appendix A, Eq. (15)] The set O(N) is used where O(C) is meant in two of the displayed constraints; this typo should be fixed so that the SDP is stated consistently.
  4. [Probabilistic Parents, Eq. (11)] The sentence 'Indeed, {K1,K2,K3} is a valid POVM' should refer to {K0,K1,K2}, since K2 is defined as the complement of K0 and K1.
  5. [Figure 1 and Appendix C] The histograms of boundary complexity are based on 1000 sampled points with no error bars or convergence checks; a brief statement about sampling uncertainty would make the numerical claim more precise.
  6. [Complexity of typical measurements] The assertion that typical compatible measurements 'will live in the interior' and hence require conic combinations of D points 'and not fewer' is heuristic; it should be labelled as an observation or conjecture rather than a proven statement.
  7. [Throughout] There are several typographical errors and inconsistent superscript and equation-number formatting (e.g., 'develep' in the main text); a careful proofread is needed before publication.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the main linear bound is proved from Carathéodory's theorem and elementary linear algebra, with no fitted inputs, no renamed predictions, and no load-bearing self-citation.

full rationale

The central claim, the linear upper bound d²(m(o−1)+1) on the number of non-vanishing parent POVM elements, is derived in Appendix B from a convex-cone representation and Carathéodory's theorem. The proof starts from an arbitrary parent with k > D non-vanishing elements, finds a linear dependence among the corresponding vectors in R^D, and constructs a new parent by taking γ = 1/max λ_a so that at least one element is zeroed while all children are preserved. This is a self-contained convex-geometry argument: the input to the argument is the existence of a parent, not the claimed bound, and the reduction does not import any result from the authors' prior work. The examples of maximally complex parents in Eqs. (6)-(8) are certified by explicit SDP dual witnesses, and the numerical sampling in Appendix C is exploratory rather than predictive. The steering application in Appendix D uses the external one-to-one correspondence between incompatibility and steering, but that correspondence is not used to derive the main bound and is not a self-citation of the present authors. No fitted parameter is renamed as a prediction, and no uniqueness theorem is invoked to forbid alternatives. Therefore the paper exhibits no circular derivation chain.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The central upper bound is self-contained and uses no fitted numbers; the examples use explicit hand-chosen operators but no free parameters. The geometric cone reduction and standard SDP duality are the main external ingredients, plus the cited steering correspondence for the LHS transfer.

assumptions (4)
  • standard math Carathéodory's theorem for convex cones
    Used in Appendix B to reduce any parent with more than D elements to one with at most D; a standard result in convex geometry.
  • domain assumption The cone of sub-measurements in R^D has the required pointed-cone structure and the dimension count D=d^2(m(o-1)+1)
    The proof relies on representing parent elements as points in R^D, relaxing normalization with extra identity coordinates, and then applying Carathéodory's theorem; this modeling assumption enters in Appendix B.
  • standard math Weak duality for semidefinite programs
    Appendix A uses feasible dual solutions with negative objective values as certificates that no parent with a given support exists; this is standard SDP duality theory.
  • domain assumption One-to-one correspondence between measurement incompatibility and EPR steering
    Appendix D transfers the parent-size bound to LHS models via the construction in Eq. (34), following the external results cited as [13] and [14].

how reviews work

0 comments
Cite this review

Pith. "Pith review of The complexity of compatible measurements." pith.science (2026). https://pith.science/paper/6HUJHLHL

@misc{pith2026190810085,
  author       = {Pith},
  title        = {Pith review of: The complexity of compatible measurements},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/6HUJHLHL}},
  note         = {Machine review of arXiv:1908.10085}
}
read the original abstract

Measurement incompatibility is one of the basic aspects of quantum theory. Here we study the structure of the set of compatible -- i.e. jointly measurable -- measurements. We are interested in whether or not there exist compatible measurements whose parent is maximally complex -- requiring a number of outcomes exponential in the number of measurements, and related questions. Although we show this to be the case in a number of simple scenarios, we show that generically it cannot happen, by proving an upper bound on the number of outcomes of a parent measurement that is linear in the number of compatible measurements. We discuss why this doesn't trivialise the problem of finding parent measurements, but rather shows that a trade-off between memory and time can be achieved. Finally, we also investigate the complexity of extremal compatible measurements in regimes where our bound is not tight, and uncover rich structure.

Figures

Figures reproduced from arXiv: 1908.10085 by the authors.

Figure 1
Figure 1. Histograms showing the distribution of complexity for [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Measurement incompatibility and quantum steering via linear programming

    quant-ph 2025-06 conditional novelty 7.0 of 10

    A hierarchy of linear programs computes provable upper and lower bounds on measurement incompatibility and quantum steering, scaling polynomially with the number of measurements.

Reference graph

Works this paper leans on

20 extracted references · 19 canonical work pages · cited by 1 Pith paper

  1. [1]

    Heisenberg, Z

    W. Heisenberg, Z. Physik 43, 172 (1927)Z. Physik 43, 172 (1927)

    work page 1927

  2. [2]

    Nevertheless, no deterministic parent with 3 outcomes exists for anyη, as previously shown. The nature of the problem of finding probabilistic parents seems much richer than the problem of finding deterministic parents, which has the simple form of a convex optimisation problem. When introducing probabilistic parents, this convex structure is lost, and it s...

    work page 2018

  3. [3]

    Busch, P

    P. Busch, P. J. Lahti, and P. Mittelstaedt, The Quantum Theory of Measurement, 2nd ed., Lecture Notes in Physics Monographs (Springer-Verlag, Berlin Heidelberg, 1996)

    work page 1996

  4. [4]

    Heinosaari, T

    T. Heinosaari, T. Miyadera, and M. Ziman, J. Phys. A: Math. Theor. 49, 123001 (2016)J. Phys. A: Math. Theor. 49, 123001 (2016)

    work page 2016

  5. [5]

    Haapasalo, T

    E. Haapasalo, T. Heinosaari, and J.-P. Pellonp ¨a¨a, Rev. Math. Phys. 26, 1450002 (2014)Rev. Math. Phys. 26, 1450002 (2014)

    work page 2014

  6. [6]

    Guerini and M

    L. Guerini and M. Terra Cunha, Journal of Mathematical Physics 59, 042106 (2018)Journal of Mathematical Physics 59, 042106 (2018)

    work page 2018

  7. [7]

    Boyd and L

    S. Boyd and L. Vandenberghe, Convex Optimization (Cam- bridge University Press, New York, NY , USA, 2004)

    work page 2004

  8. [8]

    E. T. Bell, Amer. Math. Monthly 41, 411 (1934)Amer. Math. Monthly 41, 411 (1934)

    work page 1934

Show all 20 references
  1. [9]

    Carath ´eodory, Math

    C. Carath ´eodory, Math. Ann. 64, 95 (1907)Math. Ann. 64, 95 (1907)

    1907

  2. [10]

    Accompanying notebook available herehere

  3. [11]

    H. M. Wiseman, S. J. Jones, and A. C. Doherty, Phys. Rev. Lett. 98, 140402 (2007)Phys. Rev. Lett. 98, 140402 (2007)

    2007

  4. [12]

    Cavalcanti and P

    D. Cavalcanti and P. Skrzypczyk, Rep. Prog. Phys. 80, 024001 (2017)Rep. Prog. Phys. 80, 024001 (2017)

    2017

  5. [13]

    R. Uola, A. C. S. Costa, H. C. Nguyen, and O. G ¨uhne, arXiv:1903.06663 [math-ph, 6 physics:physics, physics:quant-ph] (2019), arXiv:1903.06663 [math-ph, physics:physics, physics:quant-ph]arXiv:1903.06663 [math-ph, physics:physics, physics:quant-ph]

    2019 arXiv

  6. [14]

    M. T. Quintino, T. V ´ertesi, and N. Brunner, Phys. Rev. Lett. 113, 160402 (2014)Phys. Rev. Lett. 113, 160402 (2014)

    2014

  7. [15]

    R. Uola, T. Moroder, and O. G ¨uhne, Phys. Rev. Lett. 113, 160403 (2014)Phys. Rev. Lett. 113, 160403 (2014). APPENDICES Appendix A: Method for certifying complexity In this appendix we provide details for how one can cer- tify a lower bound on the complexity of a set of compat...

    2014

  8. [16]

    are amplitudes which will be specified shortly. Direct substitution shows that for any choice of (αa∗ 2,β a∗ 2,γ a∗ 2), for all a∗, ωa∗ + ∑ x Da(0|x)ρa∗ 0x≥ 0 ∀a⁄= a∗, 1≥ tr ∑ x,a⁄=a∗ Da(0|x)ρa∗ 0x + 7 trωa∗ , (23) which shows that ρa∗ 0x and ωa∗ are feasible solutions for the ...

  9. [17]

    This provides the required proof that it is impossible to find a parent for the set of measure- ments (1818) with 7 or fewer elements

    = { (1, 0, 0) if a∗ 2 = 0 ( √ 2 4 , √ 2 4 , √ 3 2 ) if a∗ 2 = 1 (24) leads to tr ∑ x ρa∗ 0xMa|x + trωa∗ = { 4−3 √ 2 80 if a∗ 2 = 0 12−8 √ 6−(−1)a∗ 1 3 √ 2 320 if a∗ 2 = 1 (25) which is negative in all cases. This provides the required proof that it is impossible to find a paren...

  10. [18]

    These sets of measurements will be incompatible with probability one

    Randomly generate m unitary matrices{Ux} according to the Haar measure, and from them definem ideal von- Neumann measurements{{Πa|x}a}x, via their eigen- vector decomposition. These sets of measurements will be incompatible with probability one

  11. [19]

    Using the dual formulation of the SDP for compatibil- ity, extract the dual variables, which geometrically de- fine a random direction in the space of sets of measure- ments

  12. [20]

    This problem is an SDP, and moreover will always find a set of compatible mea- surements on the boundary of the set, due to convexity

    Find the set of compatible measurements{Mx}x which are furthest in this direction. This problem is an SDP, and moreover will always find a set of compatible mea- surements on the boundary of the set, due to convexity. This method thus induces a measure on the boundary of com- p...

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.