Graph-Theoretic Approach to Quantum Correlations

Abstract

Correlations in Bell and noncontextuality inequalities can be expressed as a positive linear combination of probabilities of events. Exclusive events can be represented as adjacent vertices of a graph, so correlations can be associated to a subgraph. We show that the maximum value of the correlations for classical, quantum, and more general theories is the independence number, the Lovász number, and the fractional packing number of this subgraph, respectively. We also show that, for any graph, there is always a correlation experiment such that the set of quantum probabilities is exactly the Grötschel-Lovász-Schrijver theta body. This identifies these combinatorial notions as fundamental physical objects and provides a method for singling out experiments with quantum correlations on demand.

REVTeX4, 6 pages, 1 figure. See also arXiv:1010.2163

References in corpus (23)

• Information Causality as a Physical Principle
• A convergent hierarchy of semidefinite programs characterizing the set of quantum correlations
• A simple test for hidden variables in spin-1 system
• Bounding the set of quantum correlations
• Experimentally testable state-independent quantum contextuality
• State-independent experimental test of quantum contextuality
• Experimental non-classicality of an indivisible quantum system
• Specker's Parable of the Over-protective Seer: A Road to Contextuality, Nonlocality and Complementarity (PLUS AN ERRATUM)
• State-independent proof of Kochen-Specker theorem with 13 rays
• State-independent quantum contextuality with single photons
• A glance beyond the quantum model
• Preparation contextuality powers parity-oblivious multiplexing
• Simple explanation of the quantum violation of a fundamental inequality
• All noncontextuality inequalities for the n-cycle scenario
• Universality of state-independent violation of correlation inequalities for noncontextual theories
• State-independent experimental tests of quantum contextuality in a three dimensional system
• Experimental implementation of a Kochen-Specker set of quantum tests
• Generalized monogamy of contextual inequalities from the no-disturbance principle
• Proposed experiment for testing quantum contextuality with neutrons
• Optimal inequalities for state-independent contextuality
• Quantum Correlations are Tightly Bound by the Exclusivity Principle
• Pentagrams and paradoxes
• Bell inequalities for the simplest exclusivity graph

Cited by in corpus (199)

• The Variational Quantum Eigensolver: a review of methods and best practices
• Contextuality supplies the magic for quantum computation
• Is the quantum state real? An extended review of $\psi$-ontology theorems
• Almost quantum correlations
• Kochen-Specker Contextuality
• Wigner function negativity and contextuality in quantum computation on rebits
• Contextuality and Wigner function negativity in qubit quantum computation
• Randomness in Quantum Mechanics: Philosophy, Physics and Technology
• Necessary and Sufficient Conditions for Extended Noncontextuality in a Broad Class of Quantum Mechanical Systems
• From the Kochen-Specker theorem to noncontextuality inequalities without assuming determinism
• Entanglement: Quantum or Classical?
• Applying the simplest Kochen-Specker set for quantum information processing
• Fundamental monogamy relation between contextuality and nonlocality
• Equivalence between contextuality and negativity of the Wigner function for qudits
• State independent contextuality advances one-way communication
• Robust self-testing of quantum systems via noncontextuality inequalities
• Simple method for experimentally testing any form of quantum contextuality
• Machine Learning meets Quantum Foundations: A Brief Survey
• $\psi$-epistemic models are exponentially bad at explaining the distinguishability of quantum states
• Semidefinite programming relaxations for quantum correlations
• No Return to Classical Reality
• Kochen-Specker set with seven contexts
• Necessary and sufficient condition for quantum state-independent contextuality
• The exclusivity principle forbids sets of correlations larger than the quantum set
• Quantum Advantage from Sequential-Transformation Contextuality
• Quantum contextuality provides communication complexity advantage
• Information complementarity: A new paradigm for decoding quantum incompatibility
• Converting contextuality into nonlocality
• Contextuality Test of the Nonclassicality of Variational Quantum Eigensolvers
• Resource theory of contextuality for arbitrary prepare-and-measure experiments
• What does an experimental test of quantum contextuality prove or disprove?
• Noncontextual wirings
• Leggett-Garg macrorealism and the quantum nondisturbance conditions
• Necessary and sufficient condition for contextuality from incompatibility
• Contextuality and Wigner negativity are equivalent for continuous-variable quantum measurements
• Quantum Experiments and Hypergraphs: Multi-Photon Sources for Quantum Interference, Quantum Computation and Quantum Entanglement
• Synchronous observation of Bell nonlocality and state-dependent Kochen-Specker contextuality
• From statistical proofs of the Kochen-Specker theorem to noise-robust noncontextuality inequalities
• Dilation of states and processes in operational-probabilistic theories
• Quantum probabilities as Dempster-Shafer probabilities in the lattice of subspaces
• One-Shot Manipulation of Dynamical Quantum Resources
• Unified approach to contextuality, non-locality, and temporal correlations
• Classical causal models for Bell and Kochen-Specker inequality violations require fine-tuning
• Noisy intermediate-scale quantum algorithm for semidefinite programming
• Minimal true-implies-false and true-implies-true sets of propositions in noncontextual hidden variable theories
• Quantum key distribution protocol based on contextuality monogamy
• Deriving robust noncontextuality inequalities from algebraic proofs of the Kochen-Specker theorem: the Peres-Mermin square
• Simple explanation of the quantum limits of genuine $n$-body nonlocality
• Quantum correlations from simple assumptions
• Proof of the Peres conjecture for contextuality
• Multigraph approach to quantum non-locality
• Contextual Subspace Variational Quantum Eigensolver
• Exclusivity principle and the quantum bound of the Bell inequality
• General Hardy-Type Paradox Based on Bell inequality and its Experimental Test
• Semi-definite programming and quantum information
• Quantum Contextuality
• Quantum theory allows for absolute maximal contextuality
• Uncertainty relations from graph theory
• Probing the limits of correlations in an indivisible quantum system
• Coherence and contextuality in a Mach-Zehnder interferometer
• Quantum Advantage in Information Retrieval
• Quantum computational advantage with string order parameters of 1D symmetry-protected topological order
• Quantum prescriptions are more ontologically distinct than they are operationally distinguishable
• No quantum realization of extremal no-signaling boxes
• Contextuality-by-Default description of Bell tests: Contextuality as the rule not as an exception
• Beyond the Cabello-Severini-Winter framework: Making sense of contextuality without sharpness of measurements
• Contextual inferences, nonlocality, and the incompleteness of quantum mechanics
• Contextuality bounds the efficiency of classical simulation of quantum processes
• Sum-of-squares decompositions for a family of noncontextuality inequalities and self-testing of quantum devices
• Inequalities witnessing coherence, nonlocality, and contextuality
• Classical Simulation of Noncontextual Pauli Hamiltonians
• Gadget structures in proofs of the Kochen-Specker theorem
• Graph-theoretic strengths of contextuality
• Quantum-Inspired Hierarchy for Rank-Constrained Optimization
• Noncontextuality Inequalities from Antidistinguishability
• Contextuality and The Single-Qubit Stabilizer Formalism
• Authentication protocol based on collective quantum steering
• What makes quantum clicks special?
• Neither Contextuality nor Nonlocality Admits Catalysts
• A comonadic view of simulation and quantum resources
• Incompatibility of observables, channels and instruments in information theories
• Testing noncontextuality inequalities that are building blocks of quantum correlations
• Non-locality, contextuality and valuation algebras: a general theory of disagreement
• Necessary Conditions for Extended Noncontextuality in General Sets of Random Variables
• Contextuality as a Precondition for Quantum Entanglement
• Bell non-locality and Kochen-Specker contextuality: How are they connected?
• Graph-Theoretic Framework for Self-Testing in Bell Scenarios
• Extensions of Hardy-type true-implies-false gadgets to classically obtain indistinguishability
• A mathematical framework for operational fine tunings
• Reformulating noncontextuality inequalities in an operational approach
• Experimental Control of the Degree of Non-Classicality via Quantum Coherence
• Separability, Contextuality, and the Quantum Frame Problem
• Faithful orthogonal representations of graphs from partition logics
• Bounding the joint numerical range of Pauli strings by graph parameters
• Quantum advantages of communication complexity from Bell nonlocality
• Characterising the Performance of XOR Games and the Shannon Capacity of Graphs
• On Measures and Measurements: a Fibre Bundle approach to Contextuality
• Unified framework for quantumness -- coherence, discord, and entanglement
• Hypergraph framework for irreducible noncontextuality inequalities from logical proofs of the Kochen-Specker theorem
• Testing quantum theory by generalizing noncontextuality
• Graph Picture of Linear Quantum Networks and Entanglement
• Divisible quantum dynamics satisfies temporal Tsirelson's bound
• Topological contextuality and anyonic statistics of photonic-encoded parafermions
• Equivalence between face nonsignaling correlations, full nonlocality, all-versus-nothing proofs, and pseudotelepathy
• Contextuality, Fine-Tuning, and Teleological Explanation
• Implications of quantum automata for contextuality
• Graph Approach to Extended Contextuality
• Contextuality in composite systems: the role of entanglement in the Kochen-Specker theorem
• Contextuality and bundle diagrams
• Certified randomness in tight space
• Contextual bound states for qudit magic state distillation
• Measurable criteria of generalized non-locality under the correlation symmetry
• Experimental demonstration of the connection between quantum contextuality and graph theory
• Orthogonal Representations, Projective Rank, and Fractional Minimum Positive Semidefinite Rank: Connections and New Directions
• John Bell and the Nature of the Quantum World
• Experimental test of high-dimensional quantum contextuality based on contextuality concentration
• Contextuality beyond the Kochen-Specker theorem
• Hypergraph Contextuality
• Contextuality and noncommutative geometry in quantum mechanics
• Contextuality of Identical Particles
• Corrected Bell and Noncontextuality Inequalities for Realistic Experiments
• Local certification of programmable quantum devices of arbitrary high dimensionality
• Uncertainty relations from state polynomial optimization
• Deciding the existence of perfect entangled strategies for nonlocal games
• Violation of Bell inequality based on $S_4$ symmetry
• Roots and (re)sources of value (in)definiteness versus contextuality. A contribution to the Pitowsky Volume in memory of Itamar Pitowsky (1950--2010)
• Probabilistic inequalities and measurements in bipartite systems
• Large violations in Kochen Specker contextuality and their applications
• Closing Bell: Boxing black box simulations in the resource theory of contextuality
• State-independent quantum contextuality with projectors of nonunit rank
• Entropic No-Disturbance as a Physical Principle
• Breaking of Bell inequalities from $S_4$ symmetry: the three orbits case
• The Exclusivity Principle and the Set of Quantum Correlations
• On the origin of nonclassicality in single systems
• Classical Limits and Contextuality in a Scenario of Multiple Observers
• Revealing quantum contextuality using a single measurement device
• Continuous-variable nonlocality and contextuality
• From the problem of Future Contingents to Peres-Mermin square experiments: An introductory review to Contextuality
• The Golay codes and Quantum Contextuality
• Quantum sets of the multicolored-graph approach to contextuality
• Non-classical Correlations in n-Cycle Setting
• The problem of quantum correlations and the totalitarian principle
• The simplest Kochen-Specker set
• A Logical Proof of Quantum Correlations Requiring Entanglement Measurements
• Experimental Quantum Advantage in the Odd-Cycle Game
• Certifying nonstabilizerness in quantum processors
• All two-party facet Bell inequalities are violated by Almost Quantum correlations
• Morphophoric POVMs, generalised qplexes, and 2-designs
• Quantum correlations with a gap between the sequential and spatial cases
• Violating the KCBS inequality with a toy mechanism
• Optimal Measurement Structures for Contextuality Applications
• Bosonic Indistinguishability-Dependent Contextuality
• Note on Güney-Hillery approach to Bell inequalities
• Inconsistency of a realistic interpretation of quantum measurements: A simple example
• Wigner and friends, a map is not the territory! Contextuality in multi-agent paradoxes
• Tsirelson inequalities: Detecting cheating and quantumness in a single framework
• Lifting noncontextuality inequalities
• Generalised Kochen-Specker Theorem for Finite Non-Deterministic Outcome Assignments
• Graphical Framework for Non-Gaussian Quantum States
• Quantum Logic and Quantum Reconstruction
• The many mathematical faces of Mermin's proof of the Kochen-Specker theorem
• Multistage games and Bell scenarios with communication
• Exclusivity graph approach to Instrumental inequalities
• No contextual advantage in non-paradoxical scenarios of two state vector formalism
• Monogamy relations of entropic non-contextual inequalities and their experimental realization
• The quantum maxima for the basic graphs of exclusivity are not reachable in Bell scenarios
• Deterministic Underlying States are incompatible with a Counterfactual account of Lüders' rule
• Generalised Winograd Schema and its Contextuality
• Characterizing high-dimensional quantum contextuality
• Contextuality of Quantum Error-Correcting Codes
• Measuring the Mermin-Peres magic square using an online quantum computer
• Reexamination of the Kochen-Specker theorem: Relaxation of the completeness assumption
• Exclusivity principle and unphysicality of Garg-Mermin correlation
• Exploring the boundary of quantum correlations with a time-domain optical processor
• Unexpected consequences of Post-Quantum theories in the graph-theoretical approach to correlations
• Contemporary Perspectivism as a Framework of Scientific Inquiry in Quantum Mechanics and Beyond
• Quantum Contextual Hypergraphs, Operators, Inequalities, and Applications in Higher Dimensions
• On the One-Shot Zero-Error Classical Capacity of Classical-Quantum Channels Assisted by Quantum Non-signalling Correlations
• Quantum contextuality of a qutrit state
• Graph-theoretic approach to dimension witnessing
• An Entanglement Monotone from the Contextual Fraction
• Maximal Non-Kochen-Specker Sets and a Lower Bound on the Size of Kochen-Specker Sets
• Twenty years of quantum contextuality at USTC
• Trade-off relations between Bell nonlocality and local Kochen-Specker contextuality in generalized Bell scenarios
• Independence and totalness of subspaces in phase space methods
• Atom graph, partial Boolean algebra and quantum contextuality
• Contextuality, Witness of Quantum Weirdness
• An abstract structure determines the contextuality degree of observable-based Kochen-Specker proofs
• How contextuality and antidistinguishability are related
• Quantum Nonlocality Enhanced by Homogenization
• Graph-theoretical Bounds on the Entangled Value of Non-local Games
• Contextuality scenarios arising from networks of stochastic processes
• The Interplay between Quantum Contextuality and Wigner Negativity
• Graph theoretic quantum contextuality and unextendible Product Bases
• All fundamental non-contextuality inequalities are unique
• Detection of $d_1\otimes d_2$ Dimensional Bipartite Entangled State: A Graph Theoretical Approach
• Quantum contextuality from measurement invasiveness
• On random classical marginal problems with applications to quantum information theory
• Differential Geometry of Contextuality