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

Magic Eulerian Hypergraphs

Stefan Trandafir

Published May 8, 2017• 0 citations
OpenAlex

Abstract

Motivated by the phenomenon of contextuality in quantum physics we study a particular family of proofs of the Kochen-Specker theorem.A proof is represented by a pair consisting of a hypergraph where each vertex has even degree, called an Eulerian hypergraph, and a labeling of its vertices.If a hypergraph admits a labeling constituting a proof, we say it is magic.We are interested in determining whether a given hypergraph is magic.Working with the duals of Eulerian hypergraphs, we develop the parity minor relation, which allows us to establish a concept of minimality for the magic property.We introduce a splitting operation to show that certain hypergraphs are not magic.We combine the parity minor relation and the splitting operation in order to search for minimally magic hypergraphs whose duals are grafts, hypergraphs with one edge of size four and all other edges of size two.

Related papers

An abstract structure determines the contextuality degree of observable-based Kochen-Specker proofs

Axel Müller, Alain Giorgetti

This article delves into the concept of quantum contextuality, specifically focusing on proofs of the Kochen-Specker theorem obtained by assigning Pauli observables to hypergraph vertices satisfying a given commutation relation. The abstract structure composed of this hypergraph and the graph of anticommutations is named a hypergram. Its labelings with Pauli observables generalize the well-known magic sets. A first result is that all these correct quantum labelings of a given hypergram inherently possess the same degree of contextuality. Then we provide a necessary and sufficient condition for the existence of such quantum labelings and an efficient algorithm to find one of them. We finally attach to each assignable hypergram an abstract notion of contextuality degree. By presenting the study of observable-based Kochen-Specker proofs from the perspectives of graphs and matrices, this abstraction opens the way to new methods to search for original contextual configurations.

arXiv:2410.14463•Journal of Mathematical Physics•Aug 1, 2025•1 citation

Automated search for highly contextual Kochen-Specker proofs

Axel Muller, Metod Saniga

Observable-based Kochen-Specker proofs are configurations of multi-qubit Pauli observables grouped into contexts whose products are plus or minus the indentity. Their robustness as state-independent contextuality tests can be measured by the tolerated error per context $\varepsilon = 2d/|H|$, where $d$ is the contextuality degree and $|H|$ the number of contexts. Since the degree depends only on an underlying abstract structure called the hypergram i.e. the pair formed by the context hypergraph and the anticommutation graph, the search for highly contextual proofs can be carried out on them instead, with no reference to qubits or to any particular Pauli labeling. We further exploit this by enumerating anticommutation graphs first, and then by associating to each graph $G$ the single hypergram carrying its entire hypergraph support $HS(G)$, so that exactly one candidate is examined per graph. Applied to the House of Graphs database and to censuses of vertex-transitive graphs on at most 24 vertices, this pipeline recovers the Peres-Mermin square, the doily and the Mermin pentagram, and yields configurations reaching $\varepsilon = 0.707$, against $0.424$ for the previous published record. The best configurations are predominantly those stemming from line graphs and unions of graphs; we explain the former by showing that every perfect matching of a graph is a context of its line graph, which exhibits the Peres-Mermin square and the doily as the first members of two infinite families. We close with finite geometric descriptions of the most striking configurations inside symplectic polar spaces, in terms of ovoids, hyperbolic quadrics and Fano planes.

quant-pharXiv:2609.19862•Sep 18, 2026•0 citations

Generation of state-independent contextuality proofs from hypergraphs

Axel Müller, Alain Giorgetti, Метод Санига

We present a new structure, named hypergram, composed of a hypergraph and a graph of anticommutations, and a necessary and sufficient condition for the existence of a labeling of its vertices by Pauli observables which may produce a state-independent Kochen-Specker contextuality proof. Then we present a polynomial algorithm to find such a labeling with the minimal number of qubits. Applying this algorithm to medium-sized hypergraphs produces new contextuality proofs that were beyond the reach of the previous known methods. We also present the Qontextium tool in which this algorithm is implemented.

•Jan 28, 2025•0 citations

Quantum Contextual Hypergraphs, Operators, Inequalities, and Applications in Higher Dimensions

Mladen Pavičić

Quantum contextuality plays a significant role in supporting quantum computation and quantum information theory. The key tools for this are the Kochen-Specker and non-Kochen-Specker contextual sets. Traditionally, their representation has been predominantly operator-based, mainly focusing on specific constructs in dimensions ranging from three to eight. However, nearly all of these constructs can be represented as low-dimensional hypergraphs. This study demonstrates how to generate contextual hypergraphs in any dimension using various methods, particularly those that do not scale in complexity with increasing dimensions. Furthermore, we introduce innovative examples of hypergraphs extending to dimension 32. Our methodology reveals the intricate structural properties of hypergraphs, enabling precise quantifications of contextuality. Additionally, we investigate several promising applications of hypergraphs in quantum communication and quantum computation, paving the way for future breakthroughs in the field.

arXiv:2501.09637•Entropy•Jan 9, 2025•1 citation

An infinite family of Kochen-Specker sets in four-dimensional real spaces

Brandon Elford

Contextuality is a feature differentiating between classical and quantum physics. It is anticipated that it may become an important resource for quantum computing and quantum information processing. Contextuality was asserted by the Kochen-Specker (KS) theorem. We study parity proofs of the KS theorem. Although many parity proofs exist, only finitely many of them have been discovered in any real or complex space of fixed dimension. We study a special family of chordal ring graphs. We construct orthonormal representations of their line graphs in four-dimensional real spaces. Our construction takes advantage of the high degree of symmetry present in the special class of chordal rings that we use. In this way we find, for the first time, an infinite family of KS sets in a fixed dimension.

•Dec 13, 2018•0 citations

Quantumness via Discrete Structures

Ravi Kunjwal

Quantum theory departs from classical probabilistic theories in foundational ways. These departures--termed quantumness here--power quantum information and computation. This thesis charts the role of discrete structures in assessing quantumness, synthesizing elements of my postdoctoral research through this lens. After an introduction to the necessary background concepts, I present my work under three broad categories. First, I present work on contextuality that extensively relies on (undirected) graphs and hypergraphs as the discrete structures of interest; more specifically, it relies on invariants associated with them. This work includes Kochen-Specker (KS) contextuality and its operationalization to generalized contextuality, expressed via (hyper)graph-theoretic frameworks. I also present work on KS-contextuality in multiqubit systems and an application of generalized contextuality to a one-shot communication task, both of which rely on hypergraphs. Second, I present work on causality, where the discrete structures of interest are directed graphs. This includes work on indefinite causal order, specifically its connections to the gap between local operations and classical communication (LOCC) and separable operations (SEP), and a device-independent notion of nonclassicality--termed antinomicity--that generalizes Bell nonlocality without global causal assumptions. Finally, I present work on the incompatibility of quantum measurements, its connection to Bell nonlocality, and its role in discriminating between quantum and almost quantum correlations in the single-system setting. The discrete structures of interest here are hypergraphs that model joint measurability relations between quantum measurements. I conclude with a summary and an overview of work that is not covered in this thesis.

quant-pharXiv:2512.10063•Dec 12, 2025•0 citations
Motivated by the phenomenon of contextuality in quantum physics we study a particular family of proofs of the Kochen-Specker theorem.A proof is represented by a pair consisting of a hypergraph where each vertex has even degree, called an Eulerian hypergraph, and a labeling of its vertices.If a hypergraph admits a labeling constituting a proof, we say it is magic.We are interested in determining whether a given hypergraph is magic.Working with the duals of Eulerian hypergraphs, we develop the parity minor relation, which allows us to establish a concept of minimality for the magic property.We introduce a splitting operation to show that certain hypergraphs are not magic.We combine the parity minor relation and the splitting operation in order to search for minimally magic hypergraphs whose duals are grafts, hypergraphs with one edge of size four and all other edges of size two.
This article delves into the concept of quantum contextuality, specifically focusing on proofs of the Kochen-Specker theorem obtained by assigning Pauli observables to hypergraph vertices satisfying a given commutation relation. The abstract structure composed of this hypergraph and the graph of anticommutations is named a hypergram. Its labelings with Pauli observables generalize the well-known magic sets. A first result is that all these correct quantum labelings of a given hypergram inherently possess the same degree of contextuality. Then we provide a necessary and sufficient condition for the existence of such quantum labelings and an efficient algorithm to find one of them. We finally attach to each assignable hypergram an abstract notion of contextuality degree. By presenting the study of observable-based Kochen-Specker proofs from the perspectives of graphs and matrices, this abstraction opens the way to new methods to search for original contextual configurations.
Observable-based Kochen-Specker proofs are configurations of multi-qubit Pauli observables grouped into contexts whose products are plus or minus the indentity. Their robustness as state-independent contextuality tests can be measured by the tolerated error per context ε=2d/∣H∣\varepsilon = 2d/|H|ε=2d/∣H∣, where ddd is the contextuality degree and ∣H∣|H|∣H∣ the number of contexts. Since the degree depends only on an underlying abstract structure called the hypergram i.e. the pair formed by the context hypergraph and the anticommutation graph, the search for highly contextual proofs can be carried out on them instead, with no reference to qubits or to any particular Pauli labeling. We further exploit this by enumerating anticommutation graphs first, and then by associating to each graph GGG the single hypergram carrying its entire hypergraph support HS(G)HS(G)HS(G), so that exactly one candidate is examined per graph. Applied to the House of Graphs database and to censuses of vertex-transitive graphs on at most 24 vertices, this pipeline recovers the Peres-Mermin square, the doily and the Mermin pentagram, and yields configurations reaching ε=0.707\varepsilon = 0.707ε=0.707, against 0.4240.4240.424 for the previous published record. The best configurations are predominantly those stemming from line graphs and unions of graphs; we explain the former by showing that every perfect matching of a graph is a context of its line graph, which exhibits the Peres-Mermin square and the doily as the first members of two infinite families. We close with finite geometric descriptions of the most striking configurations inside symplectic polar spaces, in terms of ovoids, hyperbolic quadrics and Fano planes.
We present a new structure, named hypergram, composed of a hypergraph and a graph of anticommutations, and a necessary and sufficient condition for the existence of a labeling of its vertices by Pauli observables which may produce a state-independent Kochen-Specker contextuality proof. Then we present a polynomial algorithm to find such a labeling with the minimal number of qubits. Applying this algorithm to medium-sized hypergraphs produces new contextuality proofs that were beyond the reach of the previous known methods. We also present the Qontextium tool in which this algorithm is implemented.
Quantum contextuality plays a significant role in supporting quantum computation and quantum information theory. The key tools for this are the Kochen-Specker and non-Kochen-Specker contextual sets. Traditionally, their representation has been predominantly operator-based, mainly focusing on specific constructs in dimensions ranging from three to eight. However, nearly all of these constructs can be represented as low-dimensional hypergraphs. This study demonstrates how to generate contextual hypergraphs in any dimension using various methods, particularly those that do not scale in complexity with increasing dimensions. Furthermore, we introduce innovative examples of hypergraphs extending to dimension 32. Our methodology reveals the intricate structural properties of hypergraphs, enabling precise quantifications of contextuality. Additionally, we investigate several promising applications of hypergraphs in quantum communication and quantum computation, paving the way for future breakthroughs in the field.
Contextuality is a feature differentiating between classical and quantum physics. It is anticipated that it may become an important resource for quantum computing and quantum information processing. Contextuality was asserted by the Kochen-Specker (KS) theorem. We study parity proofs of the KS theorem. Although many parity proofs exist, only finitely many of them have been discovered in any real or complex space of fixed dimension. We study a special family of chordal ring graphs. We construct orthonormal representations of their line graphs in four-dimensional real spaces. Our construction takes advantage of the high degree of symmetry present in the special class of chordal rings that we use. In this way we find, for the first time, an infinite family of KS sets in a fixed dimension.
Quantum theory departs from classical probabilistic theories in foundational ways. These departures--termed quantumness here--power quantum information and computation. This thesis charts the role of discrete structures in assessing quantumness, synthesizing elements of my postdoctoral research through this lens. After an introduction to the necessary background concepts, I present my work under three broad categories. First, I present work on contextuality that extensively relies on (undirected) graphs and hypergraphs as the discrete structures of interest; more specifically, it relies on invariants associated with them. This work includes Kochen-Specker (KS) contextuality and its operationalization to generalized contextuality, expressed via (hyper)graph-theoretic frameworks. I also present work on KS-contextuality in multiqubit systems and an application of generalized contextuality to a one-shot communication task, both of which rely on hypergraphs. Second, I present work on causality, where the discrete structures of interest are directed graphs. This includes work on indefinite causal order, specifically its connections to the gap between local operations and classical communication (LOCC) and separable operations (SEP), and a device-independent notion of nonclassicality--termed antinomicity--that generalizes Bell nonlocality without global causal assumptions. Finally, I present work on the incompatibility of quantum measurements, its connection to Bell nonlocality, and its role in discriminating between quantum and almost quantum correlations in the single-system setting. The discrete structures of interest here are hypergraphs that model joint measurability relations between quantum measurements. I conclude with a summary and an overview of work that is not covered in this thesis.