Abstract Although ‘quantum contextuality’ is one of the most fundamental non-classical feature, its generic role in information processing and computation is an open quest. In this article, we present a family of distributed computing tasks pertaining to every logical proof of Kochen–Specker (KS) contextuality in two different one-way communication scenarios: (I) communication of bounded dimensional system, (II) communication of unbounded dimensional system while keeping certain information oblivious, namely, oblivious communication (OC). As the later remains largely unexplored, we introduce a general framework for OC tasks and provide a methodology for obtaining an upper bound on the success of OC tasks in classical communication. We show that quantum communication comprised of every KS set of vectors outperforms classical communication and perfectly accomplish the task in both the aforementioned scenarios. We explicitly discuss the communication tasks pertaining to the simplest state independent contextuality sets of dimension three and four. Our results establish an operational significance to single system contextuality and open up the possibility of semi-device independent quantum information processing based on that. Alongside, we identify any advantage in OC tasks as a witness of preparation contextuality.
Abstract Although ‘quantum contextuality’ is one of the most fundamental non-classical feature, its generic role in information processing and computation is an open quest. In this article, we present a family of distributed computing tasks pertaining to every logical proof of Kochen–Specker (KS) contextuality in two different one-way communication scenarios: (I) communication of bounded dimensional system, (II) communication of unbounded dimensional system while keeping certain information oblivious, namely, oblivious communication (OC). As the later remains largely unexplored, we introduce a general framework for OC tasks and provide a methodology for obtaining an upper bound on the success of OC tasks in classical communication. We show that quantum communication comprised of every KS set of vectors outperforms classical communication and perfectly accomplish the task in both the aforementioned scenarios. We explicitly discuss the communication tasks pertaining to the simplest state independent contextuality sets of dimension three and four. Our results establish an operational significance to single system contextuality and open up the possibility of semi-device independent quantum information processing based on that. Alongside, we identify any advantage in OC tasks as a witness of preparation contextuality.
The study of ontology (hidden variables) provides for a vital ground on which significant nonclassical features of quantum theory are revealed. One such nonclassical ontic feature is preparation contextuality (PC) and advantage in oblivious communication tasks is one of its operational signatures. This article primarily pursues the ontic feature underlying quantum advantage in communication complexity (CC). We construct oblivious communication tasks tailored to given CC problems. We upper bound the classical success probability of these oblivious communication tasks, obtaining preparation noncontextual inequalities. We use the very states and measurements responsible for advantage in CC problems along with the orthogonal mixtures of these states to orchestrate an advantageous protocol for the associated oblivious communication tasks and the violation of the associated inequalities, thereby unveiling PC. To showcase the vitality of our results, we find a criterion for unbounded violation of these inequalities and demonstrate the same for two widely studied CC problems.
The predictions of quantum theory resist generalised noncontextual explanations. In addition to the foundational relevance of this fact, the particular extent to which quantum theory violates noncontextuality limits available quantum advantage in communication and information processing. In the first part of this work, we formally define contextuality scenarios via prepare-and-measure experiments, along with the polytope of general contextual behaviours containing the set of quantum contextual behaviours. This framework allows us to recover several properties of set of quantum behaviours in these scenarios, including contextuality scenarios and associated noncontextuality inequalities that require for their violation the individual quantum preparation and measurement procedures to be mixed states and unsharp measurements. With the framework in place, we formulate novel semidefinite programming relaxations for bounding these sets of quantum contextual behaviours. Most significantly, to circumvent the inadequacy of pure states and projective measurements in contextuality scenarios, we present a novel unitary operator based semidefinite relaxation technique. We demonstrate the efficacy of these relaxations by obtaining tight upper bounds on the quantum violation of several noncontextuality inequalities and identifying novel maximally contextual quantum strategies. To further illustrate the versatility of these relaxations, we demonstrate monogamy of preparation contextuality in a tripartite setting, and present a secure semi-device independent quantum key distribution scheme powered by quantum advantage in parity oblivious random access codes.
Contextuality is a key distinguishing feature between classical and quantum physics. It expresses a fundamental obstruction to describing quantum theory using classical concepts. In turn, understood as a resource for quantum computation, it is expected to hold the key to quantum advantage. Yet, despite its long recognised importance in quantum foundations and, more recently, in quantum computation, the structural essence of contextuality has remained somewhat elusive - different frameworks address different aspects of the phenomenon, yet their precise relationship often remains unclear. This issue already looms large at the level of the Bell-Kochen-Specker theorem: while traditional proofs proceed by showing the nonexistence of valuations, the notion of state-independent contextuality in the marginal approach allows to prove contextuality from seemingly weaker assumptions. In the light of this, and at the absence of a unified mathematical framework for Kochen-Specker contextuality, the original algebraic approach has been widely abandoned, in favour of the study of contextual correlations. Here, we reinstate the algebraic perspective on contextuality. Concretely, by building on the novel concept of context connections, we reformulate the algebraic relations between observables originally postulated by Kochen and Specker, and we explicitly demonstrate their consistency with the notion of state-independent contextuality. In the present paper, we focus on the new conceptual ideas and discuss them in the concrete setting of spin-1 observables, specifically those in the example of [S. Yu and C.H. Oh, Phys. Rev. Lett., 108, 030402 (2012)]; in a companion paper, we generalise these ideas, obtain a complete characterisation of Kochen-Specker contextuality and provide a detailed comparison with the related notions of contextuality in the marginal and graph-theoretic approach.
Abstract The Kochen-Specker (KS) theorem is a corner-stone result in the foundations of quantum mechanics describing the fundamental difference between quantum theory and classical non-contextual theories. Recently specific substructures termed 01-gadgets were shown to exist within KS proofs that capture the essential contradiction of the theorem. Here, we show these gadgets and their generalizations provide an optimal toolbox for contextuality applications including (i) constructing classical channels exhibiting entanglement-assisted advantage in zero-error communication, (ii) identifying large separations between quantum theory and binary generalised probabilistic theories, and (iii) finding optimal tests for contextuality-based semi-device-independent randomness generation. Furthermore, we introduce and study a generalisation to definite prediction sets for more general logical propositions, that we term higher-order gadgets. We pinpoint the role these higher-order gadgets play in KS proofs by identifying these as induced subgraphs within KS graphs and showing how to construct proofs of state-independent contextuality using higher-order gadgets as building blocks. The constructions developed here may help in solving some of the remaining open problems regarding minimal proofs of the Kochen-Specker theorem.
The quantum ontological feature of contextuality apart from being central to foundations of quantum theory forms the basis of quantum advantage in a multitude of information processing tasks. In particular, the contextuality of preparation procedures was shown to power a particular two-party information processing task “parity oblivious multiplexing” (Spekkens et al. Phys Rev Lett 102:010401 (2009). Specifically, it was shown that there exists a limit to how well any preparation noncontextual theory can perform in this task. This limit constitutes a noncontextuality inequality. Moreover, the authors demonstrated quantum violation of this inequality along with preparation contextuality associated with the ontic description underlying two-level completely mixed quantum state. In this work, we extend these arguments to apply to arbitrary dimensions by introducing a class of two-party information processing tasks, namely d-level parity oblivious random access codes. We analytically obtain classical (or equivalently preparation noncontextual) bounds on the success probability for these tasks for arbitrary d. For each value of d, this bound constitutes a unique noncontextuality inequality. Remarkably, these bounds are independent of the amount of communication. Furthermore, we find a classical protocol utilizing a dc=d -dimensional classical message which saturates this bound. In order to establish nontriviality of these inequalities, we provide evidence of significant quantum violations. Specifically, by numerical techniques, we show that for d=3,…,10 , the noncontextuality bound is violated by quantum theory. (1) We provide explicit quantum protocols which violate the associated noncontextuality inequality for d=3,4,5 employing dq=d -leveled quantum systems. (2) Using see-saw semi-definite programming (SDP) technique, we find evidence (lower bounds) of significant quantum violation of these inequalities for d=3,…,10 . (3) With the help of state-of-the-art (NPA-hierarchy like) SDP technique, we provide upper bounds (independent of the dimension of the involved quantum systems) on quantum violation for d=3,…,10 . The introduced class of information tasks, thus, provides for operational depiction of preparation contextuality of the ontic description underlying mixed higher dimensional quantum systems.
Despite the conceptual importance of contextuality in quantum mechanics, there is a hitherto limited number of applications requiring contextuality but not entanglement. Here, we show that for any quantum state and observables of sufficiently small dimensions producing contextuality, there exists a communication task with quantum advantage. Conversely, any quantum advantage in this task admits a proof of contextuality whenever an additional condition holds. We further show that given any set of observables allowing for quantum state-independent contextuality, there exists a class of communication tasks wherein the difference between classical and quantum communication complexities increases as the number of inputs grows. Finally, we show how to convert each of these communication tasks into a semi-device-independent protocol for quantum key distribution.