A Graph-Theoretic Approach to Quantum Measurement Incompatibility

• URL: http://arxiv.org/abs/2511.15954v1
• Date: Thu, 20 Nov 2025 01:06:46 GMT
• Title: A Graph-Theoretic Approach to Quantum Measurement Incompatibility
• Abstract summary: We develop a graph-theoretic framework for quantifying measurement incompatibility.<n>We show that the Lovsz number yields the correct scaling for $k$-body Majorana observables.<n>We identify structural conditions under which the robustness is determined.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• Dimension-Free Polylogarithmic Quantum Shadow Tomography from Sequential Pretty-Good Measurements [42.01011095596403]
  We give a quantum protocol for shadow tomography with sample complexity.<n>Our approach first reduces the general shadow-tomography problem to a finite-ensemble estimation problem.<n>A refined tail analysis of the resulting estimation error yields simultaneous accuracy guarantees for all observables.
  arXiv  Detail & Related papers  (2026-08-06T17:51:13Z)
• Fun with Graph States: Nonlocal Bell Pairs and the Arf Invariant [0.7568725564300122]
  We study inner products and partial amplitudes of graph states, which are specified by graphs.<n>Results may illuminate the quantum advantage in the framework of Measurement-Based Quantum Computation.
  arXiv  Detail & Related papers  (2026-06-04T18:00:01Z)
• Entanglement of multi-qubit quantum graph states and studies structural properties of tripartite graphs with quantum programming [0.0]
  We propose a method for constructing multi-qubit entangled quantum states representing weighted tripartite graphs.<n>An expression for the entanglement distance for multi-qubit states corresponding to arbitrary tripartite graph structures is obtained.
  arXiv  Detail & Related papers  (2026-04-30T13:18:04Z)
• Typical entanglement in anyon chains: Page curves beyond Lie group symmetries [41.99844472131922]
  We study bipartite entanglement statistics in one-dimensional anyon chains constrained by fusion rules of unitary pre-modular categories.<n>Surprisingly, despite the constrained Hilbert space structure, the large $L$ expansion has no universal $O(sqrtL)$ or $O(1)$ symmetry-type corrections.<n> Numerical simulations of the integrable and quantum-chaotic golden chain Hamiltonian show that chaotic mid-spectrum eigenstates match the Haar-random predictions.
  arXiv  Detail & Related papers  (2026-03-26T18:00:03Z)
• Quantum Graph Theory by Example [0.0]
  We present a collection of non-trivial quantum graphs that can be thought of in discrete terms.<n>The examples arise as the quantum graphs acted on by increasingly smaller classical matrix groups.<n>We give exact formulas or establish bounds for quantum graph parameters.
  arXiv  Detail & Related papers  (2026-03-24T18:51:14Z)
• Quantum Algorithms for Approximate Graph Isomorphism Testing [0.0]
  We study the quantum query complexity of approximate graph isomorphism testing.<n>We present a quantum algorithm based on MNRS quantum walk search over the product graph $(G,H)$ of the two input graphs.
  arXiv  Detail & Related papers  (2026-03-03T06:43:41Z)
• Symmetric and Antisymmetric Quantum States from Graph Structure and Orientation [0.0]
  We prove that a graph state is fully symmetric under particle permutations if and only if the underlying graph is complete.<n>We show that complete directed graphs endowed with appropriate orientations, for an odd number of qudits generate fully antisymmetric multipartite states.
  arXiv  Detail & Related papers  (2026-01-27T18:12:52Z)
• QGraphLIME - Explaining Quantum Graph Neural Networks [0.48998185508205744]
  Quantum graph neural networks offer a powerful paradigm for learning on graph-structured data.<n>QuantumGraphLIME treats model explanations as distributions over local surrogates fit on structure-preserving perturbations of a graph.
  arXiv  Detail & Related papers  (2025-10-07T08:39:13Z)
• Entanglement in Quantum Systems Based on Directed Graphs [0.0]
  We investigate entanglement properties of quantum states associated with directed graphs.<n>Using a measure derived from the Fubini-Study metric, we quantitatively relate multipartite entanglement to the local connectivity of the graph.
  arXiv  Detail & Related papers  (2025-09-05T16:17:03Z)
• Entanglement Classification in the Graph States: The generalization to $n$-Qubits States using the Entanglement Matrix [0.0]
  Graph states represent a significant class of multi-partite entangled quantum states with applications in quantum error correction, quantum communication, and quantum computation.<n>We introduce a novel formalism called the Entanglement Matrix for quantifying and classifying entanglement in n-qubit graph states.
  arXiv  Detail & Related papers  (2025-07-15T16:30:46Z)
• Grassmann Variational Monte Carlo with neural wave functions [45.935798913942904]
  We formalize the framework introduced by Pfau et al.citepfau2024accurate in terms of Grassmann geometry of the Hilbert space.<n>We validate our approach on the Heisenberg quantum spin model on the square lattice, achieving highly accurate energies and physical observables for a large number of excited states.
  arXiv  Detail & Related papers  (2025-07-14T13:53:13Z)
• Meson spectroscopy of exotic symmetries of Ising criticality in Rydberg atom arrays [39.58317527488534]
  Coupling two Ising chains in a ladder leads to an even richer $mathcalD(1)_8$ symmetries.<n>Here, we probe these emergent symmetries in a Rydberg atom processing unit, leveraging its geometry to realize both chain and ladder configurations.
  arXiv  Detail & Related papers  (2025-06-26T14:19:30Z)
• Many-body quantum resources of graph states [0.0]
  Characterizing the non-classical correlations of a complex many-body system is an important part of quantum technologies. We consider four topologies, namely the star graph states with edges, Tur'an graphs, $r$-ary tree graphs, and square grid cluster states. We characterize many-body entanglement depth in graph states with up to $8$ qubits in $146$ classes non-equivalent under local transformations and graph isomorphisms.
  arXiv  Detail & Related papers  (2024-10-16T12:05:19Z)
• Gaussian Entanglement Measure: Applications to Multipartite Entanglement of Graph States and Bosonic Field Theory [50.24983453990065]
  An entanglement measure based on the Fubini-Study metric has been recently introduced by Cocchiarella and co-workers. We present the Gaussian Entanglement Measure (GEM), a generalization of geometric entanglement measure for multimode Gaussian states. By providing a computable multipartite entanglement measure for systems with a large number of degrees of freedom, we show that our definition can be used to obtain insights into a free bosonic field theory.
  arXiv  Detail & Related papers  (2024-01-31T15:50:50Z)
• Multiscale Dynamic Graph Representation for Biometric Recognition with Occlusions [43.05765549682057]
  Occlusion is a common problem with biometric recognition in the wild. We propose a novel unified framework integrating the merits of both CNNs and graph models.
  arXiv  Detail & Related papers  (2023-07-27T04:18:08Z)
• Spectral clustering under degree heterogeneity: a case for the random walk Laplacian [83.79286663107845]
  This paper shows that graph spectral embedding using the random walk Laplacian produces vector representations which are completely corrected for node degree. In the special case of a degree-corrected block model, the embedding concentrates about K distinct points, representing communities.
  arXiv  Detail & Related papers  (2021-05-03T16:36:27Z)
• Graph-Theoretic Framework for Self-Testing in Bell Scenarios [37.067444579637076]
  Quantum self-testing is the task of certifying quantum states and measurements using the output statistics solely. We present a new approach for quantum self-testing in Bell non-locality scenarios.
  arXiv  Detail & Related papers  (2021-04-27T08:15:01Z)
• Block-Approximated Exponential Random Graphs [77.4792558024487]
  An important challenge in the field of exponential random graphs (ERGs) is the fitting of non-trivial ERGs on large graphs. We propose an approximative framework to such non-trivial ERGs that result in dyadic independence (i.e., edge independent) distributions. Our methods are scalable to sparse graphs consisting of millions of nodes.
  arXiv  Detail & Related papers  (2020-02-14T11:42:16Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.