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

Quantum Memory Advantage from Contextuality

Shiroman Prakash

quant-phcs.FLmath.COSubmitted Jul 1, 2026• Announced Jul 2, 2026• 0 citations• Revised Jul 15, 2026 (v2)
v1 · Jul 1, 2026v2 · Jul 15, 2026
arXivHTMLPDF

Abstract

Quantum contextuality is a vital non-classical resource, yet illuminating the precise mechanisms through which it enables unconditional computational advantages remains a challenge. We translate graph-theoretic formulations of contextuality into an unconditional quantum memory advantage for formal language recognition. We define a promise problem on an exclusivity graph $G$ where any classical finite automaton respecting exclusivity requires $N \ge χ(G)$ memory states, whereas a QFA requires a memory of dimension $d = ξ(G)$. The gap between these bounds isolates a structural, information-theoretic incompatibility between classical and quantum descriptions that we term \textit{representational contextuality}. For Boolean orthogonality graphs, this exacts an exponential classical memory penalty ($d=\mathcal{O}(n)$ vs $N=2^{Ω(n)}$). Finally, we demonstrate a sharp algorithmic phase transition: allowing the classical machine a finite confusability of mutually exclusive events reduces this exponential classical memory cost to $\mathcal{O}(n)$.

Comments
12 pages, 4 figures total (includes Supplemental Material). v2: Main results tightened and extended to include bounded-error probabilistic automata and entropic bounds

Related papers

Implications of quantum automata for contextuality

Jibran Rashid, Abuzer Yakaryılmaz

We construct zero-error quantum finite automata (QFAs) for promise problems which cannot be solved by bounded-error probabilistic finite automata (PFAs). Here is a summary of our results: - There is a promise problem solvable by an exact two-way QFA in exponential expected time, but not by any bounded-error sublogarithmic space probabilistic Turing machine (PTM). - There is a promise problem solvable by an exact two-way QFA in quadratic expected time, but not by any bounded-error $ o(\log \log n) $-space PTMs in polynomial expected time. The same problem can be solvable by a one-way Las Vegas (or exact two-way) QFA with quantum head in linear (expected) time. - There is a promise problem solvable by a Las Vegas realtime QFA, but not by any bounded-error realtime PFA. The same problem can be solvable by an exact two-way QFA in linear expected time but not by any exact two-way PFA. - There is a family of promise problems such that each promise problem can be solvable by a two-state exact realtime QFAs, but, there is no such bound on the number of states of realtime bounded-error PFAs solving the members this family. Our results imply that there exist zero-error quantum computational devices with a \emph{single qubit} of memory that cannot be simulated by any finite memory classical computational model. This provides a computational perspective on results regarding ontological theories of quantum mechanics \cite{Hardy04}, \cite{Montina08}. As a consequence we find that classical automata based simulation models \cite{Kleinmann11}, \cite{Blasiak13} are not sufficiently powerful to simulate quantum contextuality. We conclude by highlighting the interplay between results from automata models and their application to developing a general framework for quantum contextuality.

arXiv:1404.2761•Apr 10, 2014•8 citations

The Logic of Contextuality

Samson Abramsky, Rui Soares Barbosa

Contextuality is a key signature of quantum non-classicality, which has been shown to play a central role in enabling quantum advantage for a wide range of information-processing and computational tasks. We study the logic of contextuality from a structural point of view, in the setting of partial Boolean algebras introduced by Kochen and Specker in their seminal work. These contrast with traditional quantum logic à la Birkhoff and von Neumann in that operations such as conjunction and disjunction are partial, only being defined in the domain where they are physically meaningful. We study how this setting relates to current work on contextuality such as the sheaf-theoretic and graph-theoretic approaches. We introduce a general free construction extending the commeasurability relation on a partial Boolean algebra, i.e. the domain of definition of the binary logical operations. This construction has a surprisingly broad range of uses. We apply it in the study of a number of issues, including: - establishing the connection between the abstract measurement scenarios studied in the contextuality literature and the setting of partial Boolean algebras; - formulating various contextuality properties in this setting, including probabilistic contextuality as well as the strong, state-independent notion of contextuality given by Kochen-Specker paradoxes, which are logically contradictory statements validated by partial Boolean algebras, specifically those arising from quantum mechanics; - investigating a Logical Exclusivity Principle, and its relation to the Probabilistic Exclusivity Principle widely studied in recent work on contextuality as a step towards closing in on the set of quantum-realisable correlations; - developing some work towards a logical presentation of the Hilbert space tensor product, using logical exclusivity to capture some of its salient quantum features.

arXiv:2011.03064•Leibniz international proceedings in informatics•Nov 5, 2020•8 citations

$k$-Contextuality as a Heuristic for Memory Separations in Learning

Mariesa H. Teo, Willers Yang, James Sud +3 more

Classical machine learning models struggle with learning and prediction tasks on data sets exhibiting long-range correlations. Previously, the existence of a long-range correlational structure known as contextuality was shown to inhibit efficient classical machine learning representations of certain quantum-inspired sequential distributions. Here, we define a new quantifier of contextuality we call strong$k$-contextuality, and prove that any translation task exhibiting strong$k$-contextuality is unable to be represented to finite relative entropy by a classical streaming model with fewer than$k$latent states. Importantly, this correlation measure does not induce a similar resource lower bound for quantum generative models. Using this theory as motivation, we develop efficient algorithms which estimate our new measure of contextuality in sequential data, and empirically show that this estimate is a good predictor for the difference in performance of resource-constrained classical and quantum Bayesian networks in modeling the data. Strong$k$-contextuality thus emerges as a measure to help identify problems that are difficult for classical computers, but may not be for quantum computers.

arXiv:2507.11604•IEEE International Conference on Quantum Computing and Engineering (QCE)•Aug 30, 2025•0 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

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

The logical structure of contextuality and nonclassicality

Songyi Liu, Yongjun Wang, Baoshan Wang +2 more

Abstract Quantum contextuality represents a fundamental form of nonclassicality in quantum mechanics. To provide a more complete characterization of nonclassical properties in quantum systems, we adopt a logical perspective and propose a mathematical framework based on exclusive partial Boolean algebras. This framework enables a unified description of contextuality and nonclassicality across finite general, quantum, and classical systems. We establish a unified and minimal classical counterpart for any finite general system. Within this framework, we formalize major categories of quantum contextuality, demonstrating that: 12 projectors suffice to generate Kochen–Specker scenarios; 10 projectors suffice to witness state-independent contextuality; and 3 observables suffice to witness quantum contextuality. Finally, we prove that contextuality is a sufficient but not necessary condition for nonclassicality.

arXiv:2506.15071•Journal of Physics A Mathematical and Theoretical•Jan 14, 2026•0 citations
Quantum contextuality is a vital non-classical resource, yet illuminating the precise mechanisms through which it enables unconditional computational advantages remains a challenge. We translate graph-theoretic formulations of contextuality into an unconditional quantum memory advantage for formal language recognition. We define a promise problem on an exclusivity graph GGG where any classical finite automaton respecting exclusivity requires N≥χ(G)N \ge χ(G)N≥χ(G) memory states, whereas a QFA requires a memory of dimension d=ξ(G)d = ξ(G)d=ξ(G). The gap between these bounds isolates a structural, information-theoretic incompatibility between classical and quantum descriptions that we term \textit{representational contextuality}. For Boolean orthogonality graphs, this exacts an exponential classical memory penalty (d=O(n)d=\mathcal{O}(n)d=O(n) vs N=2Ω(n)N=2^{Ω(n)}N=2Ω(n)). Finally, we demonstrate a sharp algorithmic phase transition: allowing the classical machine a finite confusability of mutually exclusive events reduces this exponential classical memory cost to O(n)\mathcal{O}(n)O(n).
We construct zero-error quantum finite automata (QFAs) for promise problems which cannot be solved by bounded-error probabilistic finite automata (PFAs). Here is a summary of our results: - There is a promise problem solvable by an exact two-way QFA in exponential expected time, but not by any bounded-error sublogarithmic space probabilistic Turing machine (PTM). - There is a promise problem solvable by an exact two-way QFA in quadratic expected time, but not by any bounded-error $ o(\log \log n) $-space PTMs in polynomial expected time. The same problem can be solvable by a one-way Las Vegas (or exact two-way) QFA with quantum head in linear (expected) time. - There is a promise problem solvable by a Las Vegas realtime QFA, but not by any bounded-error realtime PFA. The same problem can be solvable by an exact two-way QFA in linear expected time but not by any exact two-way PFA. - There is a family of promise problems such that each promise problem can be solvable by a two-state exact realtime QFAs, but, there is no such bound on the number of states of realtime bounded-error PFAs solving the members this family. Our results imply that there exist zero-error quantum computational devices with a \emph{single qubit} of memory that cannot be simulated by any finite memory classical computational model. This provides a computational perspective on results regarding ontological theories of quantum mechanics \cite{Hardy04}, \cite{Montina08}. As a consequence we find that classical automata based simulation models \cite{Kleinmann11}, \cite{Blasiak13} are not sufficiently powerful to simulate quantum contextuality. We conclude by highlighting the interplay between results from automata models and their application to developing a general framework for quantum contextuality.
Contextuality is a key signature of quantum non-classicality, which has been shown to play a central role in enabling quantum advantage for a wide range of information-processing and computational tasks. We study the logic of contextuality from a structural point of view, in the setting of partial Boolean algebras introduced by Kochen and Specker in their seminal work. These contrast with traditional quantum logic à la Birkhoff and von Neumann in that operations such as conjunction and disjunction are partial, only being defined in the domain where they are physically meaningful. We study how this setting relates to current work on contextuality such as the sheaf-theoretic and graph-theoretic approaches. We introduce a general free construction extending the commeasurability relation on a partial Boolean algebra, i.e. the domain of definition of the binary logical operations. This construction has a surprisingly broad range of uses. We apply it in the study of a number of issues, including: - establishing the connection between the abstract measurement scenarios studied in the contextuality literature and the setting of partial Boolean algebras; - formulating various contextuality properties in this setting, including probabilistic contextuality as well as the strong, state-independent notion of contextuality given by Kochen-Specker paradoxes, which are logically contradictory statements validated by partial Boolean algebras, specifically those arising from quantum mechanics; - investigating a Logical Exclusivity Principle, and its relation to the Probabilistic Exclusivity Principle widely studied in recent work on contextuality as a step towards closing in on the set of quantum-realisable correlations; - developing some work towards a logical presentation of the Hilbert space tensor product, using logical exclusivity to capture some of its salient quantum features.
kkk-Contextuality as a Heuristic for Memory Separations in Learning
Classical machine learning models struggle with learning and prediction tasks on data sets exhibiting long-range correlations. Previously, the existence of a long-range correlational structure known as contextuality was shown to inhibit efficient classical machine learning representations of certain quantum-inspired sequential distributions. Here, we define a new quantifier of contextuality we call strongkkk-contextuality, and prove that any translation task exhibiting strongkkk-contextuality is unable to be represented to finite relative entropy by a classical streaming model with fewer thankkklatent states. Importantly, this correlation measure does not induce a similar resource lower bound for quantum generative models. Using this theory as motivation, we develop efficient algorithms which estimate our new measure of contextuality in sequential data, and empirically show that this estimate is a good predictor for the difference in performance of resource-constrained classical and quantum Bayesian networks in modeling the data. Strongkkk-contextuality thus emerges as a measure to help identify problems that are difficult for classical computers, but may not be for quantum computers.
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 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.
Abstract Quantum contextuality represents a fundamental form of nonclassicality in quantum mechanics. To provide a more complete characterization of nonclassical properties in quantum systems, we adopt a logical perspective and propose a mathematical framework based on exclusive partial Boolean algebras. This framework enables a unified description of contextuality and nonclassicality across finite general, quantum, and classical systems. We establish a unified and minimal classical counterpart for any finite general system. Within this framework, we formalize major categories of quantum contextuality, demonstrating that: 12 projectors suffice to generate Kochen–Specker scenarios; 10 projectors suffice to witness state-independent contextuality; and 3 observables suffice to witness quantum contextuality. Finally, we prove that contextuality is a sufficient but not necessary condition for nonclassicality.