We introduce an algebraic structure for studying state-independent contextuality arguments, a key form of quantum non-classicality exemplified by the well-known Peres-Mermin magic square, and used as a source of quantum advantage. We introduce commutation groups presented by generators and relations, and analyse them in terms of a string rewriting system. There is also a linear algebraic construction, a directed version of the Heisenberg group. We introduce contextual words as a general form of contextuality witness. We characterise when contextual words can arise in commutation groups, and explicitly construct non-contextual value assignments in other cases. We give unitary representations of commutation groups as subgroups of generalized Pauli n-groups.
We introduce an algebraic structure for studying state-independent contextuality arguments, a key form of quantum non-classicality exemplified by the well-known Peres-Mermin magic square, and used as a source of quantum advantage. We introduce \emph{commutation groups} presented by generators and relations, and analyse them in terms of a string rewriting system. There is also a linear algebraic construction, a directed version of the Heisenberg group. We introduce \emph{contextual words} as a general form of contextuality witness. We characterise when contextual words can arise in commutation groups, and explicitly construct non-contextual value assignments in other cases. We give unitary representations of commutation groups as subgroups of generalized Pauli
n-groups.
Contextuality is a key distinguishing feature between classical and quantum physics. It expresses a fundamental obstruction to describing quantum theory using classical concepts. In turn, understood as a resource for quantum computation, it is expected to hold the key to quantum advantage. Yet, despite its long recognised importance in quantum foundations and, more recently, in quantum computation, the structural essence of contextuality has remained somewhat elusive - different frameworks address different aspects of the phenomenon, yet their precise relationship often remains unclear. This issue already looms large at the level of the Bell-Kochen-Specker theorem: while traditional proofs proceed by showing the nonexistence of valuations, the notion of state-independent contextuality in the marginal approach allows to prove contextuality from seemingly weaker assumptions. In the light of this, and at the absence of a unified mathematical framework for Kochen-Specker contextuality, the original algebraic approach has been widely abandoned, in favour of the study of contextual correlations. Here, we reinstate the algebraic perspective on contextuality. Concretely, by building on the novel concept of context connections, we reformulate the algebraic relations between observables originally postulated by Kochen and Specker, and we explicitly demonstrate their consistency with the notion of state-independent contextuality. In the present paper, we focus on the new conceptual ideas and discuss them in the concrete setting of spin-1 observables, specifically those in the example of [S. Yu and C.H. Oh, Phys. Rev. Lett., 108, 030402 (2012)]; in a companion paper, we generalise these ideas, obtain a complete characterisation of Kochen-Specker contextuality and provide a detailed comparison with the related notions of contextuality in the marginal and graph-theoretic approach.
Abstract Quantum contextuality represents a fundamental form of nonclassicality in quantum mechanics. To provide a more complete characterization of nonclassical properties in quantum systems, we adopt a logical perspective and propose a mathematical framework based on exclusive partial Boolean algebras. This framework enables a unified description of contextuality and nonclassicality across finite general, quantum, and classical systems. We establish a unified and minimal classical counterpart for any finite general system. Within this framework, we formalize major categories of quantum contextuality, demonstrating that: 12 projectors suffice to generate Kochen–Specker scenarios; 10 projectors suffice to witness state-independent contextuality; and 3 observables suffice to witness quantum contextuality. Finally, we prove that contextuality is a sufficient but not necessary condition for nonclassicality.
The Pauli groups are ubiquitous in quantum information theory because of their usefulness in describing quantum states and operations and their readily understood symmetry properties. In addition, the most well-understood quantum error correcting codes—stabilizer codes—are built using Pauli operators. The eigenstates of these operators—stabilizer states—display a structure (e.g., mutual orthogonality relationships) that has made them useful in examples of multi-qubit non-locality and contextuality. Here, we apply the graph-theoretical contextuality formalism of Cabello, Severini and Winter to sets of stabilizer states, with particular attention to the effect of generalizing two-level qubit systems to odd prime d-level qudit systems. While state-independent contextuality using two-qubit states does not generalize to qudits, we show explicitly how state-dependent contextuality associated with a Bell inequality does generalize. Along the way we note various structural properties of stabilizer states, with respect to their orthogonality relationships, which may be of independent interest.
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≥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.
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.