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

Contextuality as a resource for qubit quantum computation

Robert Raussendorf, Dan E. Browne, Nicolas Delfosse, Cihan Okay, Juan Bermejo-Vega

Published Nov 26, 2015• 13 citations
OpenAlex

Abstract

We describe a scheme of quantum computation with magic states on qubits for which contextuality is a necessary resource possessed by the magic states. More generally, we establish contextuality as a necessary resource for all schemes of quantum computation with magic states on qubits that satisfy three simple postulates. Furthermore, we identify stringent consistency conditions on such computational schemes, revealing the general structure by which negativity of Wigner functions, hardness of classical simulation of the computation, and contextuality are connected.

Related papers

Contextuality and Wigner-function negativity in qubit quantum computation

Robert Raussendorf, Dan E. Browne, Nicolas Delfosse +2 more

We describe schemes of quantum computation with magic states on qubits for which contextuality and negativity of the Wigner function are necessary resources possessed by the magic states. These schemes satisfy a constraint. Namely, the non-negativity of Wigner functions must be preserved under all available measurement operations. Furthermore, we identify stringent consistency conditions on such computational schemes, revealing the general structure by which negativity of Wigner functions, hardness of classical simulation of the computation, and contextuality are connected.

arXiv:1511.08506•Physical Review A•May 17, 2017•114 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

Contextual bound states for qudit magic state distillation

Shiroman Prakash, Aashi Gupta

Identifying necessary and sufficient conditions for universal quantum computing is a long-standing open problem for which contextuality is, perhaps, the only promising solution [Howard et al., Nature (London) 510, 351 (2014)]. To justify this conjecture, Howard et al. showed that contextuality is equivalent to Wigner negativity for qudits, and is therefore necessary and possibly sufficient for qudit magic state distillation. Here, we reformulate magic state distillation in the language of discrete phase space, to show that any finite qudit magic state distillation routine contains bound states outside the Wigner polytope; these states exhibit contextuality but are useless for magic state distillation.

arXiv:1905.00392•Physical Review A•Jan 22, 2020•10 citations

Hidden variable models and classical simulation algorithms for quantum computation with magic states on qubits

Michael Zurel

An important problem in quantum computation is to characterize the resources required for a computational speedup over classical computation. Veitch et al. showed that one necessary condition for a computational speedup in the model of quantum computation with magic states is that the discrete Wigner function representing the input state of the quantum circuit must take negative values. The amount of negativity in the discrete Wigner function quantifies the complexity of classical simulation of a quantum computation with simulation being efficient if the Wigner function is nonnegative everywhere. In this sense, negativity of the Wigner quasiprobability representation serves as an indicator of quantumness from a computational perspective. However, this result only holds for systems of qudits where the local Hilbert space dimension is odd. The first main result discussed in this thesis relates to a discrete Wigner function suitable for describing quantum computation with magic states defined for any local Hilbert space dimension. When the local Hilbert space dimension is odd it subsumes the standard discrete Wigner function. When the local Hilbert space dimension is even, as a result of state-independent proofs of contextuality among multiqubit (or multi-even-dimensional-qudit) Pauli observables, the phase space over which the Wigner function is defined becomes much larger. However, for systems of qubits, the properties required for simulation of quantum computation with magic states remain. This simulation method effectively extends the result described above for odd-dimensional qudits to qubits. Although in the even-dimensional case the phase space is much larger, points in multiqubit phase space can be characterized and classified and some structure can be imparted on the phase space. The second main result discussed here is a hidden variable model for quantum computation with magic states on qubits. This model is similar in structure to quasiprobability representations like the discrete Wigner function, but unlike those representations the model is capable of representing all elements of any quantum computation---states, operations, and measurements---using only classical probabilities. No negativity is required. This calls into question the role of negativity in quasiprobability representations as an indicator of quantumness for models of quantum computation.

•Jan 1, 2020•4 citations

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

Wigner Function Negativity and Contextuality in Quantum Computation on Rebits

Nicolas Delfosse, Philippe Allard Guerin, Jacob Bian +1 more

Quantum computation commonly relies on qubits, but rebits---states with real density matrices---can be used as well. Researchers show how the contextuality of two-level states is necessary for quantum computation.

arXiv:1409.5170•Physical Review X•Apr 2, 2015•179 citations
We describe a scheme of quantum computation with magic states on qubits for which contextuality is a necessary resource possessed by the magic states. More generally, we establish contextuality as a necessary resource for all schemes of quantum computation with magic states on qubits that satisfy three simple postulates. Furthermore, we identify stringent consistency conditions on such computational schemes, revealing the general structure by which negativity of Wigner functions, hardness of classical simulation of the computation, and contextuality are connected.
We describe schemes of quantum computation with magic states on qubits for which contextuality and negativity of the Wigner function are necessary resources possessed by the magic states. These schemes satisfy a constraint. Namely, the non-negativity of Wigner functions must be preserved under all available measurement operations. Furthermore, we identify stringent consistency conditions on such computational schemes, revealing the general structure by which negativity of Wigner functions, hardness of classical simulation of the computation, and contextuality are connected.
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.
Identifying necessary and sufficient conditions for universal quantum computing is a long-standing open problem for which contextuality is, perhaps, the only promising solution [Howard et al., Nature (London) 510, 351 (2014)]. To justify this conjecture, Howard et al. showed that contextuality is equivalent to Wigner negativity for qudits, and is therefore necessary and possibly sufficient for qudit magic state distillation. Here, we reformulate magic state distillation in the language of discrete phase space, to show that any finite qudit magic state distillation routine contains bound states outside the Wigner polytope; these states exhibit contextuality but are useless for magic state distillation.
An important problem in quantum computation is to characterize the resources required for a computational speedup over classical computation. Veitch et al. showed that one necessary condition for a computational speedup in the model of quantum computation with magic states is that the discrete Wigner function representing the input state of the quantum circuit must take negative values. The amount of negativity in the discrete Wigner function quantifies the complexity of classical simulation of a quantum computation with simulation being efficient if the Wigner function is nonnegative everywhere. In this sense, negativity of the Wigner quasiprobability representation serves as an indicator of quantumness from a computational perspective. However, this result only holds for systems of qudits where the local Hilbert space dimension is odd. The first main result discussed in this thesis relates to a discrete Wigner function suitable for describing quantum computation with magic states defined for any local Hilbert space dimension. When the local Hilbert space dimension is odd it subsumes the standard discrete Wigner function. When the local Hilbert space dimension is even, as a result of state-independent proofs of contextuality among multiqubit (or multi-even-dimensional-qudit) Pauli observables, the phase space over which the Wigner function is defined becomes much larger. However, for systems of qubits, the properties required for simulation of quantum computation with magic states remain. This simulation method effectively extends the result described above for odd-dimensional qudits to qubits. Although in the even-dimensional case the phase space is much larger, points in multiqubit phase space can be characterized and classified and some structure can be imparted on the phase space. The second main result discussed here is a hidden variable model for quantum computation with magic states on qubits. This model is similar in structure to quasiprobability representations like the discrete Wigner function, but unlike those representations the model is capable of representing all elements of any quantum computation---states, operations, and measurements---using only classical probabilities. No negativity is required. This calls into question the role of negativity in quasiprobability representations as an indicator of quantumness for models of quantum computation.
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.