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:1607.05490 · Quantum Information Processing

Parity oblivious d-level random access codes and class of noncontextuality inequalities

Andris Ambainis, Manik Banik, Anubhav Chaturvedi, Dmitry Kravchenko, Ashutosh Rai

Published Mar 2, 2019• 64 citations
arXivHTMLPDF

Abstract

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 $$d_\mathrm{c}=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,\ldots ,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 $$d_\mathrm{q}=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,\ldots ,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,\ldots ,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.

DOI
10.1007/s11128-019-2228-3

Related papers

Characterising and bounding the set of quantum behaviours in contextuality scenarios

Anubhav Chaturvedi, Máté Farkas, Victoria J Wright

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.

arXiv:2010.05853•Quantum•Jun 29, 2021•29 citations

Optimal quantum preparation contextuality in an n -bit parity-oblivious multiplexing task

Shouvik Ghorai, A. K. Pan

In [Phys. Rev. Lett. 102, 010401 (2009)], Spekkens et al. have shown that quantum preparation contextuality can power the parity-oblivious multiplexing (POM) task. The bound on the optimal success probability of an $n$-bit POM task performed with the classical resources was shown to be the same as in a preparation noncontextual theory. This noncontextual bound is violated if the task is performed with quantum resources. While in the 2-bit POM task the optimal quantum success probability is achieved, in the 3-bit case optimality was left as an open question. In this paper, we show that the quantum success probability of an $n$-bit POM task is solely dependent on a suitable Bell expression and the optimal value of it optimizes the success probability of the said POM task. Further, we discuss how the degree of quantum preparation contextuality restricts the amount of quantum violations of Bell's inequalities, and consequently, the success probability of a POM task.

arXiv:1806.01194•Physical Review A•Sep 14, 2018•49 citations

Preparation contextuality as an essential feature underlying quantum communication advantage

Debashis Saha, Anubhav Chaturvedi

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.

arXiv:1802.07215•Physical Review A•Aug 7, 2019•50 citations

All-vs-Nothing Operational Manifestation of Preparation Contextuality

Jayashree Karmakar, Rafiuddin Gazi, Biswadeep Chatterjee +4 more

Preparation contextuality is often manifested operationally through a quantitative advantage over preparation-noncontextual models in information-processing tasks, yet quantum theory typically falls short of perfect success. Here we introduce a parity-oblivious Hidden Matching task that instead yields an all-vs-nothing manifestation of preparation contextuality. Alice encodes an $n$-bit string so that her message reveals no information about any input parity other than the two-bit parities. Bob, given a perfect matching on the input positions, must output an edge of the matching together with the parity of its two bits. A quantum protocol using a single $\lceil\log_2 n\rceil$-qubit message satisfies the parity-obliviousness constraint and succeeds with certainty. We prove that no preparation-noncontextual model achieves perfect success for any even $n\ge6$. The result holds for arbitrary ontic state spaces and assumes neither outcome determinism nor measurement noncontextuality. For $n=6$ and $n=8$, the optimal noncontextual success probabilities are $4/5$ and $3/4$, respectively, while asymptotically the optimal noncontextual success probability is $1/2+Θ(1/\sqrt n)$. Our asymptotic upper bound follows from a Fourier-analytic sum rule derived via hypercontractivity on the Boolean hypercube. The resulting separation is qualitative rather than merely quantitative: quantum theory achieves perfect success, whereas preparation-noncontextual models cannot. We aslo show that at $n=8$ the noncontextual bound remains $3/4$ even when Bob is restricted to just suitable $4$ of the $105$ possible perfect matchings, bringing the effect within experimental reach.

quant-pharXiv:2609.34964•Sep 29, 2026•0 citations

Exclusion reshapes the operational manifestation of preparation contextuality

Pritam Roy, Thansingh Jankawat, Ranendu Adhikary +1 more

Replacing the task of retrieval with exclusion changes how preparation contextuality manifests operationally under parity-oblivious constraints, with exclusion showing a quantum advantage where retrieval does not. We introduce the parity-oblivious random exclusion code (POREC) and show that for prime symbol size $m$, classical and preparation-noncontextual encodings provide a tight noncontextual bound. For the first nontrivial case (two digits, three symbols), our derived exact qubit optimum violates this bound, in contrast to parity-oblivious retrieval, which displays no quantum advantage. This characteristic difference is absent without parity constraints. For general prime $m$, qubit strategies achieve a quantum-to-noncontextual gap that grows linearly relative to the random exclusion code (REC) gap, exceeding both parity-oblivious retrieval and standard REC. The exact qubit bound yields a sharp semi-device-independent certification of dimension $d \geq 3$. Our analysis of noise robustness demonstrates POREC to be amenable for experimental implementation on existing prepare-and-measure platforms, establishing parity-oblivious exclusion as a distinct operational probe of preparation contextuality, as well as a practical information processing protocol with wide applications.

quant-pharXiv:2605.08745•May 12, 2026•0 citations

Generalized parity-oblivious communication games powered by quantum preparation contextuality

Prabuddha Roy, A. K. Pan

Abstract The parity-oblivious random-access-code (PORAC) is a class of communication games involving a sender (Alice) and a receiver (Bob). In such games, Alice’s amount of communication to Bob is constraint by the parity-oblivious (PO) conditions, so that the parity information of her inputs remains oblivious to Bob. The PO condition in an operational theory is equivalently represented in an ontological model that satisfies the preparation noncontextuality. In this paper, we provide a nontrivial generalization of the existing two-level PORAC and derive the winning probability of the game in the preparation noncontextual ontological model. We demonstrate that the quantum theory outperforms the preparation noncontextual model by predicting higher winning probability in our generalized PORAC.

arXiv:2311.04490•Journal of Physics A Mathematical and Theoretical•Aug 19, 2024•6 citations
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=dd_\mathrm{c}=ddc​=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,…,10d=3,\ldots ,10d=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,5d=3,4,5d=3,4,5 employing dq=dd_\mathrm{q}=ddq​=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,…,10d=3,\ldots ,10d=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,…,10d=3,\ldots ,10d=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.
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.
In [Phys. Rev. Lett. 102, 010401 (2009)], Spekkens et al. have shown that quantum preparation contextuality can power the parity-oblivious multiplexing (POM) task. The bound on the optimal success probability of an nnn-bit POM task performed with the classical resources was shown to be the same as in a preparation noncontextual theory. This noncontextual bound is violated if the task is performed with quantum resources. While in the 2-bit POM task the optimal quantum success probability is achieved, in the 3-bit case optimality was left as an open question. In this paper, we show that the quantum success probability of an nnn-bit POM task is solely dependent on a suitable Bell expression and the optimal value of it optimizes the success probability of the said POM task. Further, we discuss how the degree of quantum preparation contextuality restricts the amount of quantum violations of Bell's inequalities, and consequently, the success probability of a POM task.
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.
Preparation contextuality is often manifested operationally through a quantitative advantage over preparation-noncontextual models in information-processing tasks, yet quantum theory typically falls short of perfect success. Here we introduce a parity-oblivious Hidden Matching task that instead yields an all-vs-nothing manifestation of preparation contextuality. Alice encodes an nnn-bit string so that her message reveals no information about any input parity other than the two-bit parities. Bob, given a perfect matching on the input positions, must output an edge of the matching together with the parity of its two bits. A quantum protocol using a single ⌈log⁡2n⌉\lceil\log_2 n\rceil⌈log2​n⌉-qubit message satisfies the parity-obliviousness constraint and succeeds with certainty. We prove that no preparation-noncontextual model achieves perfect success for any even n≥6n\ge6n≥6. The result holds for arbitrary ontic state spaces and assumes neither outcome determinism nor measurement noncontextuality. For n=6n=6n=6 and n=8n=8n=8, the optimal noncontextual success probabilities are 4/54/54/5 and 3/43/43/4, respectively, while asymptotically the optimal noncontextual success probability is 1/2+Θ(1/n)1/2+Θ(1/\sqrt n)1/2+Θ(1/n​). Our asymptotic upper bound follows from a Fourier-analytic sum rule derived via hypercontractivity on the Boolean hypercube. The resulting separation is qualitative rather than merely quantitative: quantum theory achieves perfect success, whereas preparation-noncontextual models cannot. We aslo show that at n=8n=8n=8 the noncontextual bound remains 3/43/43/4 even when Bob is restricted to just suitable 444 of the 105105105 possible perfect matchings, bringing the effect within experimental reach.
Replacing the task of retrieval with exclusion changes how preparation contextuality manifests operationally under parity-oblivious constraints, with exclusion showing a quantum advantage where retrieval does not. We introduce the parity-oblivious random exclusion code (POREC) and show that for prime symbol size mmm, classical and preparation-noncontextual encodings provide a tight noncontextual bound. For the first nontrivial case (two digits, three symbols), our derived exact qubit optimum violates this bound, in contrast to parity-oblivious retrieval, which displays no quantum advantage. This characteristic difference is absent without parity constraints. For general prime mmm, qubit strategies achieve a quantum-to-noncontextual gap that grows linearly relative to the random exclusion code (REC) gap, exceeding both parity-oblivious retrieval and standard REC. The exact qubit bound yields a sharp semi-device-independent certification of dimension d≥3d \geq 3d≥3. Our analysis of noise robustness demonstrates POREC to be amenable for experimental implementation on existing prepare-and-measure platforms, establishing parity-oblivious exclusion as a distinct operational probe of preparation contextuality, as well as a practical information processing protocol with wide applications.
Abstract The parity-oblivious random-access-code (PORAC) is a class of communication games involving a sender (Alice) and a receiver (Bob). In such games, Alice’s amount of communication to Bob is constraint by the parity-oblivious (PO) conditions, so that the parity information of her inputs remains oblivious to Bob. The PO condition in an operational theory is equivalently represented in an ontological model that satisfies the preparation noncontextuality. In this paper, we provide a nontrivial generalization of the existing two-level PORAC and derive the winning probability of the game in the preparation noncontextual ontological model. We demonstrate that the quantum theory outperforms the preparation noncontextual model by predicting higher winning probability in our generalized PORAC.