Robust Quantum Memory Advantage from Contextuality
2026-07-01 • Formal Languages and Automata Theory
Formal Languages and Automata Theory
AI summaryⓘ
The authors show that certain quantum machines, called quantum finite automata (QFA), can solve specific problems using much less memory than classical machines. They base their approach on special graphs and a property called contextuality, which affects how information is represented. Specifically, the QFA uses a number of states related to a graph parameter called orthogonal rank, while classical machines need states related to the graph's chromatic number, causing an exponential difference. This advantage remains even when noise is present, making it robust for practical use.
Quantum contextualityQuantum finite automataGraph theoryExclusivity graphChromatic numberOrthogonal rankNon-contextual hidden variable modelsDepolarizing noiseCoherent noisePromise problem
Authors
Shiroman Prakash
Abstract
Quantum contextuality is widely recognized as an essential non-classical resource underlying quantum technology, yet illuminating the precise mechanisms through which it translates into unconditional computational advantages remains an ongoing challenge. We demonstrate an exponential, noise-resilient memory advantage for quantum finite automata arising from graph-theoretic approaches to contextuality. We define a promise problem on an exclusivity graph $G$ for which any classical deterministic automaton acts as a non-contextual hidden variable model requiring at least $N=χ(G)$ states, where $χ(G)$ is the graph's chromatic number. In contrast, by exploiting a structural phenomenon we term \textit{representational contextuality}, a QFA solves this task using a memory of dimension at most $d=ξ(G)+1$, where $ξ(G)$ is the graph's orthogonal rank. This separation scales exponentially ($d=\mathcal O(n)$ versus $N=2^{Ω(n)}$) for Boolean-orthogonality graphs. Crucially, this memory advantage maintains an $\mathcal{O}(1)$ threshold against both depolarizing and coherent noise.