Quantum Memory Advantage from Contextuality

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 \ddot{I}‡(G)$ memory states, whereas a QFA requires a memory of dimension $d=\hat{I}¾(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^{\hat{I}\text{c◯}(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)$.

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

Topics & keywords