Generalized contextuality is a canonical distinguishing property of nonclassical generalized probabilistic theories, in particular quantum mechanics. Methods for certification and characterization of generalized contextuality of a given generalized probabilistic theory are well developed for prepare-measure and single-stage prepare-transform-measure scenarios. In a recent work [arXiv:2512.10000], a bottom-up, statistics-first linear-algebraic framework for contextuality in prepare-measure scenarios was introduced. We extend this approach to operational scenarios with sequential transformations with an arbitrary number of stages. We give a full decision procedure for contextuality of such scenarios within operational theories and analyze its computational complexity. In particular, our decision procedure has a complexity linearly exponential in the minimum generalized probabilistic theory (GPT) dimension, and polynomial in the number of procedures. We demonstrate our framework and approach through multiple examples, including Spekkens' toy theory and the 8-state single-qubit stabilizer theory. In particular, we construct an operational theory in which contextuality manifests itself only in the sequential structure of the transformations. Our findings thus shed new light on the significant role of compositional structures in the phenomenon of generalized contextuality.
Generalized contextuality is a canonical distinguishing property of nonclassical generalized probabilistic theories, in particular quantum mechanics. Methods for certification and characterization of generalized contextuality of a given generalized probabilistic theory are well developed for prepare-measure and single-stage prepare-transform-measure scenarios. In a recent work [arXiv:2512.10000], a bottom-up, statistics-first linear-algebraic framework for contextuality in prepare-measure scenarios was introduced. We extend this approach to operational scenarios with sequential transformations with an arbitrary number of stages. We give a full decision procedure for contextuality of such scenarios within operational theories and analyze its computational complexity. In particular, our decision procedure has a complexity linearly exponential in the minimum generalized probabilistic theory (GPT) dimension, and polynomial in the number of procedures. We demonstrate our framework and approach through multiple examples, including Spekkens' toy theory and the 8-state single-qubit stabilizer theory. In particular, we construct an operational theory in which contextuality manifests itself only in the sequential structure of the transformations. Our findings thus shed new light on the significant role of compositional structures in the phenomenon of generalized contextuality.
Contextuality is a fundamental nonclassical property of quantum theory, which has recently been proven to be a key resource for achieving quantum speed-ups in some leading models of quantum computation. However, which of the forms of contextuality, and how much thereof, are required to obtain a speed-up in an arbitrary model of quantum computation remains unclear. In this Letter, we show that the relation between contextuality and a computational advantage is more complicated than previously thought. We achieve this by proving that generalized contextuality is present even within the simplest subset of quantum operations, the so-called single-qubit stabilizer theory, which offers no computational advantage and was previously believed to be completely noncontextual. However, the contextuality of the single-qubit stabilizer theory can be confined to transformations. Therefore, our result also demonstrates that the commonly considered prepare-and-measure scenarios (which ignore transformations) do not fully capture the contextuality of quantum theory.
It is useful to have a criterion for when the predictions of an operational theory should be considered classically explainable. Here we take the criterion to be that the theory admits of a generalized-noncontextual ontological model. Existing works on generalized noncontextuality have focused on experimental scenarios having a simple structure: typically, prepare-measure scenarios. Here, we formally extend the framework of ontological models as well as the principle of generalized noncontextuality to arbitrary compositional scenarios. We leverage a process-theoretic framework to prove that, under some reasonable assumptions, every generalized-noncontextual ontological model of a tomographically local operational theory has a surprisingly rigid and simple mathematical structure — in short, it corresponds to a frame representation which is not overcomplete. One consequence of this theorem is that the largest number of ontic states possible in any such model is given by the dimension of the associated generalized probabilistic theory. This constraint is useful for generating noncontextuality no-go theorems as well as techniques for experimentally certifying contextuality. Along the way, we extend known results concerning the equivalence of different notions of classicality from prepare-measure scenarios to arbitrary compositional scenarios. Specifically, we prove a correspondence between the following three notions of classical explainability of an operational theory: (i) existence of a noncontextual ontological model for it, (ii) existence of a positive quasiprobability representation for the generalized probabilistic theory it defines, and (iii) existence of an ontological model for the generalized probabilistic theory it defines.
To make precise the sense in which the operational predictions of quantum theory conflict with a classical worldview, it is necessary to articulate a notion of classicality within an operational framework.A widely applicable notion of classicality of this sort is whether or not the predictions of a given operational theory can be explained by a generalized-noncontextual ontological model.We here explore what notion of classicality this implies for the generalized probabilistic theory (GPT) that arises from a given operational theory, focusing on prepare-measure scenarios.We first show that, when mapping an operational theory to a GPT by quotienting relative to operational equivalences, the constraint of explainability by a generalized-noncontextual ontological model is mapped to the constraint of explainability by an ontological model.We then show that, under the additional assumption that the ontic state space is of finite cardinality, this constraint on the GPT can be expressed as a geometric condition which we term simplex embeddability.Whereas the traditional notion of classicality for a GPT is that its state space be a simplex and its effect space be the dual of this simplex, simplex embeddability merely requires that its state space be embeddable in a simplex and its effect space in the dual of that simplex.We argue that simplex embeddability constitutes an intuitive and freestanding notion of classicality for GPTs.Our result also has applications to witnessing nonclassicality in prepare-measure experiments.
Generalized contextuality refers to our inability of explaining measurement statistics using a contextindependent probabilistic and ontological model.On the other hand, measurement statistics can also be modeled using the framework of general probabilistic theories (GPTs).Here, starting from a construction of GPTs based on a Gleason-type theorem, we fully characterize these structures with respect to their permission and rejection of generalized (non)contextual ontological models.It follows that in any GPT construction the three insistence of (i) the no-restriction hypothesis, (ii) the ontological noncontextuality, and (iii) multiple nonrefinable measurements for any fixed number of outcomes are incompatible.Hence, any GPT satisfying the no-restriction hypothesis is ontologically noncontextual if and only if it is simplicial.We give a detailed discussion of GPTs for which the no-restriction hypothesis is violated, and show that they can always be considered as subtheories (subGPTs) of GPTs satisfying the hypothesis.It is shown that subGPTs are ontologically noncontextual if and only if they are subtheories of simplicial GPTs of the same dimensionality.Finally, we establish as a corollary the necessary and sufficient condition for a single resourceful measurement or state to promote an ontologically noncontextual (i.e., classical) general probabilistic theory to an ontologically contextual (i.e., nonclassical) one under the no-restriction hypothesis.
Starting from arbitrary sets of quantum states and measurements, referred to as the prepare-and-measure scenario, an operationally noncontextual ontological model of the quantum statistics associated with the prepare-and-measure scenario is constructed. The operationally noncontextual ontological model coincides with standard Spekkens noncontextual ontological models for tomographically complete scenarios, while covering the non-tomographically complete case with a new notion of a reduced space, which we motivate following the guiding principles of noncontextuality. A mathematical criterion, called unit separability , is formulated as the relevant classicality criterion – the name is inspired by the usual notion of quantum state separability. Using this criterion, we derive a new upper bound on the cardinality of the ontic space. Then, we recast the unit separability criterion as a (possibly infinite) set of linear constraints, from which we obtain two separate hierarchies of algorithmic tests to witness the non-classicality or certify the classicality of a scenario. Finally, we reformulate our results in the framework of generalized probabilistic theories and discuss the implications for simplex-embeddability in such theories.
We develop a bottom-up, statistics-first framework in which the full probabilistic content of an operational theory is encoded in its matrix of conditional outcome probabilities of events (COPE). Within this setting, five model classes (preGPTs, GPTs, quasiprobabilistic, ontological, and noncontextual ontological) are unified as constrained factorizations of the COPE matrix. We identify equirank factorizations as the structural core of GPTs and noncontextual ontological models and establish their relation to tomographic completeness. This yields a simple, model-agnostic criterion for noncontextuality: an operational theory admits a noncontextual ontological model if and only if its COPE matrix admits an equirank nonnegative matrix factorization (ENMF). Failure of the equirank condition in all ontological models therefore establishes contextuality. We operationalize rank separation via two complementary methods provided by the linear-algebraic framework. First, we use ENMF to interpret noncontextual ontological models as nested polytopes. This allows us to establish that the boxworld operational theory is ontologically contextual. Second, we apply techniques from discrete mathematics to derive a lower bound on the ontological dimensionality of COPE matrices exhibiting sparsity patterns, and use this bound to establish a new proof that a discrete version of qubit theory exhibits ontological contextuality. By reframing contextuality as a problem in matrix analysis, our work provides a unified structure for its systematic study and opens new avenues for exploring nonclassical resources.