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.
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.
Since being defined by Kochen and Specker, and separately by Bell, contextuality has been proposed as one of the key phenomena that distinguishing quantum theory from classical theories. However, with the rise of quantum information contextuality's position as the leading definition of the quantum/classical boundary has been called into question. This is due to the fact that a contextual explanation is required by subtheories that offer no exponential quantum computational advantage over classical computation. In this thesis, submitted in requirement for a PhD in physics with quantum information, we shall explore this unwanted contextuality, and show that generalized contextuality is more prevalent than was previously thought. \n \nFirst we will show that the single-qubit stabilizer subtheory, which was previously thought of as a non-contextual subtheory, requires a generalized contextual ontological model, when transformations are included in the operational description. In addition to this we show that the even smaller single-rebit stabilizer subtheory, a strict subtheory of the single-qubit stabilizer subtheory, must also admit a generalized contextual ontological model, again when transformations are included in the operational description. We then show that both these subtheories require negatively represented quasi-probability representations, re-establishing the link between contextuality and negativity for transformations. We also investigate the representation of transformations in generic quasi-probability representations, showing that under a reasonable assumption almost-all unitaries must be negatively represented by a finite quasi-probability representation. \n \nSecond we will investigate the efficiently simulable n-qubit stabilizer subtheory, which exhibits all forms of contextuality and thus represents the main obstacle to identifying contextuality as a resource for quantum computation. To this end we present an attempt at constructing a model based on a frame-switching Wigner function. This leads us to constructing a contextual ψ-epistemic ontological model of the n-qubit stabilizer formalism. We shall see that this model is outcome deterministic, which is one of the core assumptions in the definition of traditional non-contextuality. This model then will lead us to a result that proves that any ontological model of the n-qubit stabilizer formalism requires at least n-1 generators to be encoded in the ontology of the model. As n-1 generators represents almost full knowledge about the stabilizer state, we therefore posit that ψ-onicity, a more controversial notion of non-classicality, is actually the resource for quantum computation.
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.
One of the main questions in the field of quantum computation is where the quantum computational speed-up comes from. Recent studies in the field of quantum foundations have suggested which are the features to be considered as inherently non-classical. One of the major contributions in this direction comes from a result known as Spekkens' toy theory, which is a model built to reproduce quantum theory as a classical phase-space-inspired theory with restrictions on what an observer can know about reality. The model reproduces many of the features of quantum mechanics, but it does not reproduce non-locality and contextuality. In this thesis we first complete Spekkens' toy theory with measurement update rules and a mathematical framework that generalises it to systems of any finite dimensions (prime and non-prime). We also extend the operational equivalence between the toy theory and stabilizer quantum mechanics to all odd dimensions via Gross' Wigner functions. We then use the toy theory to represent the non-contextual and classically simulatable part of the computation in state-injection schemes of quantum computation where contextuality is a resource. In the case of qubits, we show that the subtheories of quantum mechanics represented in the toy model can achieve the full stabilizer theory via state-injection and we associate different proofs of contextuality to different injection processes. Stepping back from Spekkens' toy theory, we conclude by focusing on single system protocols that compute non-linear functions (similarly to the popular CHSH game) which show quantum advantages even in absence of non-locality and contextuality (in its standard notions). We analyse their performances (formalised in Bell's and Tsirelson's bounds) in relation to Landauer's principle, which associates entropic costs to irreversible computations, and to a new notion of contextuality for sequences of transformations.
A Contextual ψ-Epistemic Model of the n-Qubit Stabilizer Formalism
Contextuality, a generalization of non-locality, has been proposed as the resource that provides the computational speed-up for quantum computation. For universal quantum computation using qudits, of odd-prime dimension, contextuality has been shown to be a necessary and possibly sufficient resource. However, the role of contextuality in quantum computation with qubits remains open. The n-qubit stabilizer formalism, which by itself cannot provide a quantum computer super-polynomial computational advantage over a classical counterpart, is contextual. Therefore contextuality cannot be identified as a sufficient resource for quantum computation. However it can be identified as a necessary resource. In this paper we construct a contextual ψ-epistemic ontological model of the n-qubit stabilizer formalism, to investigate the contextuality present in the formalism. We demonstrate it is possible for such a model to be outcome deterministic, and therefore have a value assignment to all Pauli observables. In our model the value assignment must be updated after a measurement of any stabilizer observable. Remarkably, this includes the value assignments for observables that commute with the measurement. A stronger manifestation of contextuality than is required by known no-go theorems.
Contextuality is a phenomenon at the heart of the quantum mechanical departure from classical behaviour, and has been recently identified as a resource in quantum computation. Experimental demonstration of contextuality is thus an important goal. The traditional form of contextuality -- as violation of a Kochen-Specker inequality -- requires a quantum system with at least three levels, and the status of the assumption of determinism used in deriving those inequalities has been controversial. By considering `unsharp' observables, Liang, Spekkens and Wiseman (LSW) derived an inequality for generalized noncontextual models that doesn't assume determinism, and applies already to a qubit. We experimentally implement the LSW test using the polarization states of a heralded single photon and three unsharp binary measurements. We violate the LSW inequality by more than 16 standard deviations, thus showing that our results cannot be reproduced by a noncontextual subset of quantum theory.
We give a complete characterization of the (non)classicality of all stabilizer subtheories. First, we prove that there is a unique nonnegative and diagram-preserving quasiprobability representation of the stabilizer subtheory in all odd dimensions, namely Gross's discrete Wigner function. This representation is equivalent to Spekkens' epistemically restricted toy theory, which is consequently singled out as the unique noncontextual ontological model for the stabilizer subtheory. Strikingly, the principle of noncontextuality is powerful enough (at least in this setting) to single out one particular classical realist interpretation. Our result explains the practical utility of Gross's representation by showing that (in the setting of the stabilizer subtheory) negativity in this particular representation implies generalized contextuality. Since negativity of this particular representation is a necessary resource for universal quantum computation in the state injection model, it follows that generalized contextuality is also a necessary resource for universal quantum computation in this model. In all even dimensions, we prove that there does not exist any nonnegative and diagram-preserving quasiprobability representation of the stabilizer subtheory, and, hence, that the stabilizer subtheory is contextual in all even dimensions.