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.
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.
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.
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.
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.
The Heisenberg microscope provides a powerful mental image of the measurement process of quantum mechanics (QM), attempting to explain the uncertainty relation through an uncontrollable backaction from the measurement device. However, Heisenberg's proposed backaction uses features that are not present in the QM description of the world, and according to Bohr not present in the world. Therefore, Bohr argues, the mental image proposed by Heisenberg should be avoided. Later developments by Bell and Kochen-Specker show that a model that contains the features used for the Heisenberg microscope is in principle possible but must necessarily be nonlocal and contextual. In this paper we will reexamine the measurement process within a restriction of QM known as Stabilizer QM (SQM), that still exhibits, for example, Greenberger-Horne-Zeilinger nonlocality and Peres-Mermin contextuality. The reexamination will use a recent extension of SQM, the Contextual Ontological Model (COM), where the system state gives a complete description of future measurement outcomes reproducing the quantum predictions, including the mentioned phenomena. We will see that the resulting contextual Heisenberg microscope backaction can be completely described within COM, and that the associated randomness originates in the initial state of the pointer system, exactly as in the original description of the Heisenberg microscope. The presence of contextuality, usually seen as prohibiting ontological models, suggests that the contextual Heisenberg microscope picture could perhaps be enabled in general QM.
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.
Soon after the dawn of quantum error correction, DiVincenzo and Peres observed that stabilizer codewords could give rise to simple proofs of quantumness via contextuality. This discovery can be recast in the language of nonlocal games: every n-qubit stabilizer state defines a specific "stabilizer-testing" n-player nonlocal game, which quantum players can win with probability one. If quantum players can moreover outperform all possible classical players, then the state is contextual. However, the classical values of stabilizer-testing games are largely unknown for scalable examples beyond the n-qubit GHZ state. We introduce several new methods for upper-bounding the classical values of these games. We first prove a general coding-theory bound for all stabilizer-testing games: if the classical value pcl∗<1, then pcl∗≤7/8, i.e., there is no classical strategy that can perform as well as the optimal quantum strategy even in an asymptotic sense. We then show how to tighten this bound for the most common scalable examples, namely GHZ, toric-code and cyclic cluster states. In particular, we establish an asymptotically tight upper bound for cyclic cluster states using transfer-matrix methods. This leads to the striking conclusion that measuring an exponentially small fidelity to the cyclic cluster state will suffice to witness its contextuality.