{"id":"arxiv/2607.00507","url":"https://arxiv.org/abs/2607.00507","tags":["quant-ph","cs.FL","math.CO"],"score":0,"title":"Quantum Memory Advantage from Contextuality","domain":"quant-ph","source":"arxiv","authors":["Shiroman Prakash"],"reviews":0,"subject":"quant-ph","summary":"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,…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-07-01","reactions":{}}