Measurement incompatibility and quantum steering via linear programming
Summarize this article with:
AbstractThe problem of deciding whether a set of quantum measurements is jointly measurable is known to be equivalent to determining whether a quantum assemblage is unsteerable. This problem can be formulated as a semidefinite program (SDP). However, the number of variables and constraints in such a formulation grows exponentially with the number of measurements, rendering it intractable for large measurement sets. In this work, we circumvent this problem by transforming the SDP into a hierarchy of linear programs that compute upper and lower bounds on the incompatibility robustness with a complexity that grows polynomially in the number of measurements. The hierarchy is guaranteed to converge and it can be applied to arbitrary measurements – including non-projective POVMs (Positive Operator-Valued Measures) – in arbitrary dimensions. While convergence becomes impractical in high dimensions, in the case of qubits our method reliably provides accurate upper and lower bounds for the incompatibility robustness of sets with several hundred measurements in a short time using a standard laptop. We also apply our methods to qutrits, obtaining non-trivial upper and lower bounds in scenarios that are otherwise intractable using the standard SDP approach, although such bounds are significantly looser than the ones obtained in the qubit case. Finally, we show how our methods can be used to construct local hidden state models for states (i.e., to prove that a state cannot lead to steering under any possible local measurements), or conversely, to certify that a given state exhibits steering; for two-qubit quantum states, our approach is comparable to, and in some cases outperforms, the current best methods.Featured image: Comparison between computational runtime for quantifying measurement incompatibility using the linear programming approach proposed in this work and the standard semidefinite programming approach.Popular summaryIn the classical world, the properties of any system are always assume to be well defined. A classical particle has, at any moment in time, a well-defined position and a well-defined velocity. Or, by looking at a playing card, one can simultaneously tell its value and its suit. However, this is not true in quantum theory. Heisenberg's uncertainty principle states that if a quantum particle has a well-defined position, it cannot have a well-defined value of velocity. Or, if one were to play cards with a quantum deck, it could be that the value and the suit of any card could not be simultaneously known. Within quantum theory, this phenomenon can be formalised by the concept of measurement incompatibility. A set of measurements is incompatible if they cannot be jointly performed, that is, if they cannot all be performed at the same time. Deciding whether any given set of measurements is incompatible is a problem that can be cast as a semidefinite program, which can be solved with the aid of a computer. Although this approach works perfectly well for deciding the incompatibility of sets with few measurements, the size of the resulting program grows exponentially with the number of measurements in the set and thus quickly becomes intractable. In this work, we propose a way to circumvent this scalability problem, that works particularly well for measurements on qubits, i.e., quantum systems of dimension two. The method we propose trades off accuracy for efficiency, and relies on a finite approximation of the space of valid quantum states. Since such a space is particularly simple in dimension two, the method provides remarkably precise answers for sets of more than ~100 measurements, while the standard approach already becomes prohibitive for ~20 measurements. Finally, we also discuss applications of the method for problems related to quantum correlations.► BibTeX data@article{Porto2026measurement, doi = {10.22331/q-2026-06-19-2141}, url = {https://doi.org/10.22331/q-2026-06-19-2141}, title = {Measurement incompatibility and quantum steering via linear programming}, author = {Porto, Lucas E. A. and Designolle, S{\'{e}}bastien and Pokutta, Sebastian and Quintino, Marco T{\'{u}}lio}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {10}, pages = {2141}, month = jun, year = {2026} }► References [1] O. Gühne, E. Haapasalo, T. Kraft, J.-P. Pellonpää, and R. Uola, Colloquium: Incompatible measurements in quantum information science, Rev. Mod. Phys. 95, 011003 (2023), arXiv:2112.06784 [quant-ph]. https://doi.org/10.1103/RevModPhys.95.011003 arXiv:2112.06784 [2] J. S. Bell, On the Einstein-Poldolsky-Rosen paradox, Physics 1, 195–200 (1964). https://cds.cern.ch/record/111654/files/vol1p195-200_001.pdf [3] N. Brunner, D. Cavalcanti, S. Pironio, V. Scarani, and S. Wehner, Bell nonlocality, Rev. Mod. Phys. 86, 419–478 (2014), arXiv:1303.2849 [quant-ph]. https://doi.org/10.1103/RevModPhys.86.419 arXiv:1303.2849 [4] A. Fine, Hidden Variables, Joint Probability, and the Bell Inequalities, Phys. Rev. Lett. 48, 291–295 (1982). https://doi.org/10.1103/PhysRevLett.48.291 [5] M. T. Quintino, J. Bowles, F. Hirsch, and N. Brunner, Incompatible quantum measurements admitting a local-hidden-variable model, Phys. Rev. A 93, 052115 (2016), arXiv:1406.6976 [quant-ph]. https://doi.org/10.1103/PhysRevA.93.052115 arXiv:1406.6976 [6] F. Hirsch, M. T. Quintino, and N. Brunner, Quantum measurement incompatibility does not imply Bell nonlocality, Phys. Rev. A 97, 012129 (2018), arXiv:1707.06960 [quant-ph]. https://doi.org/10.1103/PhysRevA.97.012129 arXiv:1707.06960 [7] E. Bene and T. Vértesi, Measurement incompatibility does not give rise to Bell violation in general, New J. Phys. 20, 013021 (2018), arXiv:1705.10069 [quant-ph]. https://doi.org/10.1088/1367-2630/aa9ca3 arXiv:1705.10069 [8] M. Plávala, O. Gühne, and M. T. Quintino, All Incompatible Measurements on Qubits Lead to Multiparticle Bell Nonlocality, Phys. Rev. Lett. 134, 200201 (2025), arXiv:2403.10564 [quant-ph]. https://doi.org/10.1103/PhysRevLett.134.200201 arXiv:2403.10564 [9] M. T. Quintino, T. Vértesi, and N. Brunner, Joint Measurability, Einstein-Podolsky-Rosen Steering, and Bell Nonlocality, Phys. Rev. Lett. 113, 160402 (2014), arXiv:1406.6976 [quant-ph]. https://doi.org/10.1103/PhysRevLett.113.160402 arXiv:1406.6976 [10] R. Uola, T. Moroder, and O. Gühne, Joint Measurability of Generalized Measurements Implies Classicality, Phys. Rev. Lett. 113, 160403 (2014), arXiv:1407.2224 [quant-ph]. https://doi.org/10.1103/PhysRevLett.113.160403 arXiv:1407.2224 [11] R. Uola, A. C. S. Costa, H. C. Nguyen, and O. Gühne, Quantum steering, Rev. Mod. Phys. 92, 015001 (2020), arXiv:1903.06663 [quant-ph]. https://doi.org/10.1103/RevModPhys.92.015001 arXiv:1903.06663 [12] F. Buscemi, E. Chitambar, and W. Zhou, Complete Resource Theory of Quantum Incompatibility as Quantum Programmability, Phys. Rev. Lett. 124, 120401 (2020), arXiv:1908.11274 [quant-ph]. https://doi.org/10.1103/PhysRevLett.124.120401 arXiv:1908.11274 [13] C. Carmeli, T. Heinosaari, and A. Toigo, Quantum Incompatibility Witnesses, Phys. Rev. Lett. 122, 130402 (2019), arXiv:1812.02985 [quant-ph]. https://doi.org/10.1103/PhysRevLett.122.130402 arXiv:1812.02985 [14] L. Guerini, M. T. Quintino, and L. Aolita, Distributed sampling, quantum communication witnesses, and measurement incompatibility, Phys. Rev. A 100, 042308 (2019), arXiv:1904.08435 [quant-ph]. https://doi.org/10.1103/PhysRevA.100.042308 arXiv:1904.08435 [15] A. Acín, N. Brunner, N. Gisin, S. Massar, S. Pironio, and V. Scarani, Device-Independent Security of Quantum Cryptography against Collective Attacks, Phys. Rev. Lett. 98, 230501 (2007), arXiv:1705.10069 [quant-ph]. https://doi.org/10.1103/PhysRevLett.98.230501 arXiv:1705.10069 [16] P. Skrzypczyk, I. Šupić, and D. Cavalcanti, All Sets of Incompatible Measurements give an Advantage in Quantum State Discrimination, Phys. Rev. Lett. 122, 130403 (2019), arXiv:1901.00816 [quant-ph]. https://doi.org/10.1103/PhysRevLett.122.130403 arXiv:1901.00816 [17] C. Carmeli, T. Heinosaari, and A. Toigo, State discrimination with postmeasurement information and incompatibility of quantum measurements, Phys. Rev. A 98, 012126 (2018), arXiv:1804.09693 [quant-ph]. https://doi.org/10.1103/PhysRevA.98.012126 arXiv:1804.09693 [18] B. Schumacher and M. Westmoreland, Quantum Processes Systems, and Information (Cambridge University Press, 2010). https://doi.org/10.1017/CBO9780511814006 [19] P. Busch, Unsharp reality and joint measurements for spin observables, Phys. Rev. D 33, 2253–2261 (1986). https://doi.org/10.1103/PhysRevD.33.2253 [20] S. Yu, N. Liu, L. Li, and C. H. Oh, Joint measurement of two unsharp observables of a qubit, arXiv:0805.1538 (2008). arXiv:0805.1538 [21] P. Busch and H.-J. Schmidt, Coexistence of qubit effects, Quantum Information Processing 9, 143–169 (2010), arXiv:0802.4167 [quant-ph]. https://doi.org/10.1007/s11128-009-0109-x arXiv:0802.4167 [22] P. Stano, D. Reitzner, and T. Heinosaari, Coexistence of qubit effects, Phys. Rev. A 78, 012315 (2008), arXiv:0802.4248 [quant-ph]. https://doi.org/10.1103/PhysRevA.78.012315 arXiv:0802.4248 [23] R. Pal and S. Ghosh, Approximate joint measurement of qubit observables through an Arthur-Kelly model, J. Phys. A: Math. Theor. 44, 485303 (2011), arXiv:1010.2878 [quant-ph]. https://doi.org/10.1088/1751-8113/44/48/485303 arXiv:1010.2878 [24] S. Yu and C. H. Oh, Quantum contextuality and joint measurement of three observables of a qubit, arXiv:1312.6470 (2013). arXiv:1312.6470 [25] D. Grinko and R. Uola, Compatibility of Binary Qubit Measurements, Phys. Rev. Lett. 135, 200201 (2025), arXiv:2407.07711 [quant-ph]. https://doi.org/10.1103/vv1h-5mf9 arXiv:2407.07711 [26] M. M. Wolf, D. Perez-Garcia, and C. Fernandez, Measurements Incompatible in Quantum Theory Cannot Be Measured Jointly in Any Other No-Signaling Theory, Phys. Rev. Lett. 103, 230402 (2009), arXiv:0905.2998 [quant-ph]. https://doi.org/10.1103/PhysRevLett.103.230402 arXiv:0905.2998 [27] D. Cavalcanti and P. Skrzypczyk, Quantitative relations between measurement incompatibility, quantum steering, and nonlocality, Phys. Rev. A 93, 052112 (2016), arXiv:1601.07450 [quant-ph]. https://doi.org/10.1103/PhysRevA.93.052112 arXiv:1601.07450 [28] S. Designolle, M. Farkas, and J. Kaniewski, Incompatibility robustness of quantum measurements: a unified framework, New J. Phys. 21, 113053 (2019), arXiv:1906.00448 [quant-ph]. https://doi.org/10.1088/1367-2630/ab5020 arXiv:1906.00448 [29] H. Fawzi, On Polyhedral Approximations of the Positive Semidefinite Cone, Math. Oper. Res. 46, 1479–1489 (2021), arXiv:2003.00785. https://doi.org/10.1287/moor.2020.1077 arXiv:2003.00785 [30] F. Hirsch, M. T. Quintino, T. Vértesi, M. F. Pusey, and N. Brunner, Algorithmic Construction of Local Hidden Variable Models for Entangled Quantum States, Phys. Rev. Lett. 117, 190402 (2016), arXiv:1512.00262 [quant-ph]. https://doi.org/10.1103/PhysRevLett.117.190402 arXiv:1512.00262 [31] D. Cavalcanti, L. Guerini, R. Rabelo, and P. Skrzypczyk, General Method for Constructing Local Hidden Variable Models for Entangled Quantum States, Phys. Rev. Lett. 117, 190401 (2016), arXiv:1512.00277 [quant-ph]. https://doi.org/10.1103/PhysRevLett.117.190401 arXiv:1512.00277 [32] H. C. Nguyen, H.-V. Nguyen, and O. Gühne, Geometry of Einstein-Podolsky-Rosen Correlations, Phys. Rev. Lett. 122, 240401 (2019), arXiv:1808.09349 [quant-ph]. https://doi.org/10.1103/PhysRevLett.122.240401 arXiv:1808.09349 [33] S. T. Ali, C. Carmeli, T. Heinosaari, and A. Toigo, Commutative POVMs and Fuzzy Observables, Foundations of Physics 39, 593–612 (2009), arXiv:0903.0523 [quant-ph]. https://doi.org/10.1007/s10701-009-9292-y arXiv:0903.0523 [34] R. Uola, C. Budroni, O. Gühne, and J.-P. Pellonpää, One-to-One Mapping between Steering and Joint Measurability Problems, Phys. Rev. Lett. 115, 230402 (2015), arXiv:1507.08633 [quant-ph]. https://doi.org/10.1103/PhysRevLett.115.230402 arXiv:1507.08633 [35] S. Fiorini, S. Massar, S. Pokutta, H. R. Tiwary, and R. de Wolf, Exponential Lower Bounds for Polytopes in Combinatorial Optimization, Journal of the ACM 62, 1–17 (2015), arXiv:1111.0837 [math-CO]. https://doi.org/10.1145/2716307 arXiv:1111.0837 [36] G. Braun, S. Fiorini, S. Pokutta, and D. Steurer, Approximation Limits of Linear Programs (Beyond Hierarchies), Math. Oper. Res. 40, 179–199 (2015), arXiv:1204.0957 [cs.CC]. https://doi.org/10.1287/moor.2014.0694 arXiv:1204.0957 [37] G. Braun and S. Pokutta, The matching polytope does not admit fully-polynomial size relaxation schemes, Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms , 837–846 (2014), arXiv:1403.6710 [cs.CC]. https://doi.org/10.1137/1.9781611973730.57 arXiv:1403.6710 [38] M. Grötschel, L. Lovász, and A. Schrijver, The ellipsoid method and its consequences in combinatorial optimization, Combinatorica 1, 169–197 (1981). https://doi.org/10.1007/BF02579273 [39] F. Alizadeh, Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization, SIAM Journal on Optimization 5, 13–51 (1995). https://doi.org/10.1137/0805002 [40] Y. Nesterov and A. Nemirovskii, Interior-Point Polynomial Algorithms in Convex Programming (Society for Industrial and Applied Mathematics, 1994). https://doi.org/10.1137/1.9781611970791 [41] L. Vandenberghe and S. Boyd, Semidefinite Programming, SIAM Review 38, 49–95 (1996). https://doi.org/10.1137/1038003 [42] G. Aubrun and S. J. Szarek, Alice and Bob Meet Banach: The Interface of Asymptotic Geometric Analysis and Quantum Information Theory, Mathematical Surveys and Monographs, Volume 223 (American Mathematical Society, 2017). https://doi.org/10.1090/surv/223 [43] F. Hirsch, M. T. Quintino, T. Vértesi, M. Navascués, and N. Brunner, Better local hidden variable models for two-qubit Werner states and an upper bound on the Grothendieck constant $K_G(3)$, Quantum 1, 3 (2017), arXiv:1609.06114 [quant-ph]. https://doi.org/10.22331/q-2017-04-25-3 arXiv:1609.06114 [44] J. Renegar, A Mathematical View of Interior-Point Methods in Convex Optimization (Society for Industrial and Applied Mathematics, 2001). https://doi.org/10.1137/1.9780898718812 [45] S. P. Boyd and L. Vandenberghe, Convex Optimization (Cambridge University Press, 2004). https://doi.org/10.1017/CBO9780511804441 [46] G. Chiribella and G. Mauro D’Ariano, Extremal covariant measurements, J. Math. Phys. 47, 092107 (2006), arXiv:quant-ph/0603168 [quant-ph]. https://doi.org/10.1063/1.2349481 arXiv:quant-ph/0603168 [47] J. Renegar, A polynomial-time algorithm, based on Newton's method, for linear programming, Math. Program. 40, 59–93 (1988). https://doi.org/10.1007/BF01580724 [48] S. J. Wright, Primal-Dual Interior-Point Methods (Society for Industrial and Applied Mathematics, 1997). https://doi.org/10.1137/1.9781611971453 [49] R. H. Hardin, J. A. Sloane, and W. D. Smith, Tables of spherical codes with icosahedral symmetry, published electronically at http://NeilSloane.com/icosahedral.codes/ (1994, 2000). http://NeilSloane.com/icosahedral.codes/ [50] S. Lörwald and G. Reinelt, Panda: a software for polyhedral transformations, EURO Journal on Computational Optimization 3, 297–308 (2015). https://doi.org/10.1007/s13675-015-0040-0 [51] P. Skrzypczyk, M. J. Hoban, A. B. Sainz, and N. Linden, Complexity of compatible measurements, Phys. Rev. Res. 2, 023292 (2020), arXiv:1908.10085 [quant-ph]. https://doi.org/10.1103/PhysRevResearch.2.023292 arXiv:1908.10085 [52] T.-A. Ohst, X.-D. Yu, O. Gühne, and C. H. Nguyen, Certifying Quantum Separability with Adaptive Polytopes, SciPost Physics 16, 063 (2024), arXiv:2210.10054 [quant-ph]. https://doi.org/10.21468/SciPostPhys.16.3.063 arXiv:2210.10054 [53] L. Porto, Github repository: Measurement incompatibility and quantum steering via linear programming, https://github.com/lucporto/LpJm (2025). https://github.com/lucporto/LpJm [54] Á. González, Measurement of Areas on a Sphere Using Fibonacci and Latitude-Longitude Lattices, Mathematical Geosciences 42, 49–64 (2010), arXiv:0912.4540 [math.MG]. https://doi.org/10.1007/s11004-009-9257-x arXiv:0912.4540 [55] J. Bavaresco, M. T. Quintino, L. Guerini, T. O. Maciel, D. Cavalcanti, and M. T. Cunha, Most incompatible measurements for robust steering tests, Phys. Rev. A 96, 022110 (2017), arXiv:1704.02994 [quant-ph]. https://doi.org/10.1103/PhysRevA.96.022110 arXiv:1704.02994 [56] R. F. Werner, Quantum states with Einstein-Podolsky-Rosen correlations admitting a hidden-variable model, Phys. Rev. A 40, 4277–4281 (1989). https://doi.org/10.1103/PhysRevA.40.4277 [57] Y. Zhang and E. Chitambar, Exact Steering Bound for Two-Qubit Werner States, Phys. Rev. Lett. 132, 250201 (2024), arXiv:2309.09960 [quant-ph]. https://doi.org/10.1103/PhysRevLett.132.250201 arXiv:2309.09960 [58] M. J. Renner, Compatibility of Generalized Noisy Qubit Measurements, Phys. Rev. Lett. 132, 250202 (2024), arXiv:2309.12290 [quant-ph]. https://doi.org/10.1103/PhysRevLett.132.250202 arXiv:2309.12290 [59] MOSEK ApS, MOSEK Optimizer API for Julia 11.0.20 (2025). https://docs.mosek.com/latest/juliaapi/index.html [60] N. Andrejic and R. Kunjwal, Joint measurability structures realizable with qubit measurements: Incompatibility via marginal surgery, Physical Review Research 2, 043147 (2020), arXiv:2003.00785 [quant-ph]. https://doi.org/10.1103/PhysRevResearch.2.043147 arXiv:2003.00785 [61] M. Araújo, P. Brown, S. Designolle, C. de Gois, Y.-C. Liu, L. Porto, and M. T. Quintino, Ket.jl: a Julia toolbox for quantum information, nonlocality, and entanglement (2025). https://doi.org/10.5281/zenodo.14674642 [62] T. Heinosaari, M. A. Jivulescu, and I. Nechita, Random positive operator valued measures, J. Math. Phys. 61, 042202 (2020), arXiv:1902.04751 [quant-ph]. https://doi.org/10.1063/1.5131028 arXiv:1902.04751 [63] G. Mauro D'Ariano, P. Lo Presti, and P. Perinotti, Classical randomness in quantum measurements, J. Phys. A: Math. Gen. 38, 5979–5991 (2005), arXiv:quant-ph/0408115. https://doi.org/10.1088/0305-4470/38/26/010 arXiv:quant-ph/0408115 [64] D. J. Saunders, S. J. Jones, H. M. Wiseman, and G. J. Pryde, Experimental EPR-steering using Bell-local states, Nature Physics 6, 845–849 (2010), arXiv:0909.0805 [quant-ph]. https://doi.org/10.1038/nphys1766 arXiv:0909.0805 [65] E. G. Cavalcanti, S. J. Jones, H. M. Wiseman, and M. D. Reid, Experimental criteria for steering and the Einstein-Podolsky-Rosen paradox, Phys. Rev. A 80, 032112 (2009), arXiv:0907.1109 [quant-ph]. https://doi.org/10.1103/PhysRevA.80.032112 arXiv:0907.1109 [66] M. T. Quintino, T. Vértesi, D. Cavalcanti, R. Augusiak, M. Demianowicz, A. Acín, and N. Brunner, Inequivalence of entanglement, steering, and Bell nonlocality for general measurements, Phys. Rev. A 92, 032107 (2015), arXiv:1501.03332 [quant-ph]. https://doi.org/10.1103/PhysRevA.92.032107 arXiv:1501.03332 [67] J. Barrett, Nonsequential positive-operator-valued measurements on entangled mixed states do not always violate a Bell inequality, Phys. Rev. A 65, 042302 (2002), arXiv:quant-ph/0107045. https://doi.org/10.1103/PhysRevA.65.042302 arXiv:quant-ph/0107045 [68] H. Chau Nguyen, A. Milne, T. Vu, and S. Jevtic, Quantum steering with positive operator valued measures, J. Phys. A: Math. Gen. 51, 355302 (2018), arXiv:1706.08166 [quant-ph]. https://doi.org/10.1088/1751-8121/aad115 arXiv:1706.08166 [69] S. Designolle, G. Iommazzo, M. Besançon, S. Knebel, P. Gelß, and S. Pokutta, Improved local models and new Bell inequalities via Frank-Wolfe algorithms, Phys. Rev. Res. 5, 043059 (2023), arXiv:2302.04721 [quant-ph]. https://doi.org/10.1103/PhysRevResearch.5.043059 arXiv:2302.04721 [70] S. Designolle, Github repository: Approximation of the set of quantum states via polytopes, https://github.com/sebastiendesignolle/ApproximationQuantumStates (2025). https://github.com/sebastiendesignolle/ApproximationQuantumStates [71] D. Hughes and S. Waldron, Spherical (t,t)-designs with a small number of vectors, Linear Algebra and its Applications 608, 84–106 (2021). https://doi.org/10.1016/j.laa.2020.08.010 [72] H. C. Nguyen, S. Designolle, M. Barakat, and O. Gühne, Symmetries between measurements in quantum mechanics, arXiv:2003.12553 (2020). arXiv:2003.12553 [73] W. K. Wootters and B. D. Fields, Optimal state-determination by mutually unbiased measurements, Annals of Physics 191, 363–381 (1989). https://doi.org/10.1016/0003-4916(89)90322-9 [74] D. McNulty and S. Weigert, Mutually Unbiased Bases in Composite Dimensions – A Review, arXiv:2410.23997 (2024). https://doi.org/10.22331/q-2026-04-01-2051 arXiv:2410.23997 [75] I. Bengtsson and Å. Ericsson, Mutually Unbiased Bases and the Complementarity Polytope, Open Systems & Information Dynamics 12, 107–120 (2005). https://doi.org/10.1007/s11080-005-5721-3Cited byCould not fetch Crossref cited-by data during last attempt 2026-06-19 11:04:20: Could not fetch cited-by data for 10.22331/q-2026-06-19-2141 from Crossref. This is normal if the DOI was registered recently. Could not fetch ADS cited-by data during last attempt 2026-06-19 11:04:21: Cannot retrieve data from ADS due to rate limitations.This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions. AbstractThe problem of deciding whether a set of quantum measurements is jointly measurable is known to be equivalent to determining whether a quantum assemblage is unsteerable. This problem can be formulated as a semidefinite program (SDP). However, the number of variables and constraints in such a formulation grows exponentially with the number of measurements, rendering it intractable for large measurement sets. In this work, we circumvent this problem by transforming the SDP into a hierarchy of linear programs that compute upper and lower bounds on the incompatibility robustness with a complexity that grows polynomially in the number of measurements. The hierarchy is guaranteed to converge and it can be applied to arbitrary measurements – including non-projective POVMs (Positive Operator-Valued Measures) – in arbitrary dimensions. While convergence becomes impractical in high dimensions, in the case of qubits our method reliably provides accurate upper and lower bounds for the incompatibility robustness of sets with several hundred measurements in a short time using a standard laptop. We also apply our methods to qutrits, obtaining non-trivial upper and lower bounds in scenarios that are otherwise intractable using the standard SDP approach, although such bounds are significantly looser than the ones obtained in the qubit case. Finally, we show how our methods can be used to construct local hidden state models for states (i.e., to prove that a state cannot lead to steering under any possible local measurements), or conversely, to certify that a given state exhibits steering; for two-qubit quantum states, our approach is comparable to, and in some cases outperforms, the current best methods.Featured image: Comparison between computational runtime for quantifying measurement incompatibility using the linear programming approach proposed in this work and the standard semidefinite programming approach.Popular summaryIn the classical world, the properties of any system are always assume to be well defined. A classical particle has, at any moment in time, a well-defined position and a well-defined velocity. Or, by looking at a playing card, one can simultaneously tell its value and its suit. However, this is not true in quantum theory. Heisenberg's uncertainty principle states that if a quantum particle has a well-defined position, it cannot have a well-defined value of velocity. Or, if one were to play cards with a quantum deck, it could be that the value and the suit of any card could not be simultaneously known. Within quantum theory, this phenomenon can be formalised by the concept of measurement incompatibility. A set of measurements is incompatible if they cannot be jointly performed, that is, if they cannot all be performed at the same time. Deciding whether any given set of measurements is incompatible is a problem that can be cast as a semidefinite program, which can be solved with the aid of a computer. Although this approach works perfectly well for deciding the incompatibility of sets with few measurements, the size of the resulting program grows exponentially with the number of measurements in the set and thus quickly becomes intractable. In this work, we propose a way to circumvent this scalability problem, that works particularly well for measurements on qubits, i.e., quantum systems of dimension two. The method we propose trades off accuracy for efficiency, and relies on a finite approximation of the space of valid quantum states. Since such a space is particularly simple in dimension two, the method provides remarkably precise answers for sets of more than ~100 measurements, while the standard approach already becomes prohibitive for ~20 measurements. Finally, we also discuss applications of the method for problems related to quantum correlations.► BibTeX data@article{Porto2026measurement, doi = {10.22331/q-2026-06-19-2141}, url = {https://doi.org/10.22331/q-2026-06-19-2141}, title = {Measurement incompatibility and quantum steering via linear programming}, author = {Porto, Lucas E. A. and Designolle, S{\'{e}}bastien and Pokutta, Sebastian and Quintino, Marco T{\'{u}}lio}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {10}, pages = {2141}, month = jun, year = {2026} }► References [1] O. Gühne, E. Haapasalo, T. Kraft, J.-P. Pellonpää, and R. Uola, Colloquium: Incompatible measurements in quantum information science, Rev. Mod. Phys. 95, 011003 (2023), arXiv:2112.06784 [quant-ph]. https://doi.org/10.1103/RevModPhys.95.011003 arXiv:2112.06784 [2] J. S. Bell, On the Einstein-Poldolsky-Rosen paradox, Physics 1, 195–200 (1964). https://cds.cern.ch/record/111654/files/vol1p195-200_001.pdf [3] N. Brunner, D. Cavalcanti, S. Pironio, V. Scarani, and S. Wehner, Bell nonlocality, Rev. Mod. Phys. 86, 419–478 (2014), arXiv:1303.2849 [quant-ph]. https://doi.org/10.1103/RevModPhys.86.419 arXiv:1303.2849 [4] A. Fine, Hidden Variables, Joint Probability, and the Bell Inequalities, Phys. Rev. Lett. 48, 291–295 (1982). https://doi.org/10.1103/PhysRevLett.48.291 [5] M. T. Quintino, J. Bowles, F. Hirsch, and N. Brunner, Incompatible quantum measurements admitting a local-hidden-variable model, Phys. Rev. A 93, 052115 (2016), arXiv:1406.6976 [quant-ph]. https://doi.org/10.1103/PhysRevA.93.052115 arXiv:1406.6976 [6] F. Hirsch, M. T. Quintino, and N. Brunner, Quantum measurement incompatibility does not imply Bell nonlocality, Phys. Rev. A 97, 012129 (2018), arXiv:1707.06960 [quant-ph]. https://doi.org/10.1103/PhysRevA.97.012129 arXiv:1707.06960 [7] E. Bene and T. Vértesi, Measurement incompatibility does not give rise to Bell violation in general, New J. Phys. 20, 013021 (2018), arXiv:1705.10069 [quant-ph]. https://doi.org/10.1088/1367-2630/aa9ca3 arXiv:1705.10069 [8] M. Plávala, O. Gühne, and M. T. Quintino, All Incompatible Measurements on Qubits Lead to Multiparticle Bell Nonlocality, Phys. Rev. Lett. 134, 200201 (2025), arXiv:2403.10564 [quant-ph]. https://doi.org/10.1103/PhysRevLett.134.200201 arXiv:2403.10564 [9] M. T. Quintino, T. Vértesi, and N. Brunner, Joint Measurability, Einstein-Podolsky-Rosen Steering, and Bell Nonlocality, Phys. Rev. Lett. 113, 160402 (2014), arXiv:1406.6976 [quant-ph]. https://doi.org/10.1103/PhysRevLett.113.160402 arXiv:1406.6976 [10] R. Uola, T. Moroder, and O. Gühne, Joint Measurability of Generalized Measurements Implies Classicality, Phys. Rev. Lett. 113, 160403 (2014), arXiv:1407.2224 [quant-ph]. https://doi.org/10.1103/PhysRevLett.113.160403 arXiv:1407.2224 [11] R. Uola, A. C. S. Costa, H. C. Nguyen, and O. Gühne, Quantum steering, Rev. Mod. Phys. 92, 015001 (2020), arXiv:1903.06663 [quant-ph]. https://doi.org/10.1103/RevModPhys.92.015001 arXiv:1903.06663 [12] F. Buscemi, E. Chitambar, and W. Zhou, Complete Resource Theory of Quantum Incompatibility as Quantum Programmability, Phys. Rev. Lett. 124, 120401 (2020), arXiv:1908.11274 [quant-ph]. https://doi.org/10.1103/PhysRevLett.124.120401 arXiv:1908.11274 [13] C. Carmeli, T. Heinosaari, and A. Toigo, Quantum Incompatibility Witnesses, Phys. Rev. Lett. 122, 130402 (2019), arXiv:1812.02985 [quant-ph]. https://doi.org/10.1103/PhysRevLett.122.130402 arXiv:1812.02985 [14] L. Guerini, M. T. Quintino, and L. Aolita, Distributed sampling, quantum communication witnesses, and measurement incompatibility, Phys. Rev. A 100, 042308 (2019), arXiv:1904.08435 [quant-ph]. https://doi.org/10.1103/PhysRevA.100.042308 arXiv:1904.08435 [15] A. Acín, N. Brunner, N. Gisin, S. Massar, S. Pironio, and V. Scarani, Device-Independent Security of Quantum Cryptography against Collective Attacks, Phys. Rev. Lett. 98, 230501 (2007), arXiv:1705.10069 [quant-ph]. https://doi.org/10.1103/PhysRevLett.98.230501 arXiv:1705.10069 [16] P. Skrzypczyk, I. Šupić, and D. Cavalcanti, All Sets of Incompatible Measurements give an Advantage in Quantum State Discrimination, Phys. Rev. Lett. 122, 130403 (2019), arXiv:1901.00816 [quant-ph]. https://doi.org/10.1103/PhysRevLett.122.130403 arXiv:1901.00816 [17] C. Carmeli, T. Heinosaari, and A. Toigo, State discrimination with postmeasurement information and incompatibility of quantum measurements, Phys. Rev. A 98, 012126 (2018), arXiv:1804.09693 [quant-ph]. https://doi.org/10.1103/PhysRevA.98.012126 arXiv:1804.09693 [18] B. Schumacher and M. Westmoreland, Quantum Processes Systems, and Information (Cambridge University Press, 2010). https://doi.org/10.1017/CBO9780511814006 [19] P. Busch, Unsharp reality and joint measurements for spin observables, Phys. Rev. D 33, 2253–2261 (1986). https://doi.org/10.1103/PhysRevD.33.2253 [20] S. Yu, N. Liu, L. Li, and C. H. Oh, Joint measurement of two unsharp observables of a qubit, arXiv:0805.1538 (2008). arXiv:0805.1538 [21] P. Busch and H.-J. Schmidt, Coexistence of qubit effects, Quantum Information Processing 9, 143–169 (2010), arXiv:0802.4167 [quant-ph]. https://doi.org/10.1007/s11128-009-0109-x arXiv:0802.4167 [22] P. Stano, D. Reitzner, and T. Heinosaari, Coexistence of qubit effects, Phys. Rev. A 78, 012315 (2008), arXiv:0802.4248 [quant-ph]. https://doi.org/10.1103/PhysRevA.78.012315 arXiv:0802.4248 [23] R. Pal and S. Ghosh, Approximate joint measurement of qubit observables through an Arthur-Kelly model, J. Phys. A: Math. Theor. 44, 485303 (2011), arXiv:1010.2878 [quant-ph]. https://doi.org/10.1088/1751-8113/44/48/485303 arXiv:1010.2878 [24] S. Yu and C. H. Oh, Quantum contextuality and joint measurement of three observables of a qubit, arXiv:1312.6470 (2013). arXiv:1312.6470 [25] D. Grinko and R. Uola, Compatibility of Binary Qubit Measurements, Phys. Rev. Lett. 135, 200201 (2025), arXiv:2407.07711 [quant-ph]. https://doi.org/10.1103/vv1h-5mf9 arXiv:2407.07711 [26] M. M. Wolf, D. Perez-Garcia, and C. Fernandez, Measurements Incompatible in Quantum Theory Cannot Be Measured Jointly in Any Other No-Signaling Theory, Phys. Rev. Lett. 103, 230402 (2009), arXiv:0905.2998 [quant-ph]. https://doi.org/10.1103/PhysRevLett.103.230402 arXiv:0905.2998 [27] D. Cavalcanti and P. Skrzypczyk, Quantitative relations between measurement incompatibility, quantum steering, and nonlocality, Phys. Rev. A 93, 052112 (2016), arXiv:1601.07450 [quant-ph]. https://doi.org/10.1103/PhysRevA.93.052112 arXiv:1601.07450 [28] S. Designolle, M. Farkas, and J. Kaniewski, Incompatibility robustness of quantum measurements: a unified framework, New J. Phys. 21, 113053 (2019), arXiv:1906.00448 [quant-ph]. https://doi.org/10.1088/1367-2630/ab5020 arXiv:1906.00448 [29] H. Fawzi, On Polyhedral Approximations of the Positive Semidefinite Cone, Math. Oper. Res. 46, 1479–1489 (2021), arXiv:2003.00785. https://doi.org/10.1287/moor.2020.1077 arXiv:2003.00785 [30] F. Hirsch, M. T. Quintino, T. Vértesi, M. F. Pusey, and N. Brunner, Algorithmic Construction of Local Hidden Variable Models for Entangled Quantum States, Phys. Rev. Lett. 117, 190402 (2016), arXiv:1512.00262 [quant-ph]. https://doi.org/10.1103/PhysRevLett.117.190402 arXiv:1512.00262 [31] D. Cavalcanti, L. Guerini, R. Rabelo, and P. Skrzypczyk, General Method for Constructing Local Hidden Variable Models for Entangled Quantum States, Phys. Rev. Lett. 117, 190401 (2016), arXiv:1512.00277 [quant-ph]. https://doi.org/10.1103/PhysRevLett.117.190401 arXiv:1512.00277 [32] H. C. Nguyen, H.-V. Nguyen, and O. Gühne, Geometry of Einstein-Podolsky-Rosen Correlations, Phys. Rev. Lett. 122, 240401 (2019), arXiv:1808.09349 [quant-ph]. https://doi.org/10.1103/PhysRevLett.122.240401 arXiv:1808.09349 [33] S. T. Ali, C. Carmeli, T. Heinosaari, and A. Toigo, Commutative POVMs and Fuzzy Observables, Foundations of Physics 39, 593–612 (2009), arXiv:0903.0523 [quant-ph]. https://doi.org/10.1007/s10701-009-9292-y arXiv:0903.0523 [34] R. Uola, C. Budroni, O. Gühne, and J.-P. Pellonpää, One-to-One Mapping between Steering and Joint Measurability Problems, Phys. Rev. Lett. 115, 230402 (2015), arXiv:1507.08633 [quant-ph]. https://doi.org/10.1103/PhysRevLett.115.230402 arXiv:1507.08633 [35] S. Fiorini, S. Massar, S. Pokutta, H. R. Tiwary, and R. de Wolf, Exponential Lower Bounds for Polytopes in Combinatorial Optimization, Journal of the ACM 62, 1–17 (2015), arXiv:1111.0837 [math-CO]. https://doi.org/10.1145/2716307 arXiv:1111.0837 [36] G. Braun, S. Fiorini, S. Pokutta, and D. Steurer, Approximation Limits of Linear Programs (Beyond Hierarchies), Math. Oper. Res. 40, 179–199 (2015), arXiv:1204.0957 [cs.CC]. https://doi.org/10.1287/moor.2014.0694 arXiv:1204.0957 [37] G. Braun and S. Pokutta, The matching polytope does not admit fully-polynomial size relaxation schemes, Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms , 837–846 (2014), arXiv:1403.6710 [cs.CC]. https://doi.org/10.1137/1.9781611973730.57 arXiv:1403.6710 [38] M. Grötschel, L. Lovász, and A. Schrijver, The ellipsoid method and its consequences in combinatorial optimization, Combinatorica 1, 169–197 (1981). https://doi.org/10.1007/BF02579273 [39] F. Alizadeh, Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization, SIAM Journal on Optimization 5, 13–51 (1995). https://doi.org/10.1137/0805002 [40] Y. Nesterov and A. Nemirovskii, Interior-Point Polynomial Algorithms in Convex Programming (Society for Industrial and Applied Mathematics, 1994). https://doi.org/10.1137/1.9781611970791 [41] L. Vandenberghe and S. Boyd, Semidefinite Programming, SIAM Review 38, 49–95 (1996). https://doi.org/10.1137/1038003 [42] G. Aubrun and S. J. Szarek, Alice and Bob Meet Banach: The Interface of Asymptotic Geometric Analysis and Quantum Information Theory, Mathematical Surveys and Monographs, Volume 223 (American Mathematical Society, 2017). https://doi.org/10.1090/surv/223 [43] F. Hirsch, M. T. Quintino, T. Vértesi, M. Navascués, and N. Brunner, Better local hidden variable models for two-qubit Werner states and an upper bound on the Grothendieck constant $K_G(3)$, Quantum 1, 3 (2017), arXiv:1609.06114 [quant-ph]. https://doi.org/10.22331/q-2017-04-25-3 arXiv:1609.06114 [44] J. Renegar, A Mathematical View of Interior-Point Methods in Convex Optimization (Society for Industrial and Applied Mathematics, 2001). https://doi.org/10.1137/1.9780898718812 [45] S. P. Boyd and L. Vandenberghe, Convex Optimization (Cambridge University Press, 2004). https://doi.org/10.1017/CBO9780511804441 [46] G. Chiribella and G. Mauro D’Ariano, Extremal covariant measurements, J. Math. Phys. 47, 092107 (2006), arXiv:quant-ph/0603168 [quant-ph]. https://doi.org/10.1063/1.2349481 arXiv:quant-ph/0603168 [47] J. Renegar, A polynomial-time algorithm, based on Newton's method, for linear programming, Math. Program. 40, 59–93 (1988). https://doi.org/10.1007/BF01580724 [48] S. J. Wright, Primal-Dual Interior-Point Methods (Society for Industrial and Applied Mathematics, 1997). https://doi.org/10.1137/1.9781611971453 [49] R. H. Hardin, J. A. Sloane, and W. D. Smith, Tables of spherical codes with icosahedral symmetry, published electronically at http://NeilSloane.com/icosahedral.codes/ (1994, 2000). http://NeilSloane.com/icosahedral.codes/ [50] S. Lörwald and G. Reinelt, Panda: a software for polyhedral transformations, EURO Journal on Computational Optimization 3, 297–308 (2015). https://doi.org/10.1007/s13675-015-0040-0 [51] P. Skrzypczyk, M. J. Hoban, A. B. Sainz, and N. Linden, Complexity of compatible measurements, Phys. Rev. Res. 2, 023292 (2020), arXiv:1908.10085 [quant-ph]. https://doi.org/10.1103/PhysRevResearch.2.023292 arXiv:1908.10085 [52] T.-A. Ohst, X.-D. Yu, O. Gühne, and C. H. Nguyen, Certifying Quantum Separability with Adaptive Polytopes, SciPost Physics 16, 063 (2024), arXiv:2210.10054 [quant-ph]. https://doi.org/10.21468/SciPostPhys.16.3.063 arXiv:2210.10054 [53] L. Porto, Github repository: Measurement incompatibility and quantum steering via linear programming, https://github.com/lucporto/LpJm (2025). https://github.com/lucporto/LpJm [54] Á. González, Measurement of Areas on a Sphere Using Fibonacci and Latitude-Longitude Lattices, Mathematical Geosciences 42, 49–64 (2010), arXiv:0912.4540 [math.MG]. https://doi.org/10.1007/s11004-009-9257-x arXiv:0912.4540 [55] J. Bavaresco, M. T. Quintino, L. Guerini, T. O. Maciel, D. Cavalcanti, and M. T. Cunha, Most incompatible measurements for robust steering tests, Phys. Rev. A 96, 022110 (2017), arXiv:1704.02994 [quant-ph]. https://doi.org/10.1103/PhysRevA.96.022110 arXiv:1704.02994 [56] R. F. Werner, Quantum states with Einstein-Podolsky-Rosen correlations admitting a hidden-variable model, Phys. Rev. A 40, 4277–4281 (1989). https://doi.org/10.1103/PhysRevA.40.4277 [57] Y. Zhang and E. Chitambar, Exact Steering Bound for Two-Qubit Werner States, Phys. Rev. Lett. 132, 250201 (2024), arXiv:2309.09960 [quant-ph]. https://doi.org/10.1103/PhysRevLett.132.250201 arXiv:2309.09960 [58] M. J. Renner, Compatibility of Generalized Noisy Qubit Measurements, Phys. Rev. Lett. 132, 250202 (2024), arXiv:2309.12290 [quant-ph]. https://doi.org/10.1103/PhysRevLett.132.250202 arXiv:2309.12290 [59] MOSEK ApS, MOSEK Optimizer API for Julia 11.0.20 (2025). https://docs.mosek.com/latest/juliaapi/index.html [60] N. Andrejic and R. Kunjwal, Joint measurability structures realizable with qubit measurements: Incompatibility via marginal surgery, Physical Review Research 2, 043147 (2020), arXiv:2003.00785 [quant-ph]. https://doi.org/10.1103/PhysRevResearch.2.043147 arXiv:2003.00785 [61] M. Araújo, P. Brown, S. Designolle, C. de Gois, Y.-C. Liu, L. Porto, and M. T. Quintino, Ket.jl: a Julia toolbox for quantum information, nonlocality, and entanglement (2025). https://doi.org/10.5281/zenodo.14674642 [62] T. Heinosaari, M. A. Jivulescu, and I. Nechita, Random positive operator valued measures, J. Math. Phys. 61, 042202 (2020), arXiv:1902.04751 [quant-ph]. https://doi.org/10.1063/1.5131028 arXiv:1902.04751 [63] G. Mauro D'Ariano, P. Lo Presti, and P. Perinotti, Classical randomness in quantum measurements, J. Phys. A: Math. Gen. 38, 5979–5991 (2005), arXiv:quant-ph/0408115. https://doi.org/10.1088/0305-4470/38/26/010 arXiv:quant-ph/0408115 [64] D. J. Saunders, S. J. Jones, H. M. Wiseman, and G. J. Pryde, Experimental EPR-steering using Bell-local states, Nature Physics 6, 845–849 (2010), arXiv:0909.0805 [quant-ph]. https://doi.org/10.1038/nphys1766 arXiv:0909.0805 [65] E. G. Cavalcanti, S. J. Jones, H. M. Wiseman, and M. D. Reid, Experimental criteria for steering and the Einstein-Podolsky-Rosen paradox, Phys. Rev. A 80, 032112 (2009), arXiv:0907.1109 [quant-ph]. https://doi.org/10.1103/PhysRevA.80.032112 arXiv:0907.1109 [66] M. T. Quintino, T. Vértesi, D. Cavalcanti, R. Augusiak, M. Demianowicz, A. Acín, and N. Brunner, Inequivalence of entanglement, steering, and Bell nonlocality for general measurements, Phys. Rev. A 92, 032107 (2015), arXiv:1501.03332 [quant-ph]. https://doi.org/10.1103/PhysRevA.92.032107 arXiv:1501.03332 [67] J. Barrett, Nonsequential positive-operator-valued measurements on entangled mixed states do not always violate a Bell inequality, Phys. Rev. A 65, 042302 (2002), arXiv:quant-ph/0107045. https://doi.org/10.1103/PhysRevA.65.042302 arXiv:quant-ph/0107045 [68] H. Chau Nguyen, A. Milne, T. Vu, and S. Jevtic, Quantum steering with positive operator valued measures, J. Phys. A: Math. Gen. 51, 355302 (2018), arXiv:1706.08166 [quant-ph]. https://doi.org/10.1088/1751-8121/aad115 arXiv:1706.08166 [69] S. Designolle, G. Iommazzo, M. Besançon, S. Knebel, P. Gelß, and S. Pokutta, Improved local models and new Bell inequalities via Frank-Wolfe algorithms, Phys. Rev. Res. 5, 043059 (2023), arXiv:2302.04721 [quant-ph]. https://doi.org/10.1103/PhysRevResearch.5.043059 arXiv:2302.04721 [70] S. Designolle, Github repository: Approximation of the set of quantum states via polytopes, https://github.com/sebastiendesignolle/ApproximationQuantumStates (2025). https://github.com/sebastiendesignolle/ApproximationQuantumStates [71] D. Hughes and S. Waldron, Spherical (t,t)-designs with a small number of vectors, Linear Algebra and its Applications 608, 84–106 (2021). https://doi.org/10.1016/j.laa.2020.08.010 [72] H. C. Nguyen, S. Designolle, M. Barakat, and O. Gühne, Symmetries between measurements in quantum mechanics, arXiv:2003.12553 (2020). arXiv:2003.12553 [73] W. K. Wootters and B. D. Fields, Optimal state-determination by mutually unbiased measurements, Annals of Physics 191, 363–381 (1989). https://doi.org/10.1016/0003-4916(89)90322-9 [74] D. McNulty and S. Weigert, Mutually Unbiased Bases in Composite Dimensions – A Review, arXiv:2410.23997 (2024). https://doi.org/10.22331/q-2026-04-01-2051 arXiv:2410.23997 [75] I. Bengtsson and Å. Ericsson, Mutually Unbiased Bases and the Complementarity Polytope, Open Systems & Information Dynamics 12, 107–120 (2005). https://doi.org/10.1007/s11080-005-5721-3Cited byCould not fetch Crossref cited-by data during last attempt 2026-06-19 11:04:20: Could not fetch cited-by data for 10.22331/q-2026-06-19-2141 from Crossref. This is normal if the DOI was registered recently. Could not fetch ADS cited-by data during last attempt 2026-06-19 11:04:21: Cannot retrieve data from ADS due to rate limitations.This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.