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:1307.6264

Nonclassical Structures within the N-qubit Pauli Group

Mordecai Waegell

Published Jul 23, 2013• 2 citations
arXivHTMLPDF

Abstract

Structures that demonstrate nonclassicality are of foundational interest in quantum mechanics, and can also be seen as resources for numerous applications in quantum information processing - particularly in the Hilbert space of $N$ qubits. The theory of entanglement, quantum contextuality, and quantum nonlocality within the $N$-qubit Pauli group is further developed in this thesis. The Strong Kochen-Specker theorem and the structures that prove it are introduced and explored in detail. The pattern of connections between structures that show entanglement, contextuality, and nonlocality is explained. Computational search algorithms and related tools were developed and used to perform complete searches for minimal nonclassical structures within the $N$-qubit Pauli group up to values of $N$ limited by our computational resources. Our results are surveyed and prescriptions are given for using the elementary nonclassical structures we have found to construct more complex types of such structures. Families of nonclassical structures are presented for all values of $N$, including the most compact family of projector-based parity proofs of the Kochen-Specker theorem yet discovered in all dimensions of the form $2^N$, where $N\geq2$. The applications of our results and their connection with other work is also discussed.

DOI
10.48550/arxiv.1307.6264

Related papers

Primitive nonclassical structures of the N -qubit Pauli group

Mordecai Waegell

Several types of nonclassical structures within the $N$-qubit Pauli group that can be seen as fundamental resources for quantum information processing are presented and discussed. Identity products (IDs), structures fundamentally related to entanglement, are defined and explored. The Kochen-Specker (KS) theorem is proved by particular sets of IDs that we call KS sets. We also present a theorem that we call the $N$-qubit Kochen-Specker (NKS) theorem, which is proved by particular sets of IDs that we call NKS sets, and whose utility is that it leads to efficient constructions for KS sets. We define the criticality, or irreducibility, of these structures, and its connection to entanglement. All representative critical IDs for up to $N=4$ qubits are presented, and numerous families of critical IDs for arbitrarily large values of $N$ are discussed. The critical IDs for a given $N$ are a finite set of geometric objects that appear to fully characterize the nonclassicality of the $N$-qubit Pauli group. Methods for constructing critical KS sets and NKS sets from IDs are given, and experimental tests of entanglement, contextuality, and nonlocality are discussed. Possible applications and connections to other work are also discussed.

arXiv:1310.3419•Physical Review A•Jan 21, 2014•10 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

Proofs of the Kochen-Specker theorem based on the N -qubit Pauli group

Mordecai Waegell, P. K. Aravind

We present a number of observables-based proofs of the Kochen-Specker (KS) theorem based on the $N$-qubit Pauli group for $N\ensuremath{\ge}4$, thus adding to the proofs that have been presented earlier for the 2- and 3-qubit groups. These proofs have the attractive feature that they can be presented in the form of diagrams from which they are obvious by inspection. They are also irreducible in the sense that they cannot be reduced to smaller proofs by ignoring some subset of qubits and/or observables in them. A simple algorithm is given for transforming any observables-based KS proof into a large number of projectors-based KS proofs; if the observables-based proof has $O$ observables, with each observable occurring in exactly two commuting sets and any two commuting sets having at most one observable in common, the number of associated projectors-based parity proofs is 2${}^{O}$. We introduce symbols for the observables- and projectors-based KS proofs that capture their important features and also convey a feeling for the enormous variety of both these types of proofs within the $N$-qubit Pauli group. We discuss an infinite family of observables-based proofs, whose members include all numbers of qubits from 2 up, and show how it can be used to generate projectors-based KS proofs involving only 9 bases (or experimental contexts) in any dimension of the form ${2}^{N}$ for $N\ensuremath{\ge}2$. Some implications of our results are discussed.

arXiv:1302.4801•Physical Review A•Jul 1, 2013•33 citations

Contextuality in the nnn-qubit Pauli group

Markus Frembs

The $n$-qubit Pauli group is an essential ingredient to most quantum applications, from computing and error correction to benchmarking and simulation. Despite comprising merely a discrete set of operators, it exhibits many quintessential features of quantum theory, including contextuality, which has been identified as a key resource to quantum advantage in a variety of different flavours. Here, we extend this analysis, introducing the notion of a `noncontextual property' whose nonexistence proves the Kochen-Specker theorem, similarly to and generalising common arguments based on the nonexistence of valuations. We relate this notion formally to the existence of Boolean-valued frame functions, and characterise all such frame functions in the case of the $n$-qubit Pauli group. For two qubits, we show that the Pauli group admits noncontextual properties, despite admitting no valuations. We then establish this as the only nontrivial such case with $n\geq 2$, by proving that any Boolean-valued frame function on stabiliser states is constant for more than two qubits. We also perform a similar analysis for the symplectic theory underlying the $n$-qubit Pauli group, for which nonconstant Boolean-valued frame functions exist for all $n$, yet only in restricted form. By comparison, this shows that contextuality in the $n$-qubit Pauli group is not only a consequence of the projective nature of the Pauli group as a representation of its underlying symplectic vector space, but of the geometry of symplectic polar spaces itself. In geometric terms, our result determines all Cameron-Liebler sets of maximal totally isotropic flats in the binary affine-symplectic space.

quant-pharXiv:2608.11993•Aug 13, 2026•0 citations

Contextuality in composite systems: the role of entanglement in the Kochen-Specker theorem

Victoria J Wright, Ravi Kunjwal

The Kochen–Specker (KS) theorem reveals the nonclassicality of single quantum systems. In contrast, Bell's theorem and entanglement concern the nonclassicality of composite quantum systems. Accordingly, unlike incompatibility, entanglement and Bell non-locality are not necessary to demonstrate KS-contextuality. However, here we find that for multiqubit systems, entanglement and non-locality are both essential to proofs of the Kochen–Specker theorem. Firstly, we show that unentangled measurements (a strict superset of local measurements) can never yield a logical (state-independent) proof of the KS theorem for multiqubit systems. In particular, unentangled but nonlocal measurements—whose eigenstates exhibit ''nonlocality without entanglement"—are insufficient for such proofs. This also implies that proving Gleason's theorem on a multiqubit system necessarily requires entangled projections, as shown by Wallach [Contemp Math, 305: 291-298 (2002)]. Secondly, we show that a multiqubit state admits a statistical (state-dependent) proof of the KS theorem if and only if it can violate a Bell inequality with projective measurements. We also establish the relationship between entanglement and the theorems of Kochen–Specker and Gleason more generally in multiqudit systems by constructing new examples of KS sets. Finally, we discuss how our results shed new light on the role of multiqubit contextuality as a resource within the paradigm of quantum computation with state injection.

arXiv:2109.13594•Quantum•Jan 19, 2023•9 citations

Proofs of the Kochen–Specker theorem based on a system of three qubits

Mordecai Waegell, P. K. Aravind

A number of new proofs of the Kochen–Specker theorem are given based on the observables of the three-qubit Pauli group. Each proof is presented in the form of a diagram from which it is obvious by inspection. Each of our observable-based proofs leads to a system of projectors and bases that generally yields a large number of ‘parity proofs’ of the Kochen–Specker theorem. Some examples of such proofs are given and some of their applications are discussed.

arXiv:1205.5015•Journal of Physics A Mathematical and Theoretical•Sep 18, 2012•44 citations
Structures that demonstrate nonclassicality are of foundational interest in quantum mechanics, and can also be seen as resources for numerous applications in quantum information processing - particularly in the Hilbert space of NNN qubits. The theory of entanglement, quantum contextuality, and quantum nonlocality within the NNN-qubit Pauli group is further developed in this thesis. The Strong Kochen-Specker theorem and the structures that prove it are introduced and explored in detail. The pattern of connections between structures that show entanglement, contextuality, and nonlocality is explained. Computational search algorithms and related tools were developed and used to perform complete searches for minimal nonclassical structures within the NNN-qubit Pauli group up to values of NNN limited by our computational resources. Our results are surveyed and prescriptions are given for using the elementary nonclassical structures we have found to construct more complex types of such structures. Families of nonclassical structures are presented for all values of NNN, including the most compact family of projector-based parity proofs of the Kochen-Specker theorem yet discovered in all dimensions of the form 2N2^N2N, where N≥2N\geq2N≥2. The applications of our results and their connection with other work is also discussed.
Several types of nonclassical structures within the NNN-qubit Pauli group that can be seen as fundamental resources for quantum information processing are presented and discussed. Identity products (IDs), structures fundamentally related to entanglement, are defined and explored. The Kochen-Specker (KS) theorem is proved by particular sets of IDs that we call KS sets. We also present a theorem that we call the NNN-qubit Kochen-Specker (NKS) theorem, which is proved by particular sets of IDs that we call NKS sets, and whose utility is that it leads to efficient constructions for KS sets. We define the criticality, or irreducibility, of these structures, and its connection to entanglement. All representative critical IDs for up to N=4N=4N=4 qubits are presented, and numerous families of critical IDs for arbitrarily large values of NNN are discussed. The critical IDs for a given NNN are a finite set of geometric objects that appear to fully characterize the nonclassicality of the NNN-qubit Pauli group. Methods for constructing critical KS sets and NKS sets from IDs are given, and experimental tests of entanglement, contextuality, and nonlocality are discussed. Possible applications and connections to other work are also discussed.
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.
We present a number of observables-based proofs of the Kochen-Specker (KS) theorem based on the NNN-qubit Pauli group for $N\ensuremath{\ge}4$, thus adding to the proofs that have been presented earlier for the 2- and 3-qubit groups. These proofs have the attractive feature that they can be presented in the form of diagrams from which they are obvious by inspection. They are also irreducible in the sense that they cannot be reduced to smaller proofs by ignoring some subset of qubits and/or observables in them. A simple algorithm is given for transforming any observables-based KS proof into a large number of projectors-based KS proofs; if the observables-based proof has OOO observables, with each observable occurring in exactly two commuting sets and any two commuting sets having at most one observable in common, the number of associated projectors-based parity proofs is 2O{}^{O}O. We introduce symbols for the observables- and projectors-based KS proofs that capture their important features and also convey a feeling for the enormous variety of both these types of proofs within the NNN-qubit Pauli group. We discuss an infinite family of observables-based proofs, whose members include all numbers of qubits from 2 up, and show how it can be used to generate projectors-based KS proofs involving only 9 bases (or experimental contexts) in any dimension of the form 2N{2}^{N}2N for $N\ensuremath{\ge}2$. Some implications of our results are discussed.
The nnn-qubit Pauli group is an essential ingredient to most quantum applications, from computing and error correction to benchmarking and simulation. Despite comprising merely a discrete set of operators, it exhibits many quintessential features of quantum theory, including contextuality, which has been identified as a key resource to quantum advantage in a variety of different flavours. Here, we extend this analysis, introducing the notion of a `noncontextual property' whose nonexistence proves the Kochen-Specker theorem, similarly to and generalising common arguments based on the nonexistence of valuations. We relate this notion formally to the existence of Boolean-valued frame functions, and characterise all such frame functions in the case of the nnn-qubit Pauli group. For two qubits, we show that the Pauli group admits noncontextual properties, despite admitting no valuations. We then establish this as the only nontrivial such case with n≥2n\geq 2n≥2, by proving that any Boolean-valued frame function on stabiliser states is constant for more than two qubits. We also perform a similar analysis for the symplectic theory underlying the nnn-qubit Pauli group, for which nonconstant Boolean-valued frame functions exist for all nnn, yet only in restricted form. By comparison, this shows that contextuality in the nnn-qubit Pauli group is not only a consequence of the projective nature of the Pauli group as a representation of its underlying symplectic vector space, but of the geometry of symplectic polar spaces itself. In geometric terms, our result determines all Cameron-Liebler sets of maximal totally isotropic flats in the binary affine-symplectic space.
The Kochen–Specker (KS) theorem reveals the nonclassicality of single quantum systems. In contrast, Bell's theorem and entanglement concern the nonclassicality of composite quantum systems. Accordingly, unlike incompatibility, entanglement and Bell non-locality are not necessary to demonstrate KS-contextuality. However, here we find that for multiqubit systems, entanglement and non-locality are both essential to proofs of the Kochen–Specker theorem. Firstly, we show that unentangled measurements (a strict superset of local measurements) can never yield a logical (state-independent) proof of the KS theorem for multiqubit systems. In particular, unentangled but nonlocal measurements—whose eigenstates exhibit ''nonlocality without entanglement"—are insufficient for such proofs. This also implies that proving Gleason's theorem on a multiqubit system necessarily requires entangled projections, as shown by Wallach [Contemp Math, 305: 291-298 (2002)]. Secondly, we show that a multiqubit state admits a statistical (state-dependent) proof of the KS theorem if and only if it can violate a Bell inequality with projective measurements. We also establish the relationship between entanglement and the theorems of Kochen–Specker and Gleason more generally in multiqudit systems by constructing new examples of KS sets. Finally, we discuss how our results shed new light on the role of multiqubit contextuality as a resource within the paradigm of quantum computation with state injection.