Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2511.15954

A Graph-Theoretic Approach to Quantum Measurement Incompatibility

Daniel McNulty

quant-phmath-phSubmitted Nov 20, 2025• Announced Nov 21, 2025• 1 citation
arXivHTMLPDF

Abstract

Measurement incompatibility--the impossibility of jointly measuring certain quantum observables--is a fundamental resource for quantum information processing. We develop a graph-theoretic framework for quantifying this resource for large families of binary measurements, including Pauli observables on multi-qubit systems and $k$-body Majorana observables on $n$-mode fermionic systems. To each set of observables we associate an anti-commutativity graph, whose vertices represent observables and whose edges indicate pairs that anti-commute. In this representation, the incompatibility robustness--the minimal amount of classical noise required to render the set jointly measurable--becomes a graph invariant. We derive general bounds on this invariant in terms of the Lovász number, clique number, and fractional chromatic number, and show that the Lovász number yields the correct asymptotic scaling for $k$-body Majorana observables. For line graphs $L(G)$, which naturally arise in the characterisation of exactly solvable spin models, we obtain spectral bounds on the robustness expressed through the energy and skew-energy of the underlying graph $G$. These bounds become tight for highly symmetric graphs, leading to closed formulas for several graph families. Finally, we identify structural conditions under which the robustness is determined by a simple function of the graph's maximum degree and the number of vertices and edges, and show that such extremal cases occur only when combinatorial structures such as Hadamard, conference or weighing matrices exist.

Comments
24 pages, 7 figures

Related papers

Optimal Fermionic Joint Measurements for Estimating Non-Commuting Majorana Observables

Daniel McNulty, Susane Calegari, Michał Oszmaniec

An important class of fermionic observables, relevant in tasks such as fermionic partial tomography and estimating energy levels of chemical Hamiltonians, are the binary measurements obtained from the product of anti-commuting Majorana operators. In this work, we investigate efficient estimation strategies of these observables based on a joint measurement which, after classical post-processing, yields all sufficiently unsharp (noisy) Majorana observables of even-degree. By exploiting the symmetry properties of the Majorana observables, as described by the braid group, we show that the incompatibility robustness, i.e., the minimal classical noise necessary for joint measurability, relates to the spectral properties of the Sachdev-Ye-Kitaev (SYK) model. In particular, we show that for an n mode fermionic system, the incompatibility robustness of all degree- 2 k Majorana observables satisfies Θ ( n − k / 2 ) for k ≤ 5 . Furthermore, we present a joint measurement scheme achieving the asymptotically optimal noise, implemented by a small number of fermionic Gaussian unitaries and sampling from the set of all Majorana monomials. Our joint measurement, which can be performed via a randomization over projective measurements, provides rigorous performance guarantees for estimating fermionic observables comparable with fermionic classical shadows.

arXiv:2402.19349•Quantum•Nov 17, 2025•3 citations

Noise robustness of the incompatibility of quantum measurements

Teiko Heinosaari, Jukka Kiukas, Daniel Reitzner

The existence of incompatible measurements is a fundamental phenomenon having no explanation in classical physics. Intuitively, one considers given measurements to be incompatible within a framework of a physical theory, if their simultaneous implementation on a single physical device is prohibited by the theory itself. In the mathematical language of quantum theory, measurements are described by POVMs (positive operator valued measures), and given POVMs are by definition incompatible if they cannot be obtained via coarse-graining from a single common POVM; this notion generalizes noncommutativity of projective measurements. In quantum theory, incompatibility can be regarded as a resource necessary for manifesting phenomena such as Clauser-Horne-Shimony-Holt (CHSH) Bell inequality violations or Einstein-Podolsky-Rosen (EPR) steering which do not have classical explanation. We define operational ways of quantifying this resource via the amount of added classical noise needed to render the measurements compatible, i.e., useless as a resource. In analogy to entanglement measures, we generalize this idea by introducing the concept of incompatibility measure, which is monotone in local operations. In this paper, we restrict our consideration to binary measurements, which are already sufficient to explicitly demonstrate nontrivial features of the theory. In particular, we construct a family of incompatibility monotones operationally quantifying violations of certain scaled versions of the CHSH Bell inequality, prove that they can be computed via a semidefinite program, and show how the noise-based quantities arise as special cases. We also determine maximal violations of the new inequalities, demonstrating how Tsirelson's bound appears as a special case. The resource aspect is further motivated by simple quantum protocols where our incompatibility monotones appear as relevant figures of merit.

arXiv:1501.04554•Physical Review A•Aug 17, 2015•92 citations

Amount of quantum coherence needed for measurement incompatibility

Jukka Kiukas, Daniel McNulty, Juha-Pekka Pellonpää

A pair of quantum observables diagonal in the same ``incoherent'' basis can be measured jointly, so some coherence is obviously required for measurement incompatibility. Here we first observe that coherence in a single observable is linked to the diagonal elements of any observable jointly measurable with it, leading to a general criterion for the coherence needed for incompatibility. Specializing to the case where the second observable is incoherent (diagonal), we develop a concrete method for solving incompatibility problems, tractable even in large systems by analytical bounds, without resorting to numerical optimization. We verify the consistency of our method by a quick proof of the known noise bound for mutually unbiased bases, and apply it to study emergent classicality in the spin-boson model of an $N$-qubit open quantum system. Finally, we formulate our theory in an operational resource-theoretic setting involving ``genuinely incoherent operations'' used previously in the literature, and show that if the coherence is insufficient to sustain incompatibility, the associated joint measurements have sequential implementations via incoherent instruments.

arXiv:2011.07239•Physical Review A•Jan 6, 2022•13 citations

Extreme Observables and Optimal Measurements in Quantum Theory

Erkka Haapasalo

Optimization of quantum measurement processes has a pivotal role in carrying out better, more accurate or less disrupting, measurements and experiments on a quantum system. Especially, convex optimization, i.e., identifying the extreme points of the convex sets and subsets of quantum measuring devices plays an important part in quantum optimization since the typical figures of merit for measuring processes are affine functionals. In this thesis, we discuss results determining the extreme quantum devices and their relevance, e.g., in quantum-compatibility-related questions. Especially, we see that a compatible device pair where one device is extreme can be joined into a single apparatus essentially in a unique way. Moreover, we show that the question whether a pair of quantum observables can be measured jointly can often be formulated in a weaker form when some of the observables involved are extreme. Another major line of research treated in this thesis deals with convex analysis of special restricted quantum device sets, covariance structures or, in particular, generalized imprimitivity systems. Some results on the structure ofcovariant observables and instruments are listed as well as results identifying the extreme points of covariance structures in quantum theory. As a special case study, not published anywhere before, we study the structure of Euclidean-covariant localization observables for spin-0-particles. We also discuss the general form of Weyl-covariant phase-space instruments. Finally, certain optimality measures originating from convex geometry are introduced for quantum devices, namely, boundariness measuring how ‘close’ to the algebraic boundary of the device set a quantum apparatus is and the robustness of incompatibility quantifying the level of incompatibility for a quantum device pair by measuring the highest amount of noise the pair tolerates without becoming compatible. Boundariness is further associated to minimum-error discrimination of quantum devices, and robustness of incompatibility is shown to behave monotonically under certain compatibility-non-decreasing operations. Moreover, the value of robustness of incompatibility is given for a few special device pairs.

•Nov 21, 2015•1 citation

Characterising extremal decoherence by quantum measurement incompatibility

Daniel McNulty, William Townsend, Jukka Kiukas

Decoherence, when viewed in the Heisenberg picture, can turn incompatible measurements into jointly measurable ones. This provides an observable-level description of emergent classicality in terms of the incompatibility destroyed by a noise channel. The corresponding loss of incompatibility can be captured by the channel's \emph{compatibility region}---the observables in a probe class that become jointly measurable with every noisy observable. The geometry and volume of this region provide a refined operational way to compare noise channels. We apply this framework to decoherence channels, each of which acts by Schur multiplication with extreme points of the convex set of unit-diagonal positive semidefinite matrices. Restricting to extremals eliminates convex mixing and reveals subtle phase-dependent decoherence effects thar are not captured by damping rates or conventional coherence quantifiers. Such channels have a rigid dilation structure described by a rank-one operator frame, which reduces joint measurability to a positivity test, making the compatibility region analytically tractable, and its volume computable from the frame's Gram matrix. If the frame can be normalised to a minimal informationally complete (MIC) POVM, the compatibility region acquires a geometric interpretation in the associated probability representation of the quantum state space, familiar with Qbism. Among maximal-rank extremals, those associated with symmetric informationally complete (SIC) POVMs maximise the compatibility volume and hence destroy the greatest amount of incompatibility, providing an operational characterisation of the special role of SICs in terms of joint measurability. This leads to a new formulation of the well-known SIC existence problem as a joint measurability question for noisy mutually unbiased bases.

quant-pharXiv:2607.21169•Jul 24, 2026•0 citations

Compatibility of Pauli Observables

Daniel McNulty, Paolo Facchi A, Saverio Pascazio

Given an arbitrary finite family of Pauli observables, how sharply can they be approximated by a single measurement? We derive an exact state-space correspondence that characterises the resulting sharpness tradeoffs, establishing a link between incompatibility and preparation uncertainty. In particular, suitable ensembles of quantum states determine the full compatibility region and generate explicit parent measurements through Pauli conjugation and classical randomisation. The compatibility region depends only on the anti-commutativity graph and determines all nonuniform tradeoffs under standard noise models, including depolarising, probabilistic and generalised noise. We show that optimal sharpness tradeoffs are determined by spectral problems for signed Pauli Hamiltonians, whose ground states supply the seeds for optimal parent measurements. The correspondence also shows that magic is necessary to attain the full compatibility region of every noncommuting Pauli family. We quantify the resulting sharpness advantage and relate it to the reduced robustness of magic. Finally, we apply the framework to several structured Pauli families, obtaining exact compatibility characterisations and explicit optimal parents.

arXiv:2611.06592•Nov 4, 2026•0 citations
Measurement incompatibility--the impossibility of jointly measuring certain quantum observables--is a fundamental resource for quantum information processing. We develop a graph-theoretic framework for quantifying this resource for large families of binary measurements, including Pauli observables on multi-qubit systems and kkk-body Majorana observables on nnn-mode fermionic systems. To each set of observables we associate an anti-commutativity graph, whose vertices represent observables and whose edges indicate pairs that anti-commute. In this representation, the incompatibility robustness--the minimal amount of classical noise required to render the set jointly measurable--becomes a graph invariant. We derive general bounds on this invariant in terms of the Lovász number, clique number, and fractional chromatic number, and show that the Lovász number yields the correct asymptotic scaling for kkk-body Majorana observables. For line graphs L(G)L(G)L(G), which naturally arise in the characterisation of exactly solvable spin models, we obtain spectral bounds on the robustness expressed through the energy and skew-energy of the underlying graph GGG. These bounds become tight for highly symmetric graphs, leading to closed formulas for several graph families. Finally, we identify structural conditions under which the robustness is determined by a simple function of the graph's maximum degree and the number of vertices and edges, and show that such extremal cases occur only when combinatorial structures such as Hadamard, conference or weighing matrices exist.
An important class of fermionic observables, relevant in tasks such as fermionic partial tomography and estimating energy levels of chemical Hamiltonians, are the binary measurements obtained from the product of anti-commuting Majorana operators. In this work, we investigate efficient estimation strategies of these observables based on a joint measurement which, after classical post-processing, yields all sufficiently unsharp (noisy) Majorana observables of even-degree. By exploiting the symmetry properties of the Majorana observables, as described by the braid group, we show that the incompatibility robustness, i.e., the minimal classical noise necessary for joint measurability, relates to the spectral properties of the Sachdev-Ye-Kitaev (SYK) model. In particular, we show that for an n mode fermionic system, the incompatibility robustness of all degree- 2 k Majorana observables satisfies Θ ( n − k / 2 ) for k ≤ 5 . Furthermore, we present a joint measurement scheme achieving the asymptotically optimal noise, implemented by a small number of fermionic Gaussian unitaries and sampling from the set of all Majorana monomials. Our joint measurement, which can be performed via a randomization over projective measurements, provides rigorous performance guarantees for estimating fermionic observables comparable with fermionic classical shadows.
The existence of incompatible measurements is a fundamental phenomenon having no explanation in classical physics. Intuitively, one considers given measurements to be incompatible within a framework of a physical theory, if their simultaneous implementation on a single physical device is prohibited by the theory itself. In the mathematical language of quantum theory, measurements are described by POVMs (positive operator valued measures), and given POVMs are by definition incompatible if they cannot be obtained via coarse-graining from a single common POVM; this notion generalizes noncommutativity of projective measurements. In quantum theory, incompatibility can be regarded as a resource necessary for manifesting phenomena such as Clauser-Horne-Shimony-Holt (CHSH) Bell inequality violations or Einstein-Podolsky-Rosen (EPR) steering which do not have classical explanation. We define operational ways of quantifying this resource via the amount of added classical noise needed to render the measurements compatible, i.e., useless as a resource. In analogy to entanglement measures, we generalize this idea by introducing the concept of incompatibility measure, which is monotone in local operations. In this paper, we restrict our consideration to binary measurements, which are already sufficient to explicitly demonstrate nontrivial features of the theory. In particular, we construct a family of incompatibility monotones operationally quantifying violations of certain scaled versions of the CHSH Bell inequality, prove that they can be computed via a semidefinite program, and show how the noise-based quantities arise as special cases. We also determine maximal violations of the new inequalities, demonstrating how Tsirelson's bound appears as a special case. The resource aspect is further motivated by simple quantum protocols where our incompatibility monotones appear as relevant figures of merit.
A pair of quantum observables diagonal in the same ``incoherent'' basis can be measured jointly, so some coherence is obviously required for measurement incompatibility. Here we first observe that coherence in a single observable is linked to the diagonal elements of any observable jointly measurable with it, leading to a general criterion for the coherence needed for incompatibility. Specializing to the case where the second observable is incoherent (diagonal), we develop a concrete method for solving incompatibility problems, tractable even in large systems by analytical bounds, without resorting to numerical optimization. We verify the consistency of our method by a quick proof of the known noise bound for mutually unbiased bases, and apply it to study emergent classicality in the spin-boson model of an NNN-qubit open quantum system. Finally, we formulate our theory in an operational resource-theoretic setting involving ``genuinely incoherent operations'' used previously in the literature, and show that if the coherence is insufficient to sustain incompatibility, the associated joint measurements have sequential implementations via incoherent instruments.
Optimization of quantum measurement processes has a pivotal role in carrying out better, more accurate or less disrupting, measurements and experiments on a quantum system. Especially, convex optimization, i.e., identifying the extreme points of the convex sets and subsets of quantum measuring devices plays an important part in quantum optimization since the typical figures of merit for measuring processes are affine functionals. In this thesis, we discuss results determining the extreme quantum devices and their relevance, e.g., in quantum-compatibility-related questions. Especially, we see that a compatible device pair where one device is extreme can be joined into a single apparatus essentially in a unique way. Moreover, we show that the question whether a pair of quantum observables can be measured jointly can often be formulated in a weaker form when some of the observables involved are extreme. Another major line of research treated in this thesis deals with convex analysis of special restricted quantum device sets, covariance structures or, in particular, generalized imprimitivity systems. Some results on the structure ofcovariant observables and instruments are listed as well as results identifying the extreme points of covariance structures in quantum theory. As a special case study, not published anywhere before, we study the structure of Euclidean-covariant localization observables for spin-0-particles. We also discuss the general form of Weyl-covariant phase-space instruments. Finally, certain optimality measures originating from convex geometry are introduced for quantum devices, namely, boundariness measuring how ‘close’ to the algebraic boundary of the device set a quantum apparatus is and the robustness of incompatibility quantifying the level of incompatibility for a quantum device pair by measuring the highest amount of noise the pair tolerates without becoming compatible. Boundariness is further associated to minimum-error discrimination of quantum devices, and robustness of incompatibility is shown to behave monotonically under certain compatibility-non-decreasing operations. Moreover, the value of robustness of incompatibility is given for a few special device pairs.
Decoherence, when viewed in the Heisenberg picture, can turn incompatible measurements into jointly measurable ones. This provides an observable-level description of emergent classicality in terms of the incompatibility destroyed by a noise channel. The corresponding loss of incompatibility can be captured by the channel's \emph{compatibility region}---the observables in a probe class that become jointly measurable with every noisy observable. The geometry and volume of this region provide a refined operational way to compare noise channels. We apply this framework to decoherence channels, each of which acts by Schur multiplication with extreme points of the convex set of unit-diagonal positive semidefinite matrices. Restricting to extremals eliminates convex mixing and reveals subtle phase-dependent decoherence effects thar are not captured by damping rates or conventional coherence quantifiers. Such channels have a rigid dilation structure described by a rank-one operator frame, which reduces joint measurability to a positivity test, making the compatibility region analytically tractable, and its volume computable from the frame's Gram matrix. If the frame can be normalised to a minimal informationally complete (MIC) POVM, the compatibility region acquires a geometric interpretation in the associated probability representation of the quantum state space, familiar with Qbism. Among maximal-rank extremals, those associated with symmetric informationally complete (SIC) POVMs maximise the compatibility volume and hence destroy the greatest amount of incompatibility, providing an operational characterisation of the special role of SICs in terms of joint measurability. This leads to a new formulation of the well-known SIC existence problem as a joint measurability question for noisy mutually unbiased bases.
Given an arbitrary finite family of Pauli observables, how sharply can they be approximated by a single measurement? We derive an exact state-space correspondence that characterises the resulting sharpness tradeoffs, establishing a link between incompatibility and preparation uncertainty. In particular, suitable ensembles of quantum states determine the full compatibility region and generate explicit parent measurements through Pauli conjugation and classical randomisation. The compatibility region depends only on the anti-commutativity graph and determines all nonuniform tradeoffs under standard noise models, including depolarising, probabilistic and generalised noise. We show that optimal sharpness tradeoffs are determined by spectral problems for signed Pauli Hamiltonians, whose ground states supply the seeds for optimal parent measurements. The correspondence also shows that magic is necessary to attain the full compatibility region of every noncommuting Pauli family. We quantify the resulting sharpness advantage and relate it to the reduced robustness of magic. Finally, we apply the framework to several structured Pauli families, obtaining exact compatibility characterisations and explicit optimal parents.