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

A Contextual $ψ$-Epistemic Model of the $n$-Qubit Stabilizer Formalism

Piers Lillystone, Joseph Emerson

Published Apr 8, 2019• 4 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.1904.04268

Related papers

Contextuality and Ontological Models: A Tale of Desire and Disappointment

Piers Lillystone

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.

•Sep 23, 2019•0 citations

Efficient Contextual Ontological Model of n -Qubit Stabilizer Quantum Mechanics

Christoffer Hindlycke, Jan-Åke Larsson

The most well-known tool for studying contextuality in quantum computation is the n-qubit Stabilizer state tableau representation. We provide an extension that not only describes the quantum state but is also outcome deterministic. The extension enables a value assignment to exponentially many Pauli observables, yet it remains quadratic in both memory and computational complexity. Furthermore, we show that the mechanisms employed for contextuality and measurement disturbance are wholly separate. The model will be useful for investigating the role of contextuality in n-qubit quantum computation.

arXiv:2202.05081•Physical Review Letters•Sep 19, 2022•10 citations

Contextuality as a resource for measurement-based quantum computation beyond qubits

Markus Frembs, Sam Roberts, Stephen D. Bartlett

Contextuality—the obstruction to describing quantum mechanics in a classical statistical way—has been proposed as a resource that powers quantum computing. The measurement-based model provides a concrete manifestation of contextuality as a computational resource, as follows. If local measurements on a multi-qubit state can be used to evaluate nonlinear boolean functions with only linear control processing, then this computation constitutes a proof of strong contextuality—the possible local measurement outcomes cannot all be pre-assigned. However, this connection is restricted to the special case when the local measured systems are qubits , which have unusual properties from the perspective of contextuality. A single qubit cannot allow for a proof of contextuality, unlike higher-dimensional systems, and multiple qubits can allow for state-independent contextuality with only Pauli observables, again unlike higher-dimensional generalisations. Here we identify precisely that strong non-locality is necessary in a qudit measurement-based computation (MBC) that evaluates high-degree polynomial functions with only linear control. We introduce the concept of local universality , which places a bound on the space of output functions accessible under the constraint of single-qudit measurements. Thus, the partition of a physical system into subsystems plays a crucial role for the increase in computational power. A prominent feature of our setting is that the enabling resources for qubit and qudit MBC are of the same underlying nature, avoiding the pathologies associated with qubit contextuality.

arXiv:1804.07364•New Journal of Physics•Sep 24, 2018•44 citations

Contextuality as a Resource for Models of Quantum Computation with Qubits

Juan Bermejo-Vega, Nicolas Delfosse, Dan E. Browne +2 more

A central question in quantum computation is to identify the resources that are responsible for quantum speed-up. Quantum contextuality has been recently shown to be a resource for quantum computation with magic states for odd-prime dimensional qudits and two-dimensional systems with real wave functions. The phenomenon of state-independent contextuality poses a priori an obstruction to characterizing the case of regular qubits, the fundamental building block of quantum computation. Here, we establish contextuality of magic states as a necessary resource for a large class of quantum computation schemes on qubits. We illustrate our result with a concrete scheme related to measurement-based quantum computation.

arXiv:1610.08529•Physical Review Letters•Sep 21, 2017•143 citations

Contextuality bounds the efficiency of classical simulation of quantum processes

Angela Karanjai, Joel J. Wallman, Stephen D. Bartlett

Contextuality has been conjectured to be a super-classical resource for quantum computation, analogous to the role of non-locality as a super-classical resource for communication. We show that the presence of contextuality places a lower bound on the amount of classical memory required to simulate any quantum sub-theory, thereby establishing a quantitative connection between contextuality and classical simulability. We apply our result to the qubit stabilizer sub-theory, where the presence of state-independent contextuality has been an obstacle in establishing contextuality as a quantum computational resource. We find that the presence of contextuality in this sub-theory demands that the minimum number of classical bits of memory required to simulate a multi-qubit system must scale quadratically in the number of qubits; notably, this is the same scaling as the Gottesman-Knill algorithm. We contrast this result with the (non-contextual) qudit case, where linear scaling is possible.

arXiv:1802.07744•Feb 21, 2018•20 citations

Non-classicality as a computational resource

Lorenzo Catani

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.

•Oct 28, 2018•0 citations
A Contextual ψψψ-Epistemic Model of the nnn-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 nnn-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 nnn-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.
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.
The most well-known tool for studying contextuality in quantum computation is the n-qubit Stabilizer state tableau representation. We provide an extension that not only describes the quantum state but is also outcome deterministic. The extension enables a value assignment to exponentially many Pauli observables, yet it remains quadratic in both memory and computational complexity. Furthermore, we show that the mechanisms employed for contextuality and measurement disturbance are wholly separate. The model will be useful for investigating the role of contextuality in n-qubit quantum computation.
Contextuality—the obstruction to describing quantum mechanics in a classical statistical way—has been proposed as a resource that powers quantum computing. The measurement-based model provides a concrete manifestation of contextuality as a computational resource, as follows. If local measurements on a multi-qubit state can be used to evaluate nonlinear boolean functions with only linear control processing, then this computation constitutes a proof of strong contextuality—the possible local measurement outcomes cannot all be pre-assigned. However, this connection is restricted to the special case when the local measured systems are qubits , which have unusual properties from the perspective of contextuality. A single qubit cannot allow for a proof of contextuality, unlike higher-dimensional systems, and multiple qubits can allow for state-independent contextuality with only Pauli observables, again unlike higher-dimensional generalisations. Here we identify precisely that strong non-locality is necessary in a qudit measurement-based computation (MBC) that evaluates high-degree polynomial functions with only linear control. We introduce the concept of local universality , which places a bound on the space of output functions accessible under the constraint of single-qudit measurements. Thus, the partition of a physical system into subsystems plays a crucial role for the increase in computational power. A prominent feature of our setting is that the enabling resources for qubit and qudit MBC are of the same underlying nature, avoiding the pathologies associated with qubit contextuality.
A central question in quantum computation is to identify the resources that are responsible for quantum speed-up. Quantum contextuality has been recently shown to be a resource for quantum computation with magic states for odd-prime dimensional qudits and two-dimensional systems with real wave functions. The phenomenon of state-independent contextuality poses a priori an obstruction to characterizing the case of regular qubits, the fundamental building block of quantum computation. Here, we establish contextuality of magic states as a necessary resource for a large class of quantum computation schemes on qubits. We illustrate our result with a concrete scheme related to measurement-based quantum computation.
Contextuality has been conjectured to be a super-classical resource for quantum computation, analogous to the role of non-locality as a super-classical resource for communication. We show that the presence of contextuality places a lower bound on the amount of classical memory required to simulate any quantum sub-theory, thereby establishing a quantitative connection between contextuality and classical simulability. We apply our result to the qubit stabilizer sub-theory, where the presence of state-independent contextuality has been an obstacle in establishing contextuality as a quantum computational resource. We find that the presence of contextuality in this sub-theory demands that the minimum number of classical bits of memory required to simulate a multi-qubit system must scale quadratically in the number of qubits; notably, this is the same scaling as the Gottesman-Knill algorithm. We contrast this result with the (non-contextual) qudit case, where linear scaling is possible.
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.