Quantum Coordination Advantages in AI State-Tracking Tasks: Semantic Compilation and Latent Memory

Quantum Coordination Advantages in AI State-Tracking Tasks: Semantic Compilation and Latent Memory Ming Yang August 12, 2026

arXiv:2608.11066v1 [quant-ph] 11 Aug 2026

Abstract We prove inference-time quantum coordination advantages for specified AI state-tracking tasks. A solver compresses semantic history into a future-accessible boundary state and later answers a query. We count communication B, persistent instance-dependent memory M , and local work D; classical recurrence, caches, tools, and recomputation are allowed and charged. The central result is a boundary-preserving semantic-compilation theorem. It maps a finite one-way, streaming, or adaptive causal task into a semantic AI interface while preserving event order and access to past input. Classical boundary-state lower bounds and quantum-memory upper bounds transfer up to explicit compiler overhead, independently of the finite-precision recurrent architecture. Two applications have classical semantics. Matched-entity √ synopsis QA inherits the hidden-matching separation between O(log N ) qubits and Ω( N ) classical boundary bits. Continual requirements auditing inherits a Max-kSAT streaming separation: a recurrent solver uses O(log5 n log(1/δ)) qubits and polylogarithmic classical workspace to obtain a 0.7172-approximation,√whereas every classical one-pass finite-information solver attaining that ratio requires Ω( n) coordination width. As a quantum-native compiler test, a stabilizer latent-state dialogue uses n qubits, while every exact finite-state classical causal online realization satisfies B + M ≥ 21 n2 + ( 32 − log2 3)n + O(1). The source protocols, streaming algorithms, and stabilizer witness are imported; the new result is their architecture-independent semantic transfer. These are memory and coordination separations, not runtime or empirical advantages for present-day language models. The stabilizer result assumes exact simulation and ideal noiseless quantum memory.

1

Introduction

Generative modeling is often described as the problem of sampling outputs that look locally plausible under a learned distribution. For many tasks this is not enough. A model must also preserve an implicit state: the identity of an object in a story, the value of an unobserved variable, the current branch of a plan, the state of a simulated world, or the latent rule governing future observations. We call this requirement state tracking or latent-state persistence. Recent analyses of transformer architectures identify state tracking as a structural bottleneck [1, 2]. They also make clear that classical architectures have real repair mechanisms: add recurrence, add a state-space memory, write a scratchpad, use tools or external memory, increase reasoning depth, or run a looped/iterative model. These repairs are important. They mean that the right theoretical question is not Can a classical model track state at all? but rather How much communication, memory, and computation does it need? 1

This note develops that second question. The guiding principle is boundary-relative: once a computational boundary Σ is chosen, an explicit signal crossing it is communication, a state retained across it is memory, and local iterative work performed after crossing it is computation depth. The same engineering device may therefore play different roles under different cuts. A scratchpad token is just part of the input if it is supplied by the environment, but it is communication if it was written by an earlier computational event to coordinate a later one. A recurrent hidden vector is a memory resource; an external memory lookup may combine communication and memory; additional latent thinking steps increase local depth. This accounting follows the general spacetime-separator framework of Ref. [3], which also distinguishes general classical causal simulation from restricted global-chart covering. Relation to quantum generative models. Quantum generative models have already been shown to have expressive advantages over several classical generative model classes [4]. The goal here is not to restate that claim. Instead we ask whether quantum models can reduce the coordination cost of maintaining a latent state. For ordinary classical latent variables, there is no reason to expect a universal quantum advantage: a classical recurrent model can simply store the variable if enough memory is available. A sharper target is a noncommuting latent state, where the current query selects a measurement context and no small classical hidden state can consistently answer all possible queries. Contextuality, predictive quantum memory, and stabilizer simulation lower bounds then become candidates for proving classical coordination costs. What would count as an advantage? The advantage studied here is not a vague increase in sample quality. It is a resource separation. For a family of target processes Pn , one wants log2 KclD,ϵ (Pn ; Σ) − log2 Kqϵ (Pn ; Σ) to grow with n, or equivalently a lower bound on the classical coordination bits B + M that is larger than the number of qubits needed by a quantum recurrent generator. A useful result must compare against classical models that are allowed to use the obvious repairs: recurrence, scratchpads, external memory, and additional computation. The streaming-derived results below are specifically space or retained-information separations rather than time-complexity separations: the classical update map may perform arbitrary computation within the one-pass access model, while all information that survives the next online boundary is charged. In the general coordination region, local work is still recorded by D; no result here claims a runtime speedup. Contributions and status.

The paper makes three linked contributions.

1. It defines an inference-time quantum-AI state-tracking interface and places classical architectural repairs inside the B, M, D accounting of Ref. [3], while keeping general causal simulation separate from restricted chart and ontological baselines. 2. It proves a boundary-preserving semantic-compilation theorem, together with one-way and online specializations, that transfers classical space lower bounds and quantum-memory upper bounds to arbitrary finite-precision recurrent AI solvers. 3. It instantiates the compiler with matched-entity QA, continual requirements auditing, and contextual latent-state persistence. The first two import communication or streaming separations; the third imports the finite stabilizer witness of Ref. [3]. The new claim is preservation under the AI interface, not a new hidden-matching, streaming, or stabilizer lower bound.

2

2

Boundary-Relative Coordination Cost

Let P be a target generative process. At time t, the past history is ht = (c1 , o1 , . . . , ct−1 , ot−1 ), the current condition or query is ct , and the model outputs ot . A computational boundary Σt separates the event that has processed ht from the event that must respond to ct . Definition 1 (Coordination resources). Relative to Σt , define: B : explicit information crossing the boundary, M

: internal state retained across the boundary,

D : local processing depth after the boundary. The unit of B and M is the bit. For a finite hidden-state space Λ, storing a state requires ⌈log2 |Λ|⌉ bits. Definition 2 (Generative coordination region). For a model class A, error tolerance ϵ, and boundary choice Σ, define CostϵA (P ; Σ) = {(B, M, D) : some A-generator simulates P within error ϵ using (B, M, D)}. The distance of this region from the origin measures the coordination burden of the process under the chosen boundary. Remark 1. The boundary is part of the model. The prompt or context is not automatically communication. It counts as communication only when it carries information from one modeled computational event to another. This convention prevents the resource accounting from prejudging whether a long context, a scratchpad, a KV cache, or a recurrent state is the relevant resource.

2.1

General and restricted classical baselines

The term classical simulation has two different strengths that must not be conflated [3]. A general classical causal simulator may use randomized, context-dependent response kernels and adaptive state updates. Its complete future-accessible boundary configuration λ must contain all past-dependent information available after the cut, but the transition and response rules themselves are unrestricted. For a static past–future probability table FΣ (P )u,v = Pr(U = u, V = v), P

the general separator theorem gives B + M ≥ log2 rank+ FΣ (P ). For an online process with Hankel table HP , the corresponding quantity is the causal positiverealization rank: one common family of response and update kernels must realize every history and continuation. At depth D, B + M ≥ log2 rankcausal,D (HP ). + These are general within the stated causal boundary and access model.

3

A restricted chart simulator instead requires every counted transcript–memory state to select a context-independent global response chart. Its covering-number bound B + M ≥ log2 χD G applies only to that cover-admissible class. A KWB-compatible stabilizer simulator is a different restricted sequential model: it imposes exact state update and single-shot-distinguishability support conditions. Neither a chart covering lower bound nor a KWB support-counting lower bound applies to a general causal simulator without an explicit reduction. For the exact stabilizer family used below, Ref. [3] supplies that reduction by constructing a finite adaptive witness whose partitioning and distinguishing tests force the KWB overlap count on every finite-state causal realization. Accordingly, KclD,ϵ below is always relative to a named classical model class. When a concrete theorem uses an unrestricted one-way or one-pass baseline, it says so. When only a chart, HMM, or other restricted lower bound is available, the restriction is part of the claim and must not be silently promoted to a bound on arbitrary classical AI.

3

Classical Latent-State Generators

A finite classical latent-state generator has hidden state λt ∈ Λ. The past history prepares a distribution over hidden states, wt (λ) = w(λ | ht ), and the current query ct is answered by a response kernel R(ot | ct , λt ). Thus q(ot | ht , ct ) =

X

w(λt | ht )R(ot | ct , λt ).

λt ∈Λ

After observing ct , ot , the state may update by another stochastic kernel U (λt+1 | λt , ct , ot ). Definition 3 (Classical state complexity). Let KclD,ϵ (P ; Σ) be the minimum number of classical hidden coordination states needed by a depth-D classical generator to simulate P within error ϵ relative to Σ. The associated memory cost is m l MclD,ϵ (P ; Σ) = log2 KclD,ϵ (P ; Σ) . Definition 4 (Quantum state complexity). Let Kqϵ (P ; Σ) be the minimum Hilbert-space dimension needed by a quantum latent-state generator to simulate P within error ϵ relative to Σ. The associated quantum memory cost is   Qϵ (P ; Σ) = log2 Kqϵ (P ; Σ) qubits. The classical model class is an argument suppressed by the notation. Thus KclD,ϵ may denote the general causal class, an HMM class, or a more restricted simulator class only when that choice is stated locally. Proposition 1 (Basic state-count lower bound). Suppose a simulator with B bits of explicit boundary communication and M bits of retained memory can select among at most 2B+M effective classical coordination states in a depth-D model class. Then exact or ϵ-approximate simulation of P implies B + M ≥ log2 KclD,ϵ (P ; Σ). 4

Proof. The transcript and retained memory jointly take at most 2B+M values. If each value determines one effective state of the simulator class, then the simulator can realize no more than 2B+M effective coordination states. By minimality of KclD,ϵ (P ; Σ), this number must be at least KclD,ϵ (P ; Σ). Proposition 2 (Ordinary latent-state repair). Suppose P has a finite classical sufficient state zt ∈ Z such that P (ot | ht , ct ) = P (ot | zt , ct ) and zt+1 is sampled from a kernel depending only on (zt , ct , ot ). Then, for a model class that can implement the required kernels at depth D, KclD,0 (P ; Σ) ≤ |Z|,

MclD,0 (P ; Σ) ≤ ⌈log2 |Z|⌉.

Proof. Use the sufficient state itself as the hidden coordination state λt = zt . The response and update kernels are precisely the kernels given in the hypothesis. Remark 2. This elementary upper bound is the reason that transformer failures alone do not prove a quantum advantage. A recurrent classical model may repair the failure by spending memory. The relevant question is whether the required classical memory, communication, or depth grows asymptotically faster than the quantum latent state needed for the same process.

4

Classical Repairs as Resource Moves

This section records how common classical repairs to state-tracking failures fit the resource region. 1. Recurrence and state-space models. Recurrent neural networks, state-space models, and recurrent transformers carry a hidden state across time. In the present accounting, they primarily increase M . 2. Scratchpads and chain-of-thought traces. When an earlier generation step writes information for a later step to read, the trace is explicit boundary traffic. It is therefore a B-type resource under that time cut. 3. External memory and tools. Tool calls and retrieval systems mix communication and memory: the main generator sends a query, receives a message, and may store a summary. 4. Latent thinking and iterative inference. Extra internal iterations increase D, the local processing depth available after the current condition is known. 5. Long context. Long context is not automatically a cost. If it is supplied as part of the task input, it is data. If it is generated or compressed by the model to coordinate future events, it is part of the resource accounting. Thus classical solutions are not dismissed. They are the baselines whose resource costs the theory tries to quantify.

5

Quantum and Noncommuting Latent States

A quantum latent-state generator carries a density operator ρt ∈ D(Ht ).

5

For each current condition ct , the generator uses a POVM {Moct }o and outputs p(ot | ht , ct ) = Tr(Moctt ρt ). The latent state then updates by a quantum instrument, ρt+1 = Ect ,ot (ρt ). The important distinction is not merely that ρt is continuous or random. It is that different queries ct may correspond to noncommuting measurements. A classical hidden state can answer all queries by carrying a large enough table of counterfactual responses. Contextuality lower bounds ask how large that table, or the coordination mechanism selecting among tables, must be. Definition 5 (Noncommuting latent-state task). A latent-state tracking task is noncommuting if there are query contexts c, c′ whose associated measurements cannot be jointly represented as coarse-grainings of one fixed classical response variable without increasing the hidden coordination state space. In finite measurement scenarios this condition can be formalized by the absence, or high cost, of a noncontextual/global-chart representation of the induced empirical model. Definition 6 (Induced one-step empirical model). Fix a history class H and a set of allowed queries C. The one-step empirical model induced by P is the family Eh = {P (· | h, c) : c ∈ C}h∈H . A classical hidden-state representation with K states writes every member as P (o | h, c) ≈

K X

wh (λ)R(o | c, λ).

λ=1

If the same λ must answer several incompatible queries c, the problem reduces to finding small classical charts for the query family. Proposition 3 (Contextual coordination lower bound). Let P induce a finite query model Eh , and fix a classical model class C. If every depth-D representation in C within error ϵ needs at least K effective states, then any depth-D implementation in C with boundary resources (B, M ) must satisfy B + M ≥ log2 K. Proof. This is the basic state-count lower bound applied to the induced query model. Each boundary transcript and retained state selects one effective classical response state for the query family. Fewer than K such states cannot realize the required empirical model within the specified error. Remark 3. Ordinary natural-language ambiguity or hidden world state is not by itself evidence for quantum advantage. The quantum advantage target is narrower: latent states whose observable queries have a contextual or noncommuting structure, or classical stochastic processes whose predictive states admit a provably smaller quantum representation.

6

6

Separation Criterion

The preceding definitions give a simple separation template. Theorem 1 (Coordination-cost separation criterion). Let Pn be a family of generative processes and Cn a named classical simulator class. Suppose: 1. there is a quantum latent-state generator for Pn with Hilbert-space dimension dn , and 2. every depth-Dn generator in Cn simulating Pn within error ϵn needs at least Ln hidden coordination states. Then every such implementation in Cn satisfies B + M ≥ log2 Ln , whereas the quantum implementation uses at most ⌈log2 dn ⌉ qubits of latent memory. The separation is linear, polynomial, or exponential according to the growth of log2 Ln − log2 dn . Proof. The classical bound is Proposition 3. The quantum upper bound is the definition of Hilbert-space dimension as quantum memory. The final statement is only a naming convention for the asymptotic gap. This theorem is deliberately formal. It identifies exactly what has to be proved in any proposed application: a quantum generator of small dimension and a lower bound on classical coordination states against the chosen classical baseline.

7

Related Work: Expressivity, Memory, and State Tracking

Prior work on quantum generative models shows that quantum correlations can increase the expressive power of Born machines, quantum circuit generators, and related models [4]. Recent work has also emphasized the need for task-level metrics when assessing whether such expressive advantages matter for practical learning problems [5]. Quantum predictive-memory separations similarly show that quantum states can reduce the memory needed to simulate certain stochastic processes [6, 7]. That line of work is about representing or sampling distributions. The present note asks a different but related question: whether maintaining a latent state over time can be done with less coordination. An expressivity advantage asks which distributions can be represented compactly. A coordination advantage asks how many states, messages, or update steps are needed to preserve one latent process. The two can interact. A distributional separation may imply a state-complexity separation for a one-shot process, while a recurrent contextual process may produce an advantage even when each local output distribution is simple. Contextuality as classical memory cost. Sequential contextuality was already formulated as a classical internal-memory cost by Kleinmann et al., and Fagundes and Kleinmann extended that analysis to the full probabilistic Peres–Mermin correlations [8, 9]. Karanjai, Wallman, and Bartlett later obtained growing stabilizer-simulation memory bounds [10]. Most directly, Prakash converts graph-theoretic contextuality into an exponential quantum-memory advantage for a formal-language promise problem, including bounded-error probabilistic automata and 7

entropic bounds [11]. That result uses a quantum finite automaton and an exclusivity-sensitive classical automaton model; allowing finite confusability changes its exponential conclusion. It is direct prior art for contextuality-to-memory advantage and is not subsumed here. Conversely, the present theorem concerns a generic boundary-preserving compiler across named one-way, streaming, and adaptive causal access models; it does not reproduce Prakash’s bounded-error automata result. AI state tracking and architectural lower bounds. Language-model state tracking has also been studied through learned permutation-composition mechanisms, expressivity limits for state-space models, and communication-complexity limitations of transformer layers [12, 13, 14]. These results motivate the semantic interfaces used below, but they diagnose particular architectures or learned mechanisms. The present resource comparison instead charges the complete future-accessible state of any solver in the named access model and asks whether quantum memory changes that cost. Relation to Gao et al. and strong k-contextuality. Gao et al. show that quantum correlations can give compact generative representations outside the reach of selected classical Bayesian-network and neural-network families, and they explicitly connect their separations to nonlocality and contextuality [4]. Their hidden-Markov-model result is especially close: a basis-enhanced 2-gram model with state-space dimension D cannot, under their support/KL criterion, be represented by a translation-form classical HMM with fewer than DΩ(log D) hidden units. Since the logarithm of the hidden-state count is a memory cost, this already has the shape classical memory = Ω((log D)2 ), quantum memory = O(log D), for that simulator class. Teo et al. give a still more direct precursor to the contextual memory interpretation [15]. They define strong k-contextuality for translation tasks and show that a strongly k-contextual task cannot be represented to finite relative entropy by a classical streaming model with fewer than k latent states. They also give algorithms for estimating the relevant contextuality quantity and study it as an empirical heuristic for memory separation. Their theorem already establishes a contextuality-to-classical-memory link; the present paper does not claim that link as new. The present note should therefore not be read as discovering that quantum correlations can help generative models. Rather, it recasts such separations as boundary-relative coordination statements and connects them to modern state-tracking failures. Relative to Gao et al. and Teo et al., the added claims are the boundary-preserving semantic transfer across one-way, streaming, and adaptive causal access models, together with explicit B, M, D accounting across recurrent AI repairs. If a classical model repairs a deficit by carrying a larger recurrent state, writing a scratchpad, using external memory, or recomputing from the transcript, those repairs are allowed but charged to M , B, or D. In this language, Gao et al.’s HMM separation and Teo et al.’s strong k-contextuality theorem are precursor coordination-cost statements; the contextual-LSP and dialogue formulations below ask for corresponding statements under an explicit interactive boundary.

8

Boundary-Preserving Semantic Compilation

The source of a quantum advantage may be a communication problem, a streaming algorithm, or an adaptive quantum process. To make it an AI state-tracking task, one must encode its events as semantic inputs and its answers as task-level outputs without changing what information is available at each time. The following definition isolates that requirement.

8

Definition 7 (Boundary-preserving semantic compiler). Let Πn be a finite task with an ordered sequence of environment events, solver actions, and computational boundaries specified by an access model An . A boundary-preserving semantic compiler maps each source event online to a finite text, symbolic, or multimodal block and maps solver outputs back to the source output alphabet. It must: 1. preserve the event order, adaptive choices, and source boundaries; 2. never re-supply a past source event after its boundary unless that record is explicitly charged as persistent state; 3. preserve the source acceptance relation or transcript distribution up to error ηn ; and 4. use at most an bits of parser, renderer, and compiler workspace, including every compiler record retained across a source boundary. The resulting semantic task is denoted SemAn (Πn ). Let CclA,ϵ (Πn ) denote the minimum peak number of classical bits in the complete futureaccessible boundary state of a finite-state causal solver for Πn with error at most ϵ. A quantum resource profile (qn , cn ) means qn retained qubits and cn retained classical bits under the same access model. Theorem 2 (Semantic coordination transfer). Let SemAn be a boundary-preserving semantic compiler with workspace an , compilation error ηn , and at most Tn event boundaries. Then: 1. every classical solver for SemAn (Πn ) with error at most ϵ and peak coordination width WΣ satisfies WΣ ≥ CclA,ϵ+ηn (Πn ) − an − O(log Tn ); 2. if Πn has a quantum solver with error at most ϵ and resource profile (qn , cn ), then the compiled semantic task has a solver with error at most ϵ + ηn using qn qubits and cn + an + O(log Tn ) classical bits across the corresponding boundaries. For an exact eventwise compiler that retains no additional instance-dependent state, exact classical causal-state lower bounds and quantum-memory upper bounds are preserved without asymptotic loss. Proof. Compose a classical semantic solver with the online encoder, parser, and output decoder. Because the compiler preserves event order and does not reintroduce expired source records, the composition is a valid An -solver for Πn . At each source boundary its complete state consists of the semantic solver’s state, at most an compiler bits, and O(log Tn ) event-counter bits. Its error is at most ϵ + ηn . The definition of CclA,ϵ+ηn gives the first inequality. For the quantum direction, run the semantic parser online, apply the source quantum channel or measurement selected by the decoded event, retain its qn -qubit state and cn -bit classical state, and render the source output semantically. The workspace and error overheads are those stated. When the compiler is exact and retains no state, the compositions preserve the source boundary-state sets themselves, giving the final claim. This theorem is the paper’s central transfer principle. It does not create a new quantum communication protocol, streaming algorithm, or contextuality lower bound. It states when any such result becomes an inference-time quantum AI result rather than a superficial relabelling: the semantic interface must preserve the causal boundary on which the resource comparison is made. 9

9

AI State-Tracking Baselines and One-Way Applications

Transformer state-tracking failures provide the motivating classical bottleneck [16, 1, 2]. A feed-forward transformer can often use the context as a workaround, but persistent dynamic state is not free: the state must be stored, rewritten, copied into a scratchpad, retrieved from memory, or recomputed. The coordination-cost picture turns those engineering choices into resource moves: recurrence 7→ M,

scratchpad or tool messages 7→ B,

extra latent computation 7→ D.

This perspective treats classical repairs as serious baselines. A quantum proposal must beat not only a plain transformer, but also classical models that are allowed to spend the relevant B, M, D resources. Latent-state persistence benchmarks. The latent-state-persistence tasks of Huang et al. are useful because they separate local linguistic plausibility from the ability to preserve a hidden state across many queries [1]. In this paper they play the role of a classical stress test, not a quantum benchmark. Number guessing, yes/no state tracking, and related tasks can usually be repaired by giving the classical model a sufficient recurrent state, a scratchpad, or external memory. The contribution of the present framework is to charge those repairs: the recurrent state contributes to M , the scratchpad contributes to B, and repeated inference contributes to D. To obtain a specifically quantum advantage, one must enrich this kind of benchmark so that the hidden state is not merely unknown but query-contextual or noncommuting. Topological state-tracking dialogues. The state-tracking problems emphasized by Mozer, Siddiqui, and Liu provide a second useful shell [2]. A transcript describes a path of local updates, and later prompts query the current state. If the state space is an ordinary classical space, this again admits an ordinary recurrent repair: store a sufficient coordinate for the current state. The route to a quantum separation is therefore not to claim that these classical tasks are already quantum, but to keep their dialogue structure while replacing the tracked state by a noncommuting latent state. The history then prepares ρh , the prompt selects a measurement context c, and the answer is sampled from Tr(Moc ρh ). In this form, the topological/statetracking burden is preserved, but the classical repair is no longer a small coordinate; it is a contextual response chart whose size can be lower-bounded. Relational state tracking. Multi-entity text tasks provide a natural source of large coordination costs. If a history determines N = Θ(n2 ) independent pairwise facts among n entities and a query asks for any selected fact, then an exact classical tracker needs Θ(n2 ) retained bits. However, this observation alone does not imply a quantum advantage. An m-qubit latent representation that can answer any one of the N independent facts with success probability p > 1/2 is a quantum random-access code, so Nayak’s bound gives m ≥ (1 − H2 (p))N = Ω(n2 ), where H2 is the binary entropy [17]. Thus an arbitrary classical relation table cannot be compressed to O(n) qubits if the benchmark allows reliable random access to all its entries. The plausible quantum target is narrower: the text-induced IO relation should have high classical coordination rank but low quantum, or positive semidefinite, rank. In binary-output form, a family of histories and queries defines a nonnegative matrix Ah,c = P (o = 1 | h, c).

10

A classical latent-state factorization corresponds to a nonnegative factorization of A, while a quantum latent-state representation has the form Ah,c = Tr(Ec ρh ), which is a positive-semidefinite factorization [18]. A natural-text or text-wrapped relational benchmark would therefore show a coordination advantage only if its conditional-response matrix has large nonnegative rank but small PSD rank. Stabilizer state tracking is one structured instance of this pattern: it is not an arbitrary table of classical pairwise facts, but a noncommuting relational state whose query responses are compactly represented by an n-qubit state. A more classical-looking route comes from one-way communication complexity. Here it serves as a calibration of the same boundary resource, stated at the level of a general readingcomprehension schema rather than a single hand-picked relation.

9.1

One-way communication calibration

Definition 8 (Entity-attribute synopsis QA). An entity-attribute synopsis QA family consists of finite sets XN of passage states, CN of query contexts, and ON of answers, together with a relation RN ⊆ XN × CN × ON . A passage hx is an unambiguous text encoding of an entity-attribute state x ∈ XN . A query c ∈ CN is revealed after the passage has been processed. A valid answer is any o ∈ ON such that (x, c, o) ∈ RN . The benchmark boundary is essential. The passage is read first, then only a boundary state is retained, and the query is revealed later. If the full passage is carried across the boundary, its length is charged to B; if a classical model rereads or rescans the passage after seeing the query, that repair is charged to D. Corollary 1 (One-way lift to synopsis QA). Suppose the relation problem RN , under a chosen input distribution, admits a one-way quantum protocol with qN qubits and success probability at least 1 − ϵ, while every one-way randomized classical protocol with the same success probability requires at least cN bits. Then the corresponding entity-attribute synopsis QA family has a quantum state-tracking solver using qN qubits across the passage–query boundary, and every classical solver in the same one-way boundary model satisfies B + M ≥ cN . Proof. This is the exact one-boundary specialization of Theorem 2, with the passage and query as the two source events and no retained compiler state. The quantum upper bound is obtained by running the quantum one-way encoder after parsing the passage and retaining its qN -qubit message as the boundary state. After the query is revealed, the query responder runs the one-way decoder and renders its output as text. Conversely, any classical QA solver using m = B +M boundary bits gives a one-way classical protocol for RN : Alice parses x, forms the passage hx , runs the passage processor, and sends the resulting boundary state to Bob; Bob parses c, runs the query responder, and outputs its answer. Thus m ≥ cN . The content is therefore not tied to a specific Boolean operation. Direct random access to arbitrary entity attributes is ruled out by the quantum random-access-code obstruction above, but any entity-attribute relation family with a one-way quantum/classical separation yields a synopsis-QA separation. Hidden matching is a simple instantiation of this more general lifting principle. 11

In that instantiation, a passage describes N named records, each with a binary attribute such as cohort, stance, access level, or case label. After the passage has been processed, a later query gives a list of disjoint record pairs and asks the model to report any listed pair together with whether the two records have the same or different labels. This is a normal database-style question about entities and relations; it does not mention quantum physics. Under the memory version of this task, the problem is √ exactly the hidden matching problem: it has an O(log N )-qubit one-way protocol and requires Ω( N ) classical one-way bits at bounded error [19]. Kerenidis and Raz study the related Boolean Hidden Matching partial function [20]; the relational result used here is the Bar-Yossef–Jayram–Kerenidis problem. This avoids the random-access-code obstruction because the query does not ask for a pre-specified stored bit; it lets the solver choose any edge from a large matching and report the corresponding relation. Chart interpretation. This interpretation uses the sheaf-theoretic framework for contextuality and its database reading [21, 22]. The relevant “global” notion here is the local-to-global one: local tables or contexts are easy to satisfy, while the issue is whether they can be glued into a single global section. We do not impose the physical “genuine global” conditions of multipartite KS scenarios. For a fixed matching M , the response condition is local: output one edge of M and the corresponding parity. A classical boundary state s, however, induces a global response chart gs : M 7−→ (i, j, b) over all possible matchings. A solver using B + M classical bits can select at most 2B+M such charts after reading the history. The hidden-matching lower bound says that, at bounded error, no small family of classical global charts can cover the required history–query relation. This is not a bare KS contradiction. If the full string x is stored, then the assignment bij = xi ⊕ xj is a perfectly good global parity chart for all pairs. The obstruction is resource-sensitive: classical simulation must spend many bits to select an adequate chart, while the quantum protocol keeps a compact phase state from which a query context extracts one valid local relation by interference. In this sense, hidden matching is a classical-looking local-to-global task whose coordination advantage can be read in a resource-sensitive global-chart language. The local-to-global language is not new; the added point is to charge the number of selectable charts to the boundary resources of a state-tracking generator. Definition 9 (Matched-entity consistency QA). Let N be even. A passage hx describes N named entities with binary labels x ∈ {0, 1}N , using a fixed unambiguous grammar. A query cM presents a perfect matching M on the entity set [N ]. A valid answer is any triple (i, j, b) such that (i, j) ∈ M and b = x i ⊕ xj . Here b = 0 means that the two selected entities have the same label, and b = 1 means that they have different labels. Corollary 2 (Matched-entity QA separation). Consider the one-way state-tracking protocol in which x is drawn uniformly from {0, 1}N , the passage processor sees hx , a boundary state is retained, and only then a uniformly random perfect matching M is revealed to the query responder. The query responder must output a valid triple for (x, M ) with probability at least 2/3. There is an exact quantum boundary-state protocol using ⌈log2 N ⌉ qubits. Any bounded-error classical protocol in the same one-way boundary model requires √ B + M = Ω( N ) 12

bits. Proof. For the quantum upper bound, after reading the passage prepare N

1 X |ψx ⟩ = √ (−1)xi |i⟩, N i=1 which uses ⌈log2 N ⌉ qubits. Given a matching M , measure first in the orthogonal decomposition span{|i⟩, |j⟩},

(i, j) ∈ M,

which selects an edge (i, j) ∈ M . Conditional on this edge, the state is proportional to (−1)xi |i⟩ + (−1)xj |j⟩. Now measure in the basis

|i⟩ ± |j⟩ √ 2

inside that two-dimensional subspace. The sign is + iff xi ⊕ xj = 0 and − iff xi ⊕ xj = 1, so the responder outputs (i, j, xi ⊕ xj ) with certainty. For the classical lower bound, suppose a classical state-tracking solver uses m = B + M boundary bits and succeeds with probability at least 2/3. This solver gives a one-way randomized communication protocol for hidden matching: Alice, given x, forms the passage hx , runs the passage processor, and sends the resulting m-bit boundary state to Bob; Bob, given M , runs the query responder and outputs its triple. The success probability is the same as that of the QA √ solver. The one-way communication lower bound for hidden matching therefore implies m = Ω( N ) [19]. Why RNNs and state-space models do not trivialize the question. They do trivialize one weak claim: it is not enough to show that a fixed-depth feed-forward transformer loses track of a latent variable. A recurrent model can store the variable. But recurrence changes the resource point from small M to larger M . The nontrivial question is whether, for some process family Pn , every classical recurrent repair requires Ω(f (n)) bits while a quantum latent state uses O(g(n)) qubits with g(n) ≪ f (n).

10

Online Quantum-AI Specialization and Coordination Width

The one-way synopsis theorem places one boundary between a completed passage and a later query. State tracking in the sense of an update rule st = f (st−1 , xt ) instead places a boundary after every update. This section gives the corresponding online notion and shows how ordinary streaming-space lower bounds become architecture-independent coordination lower bounds. It is the one-pass specialization of Theorem 2. Definition 10 (Peak online coordination width). Consider a solver that consumes update blocks x1 , . . . , xT in order. Let Zt contain all stream-dependent information available after xt has been consumed and before xt+1 arrives. This includes retained activations, recurrent states, accessible cache entries, generated scratchpad symbols, and records written to an external tool or store. If Zt has at most 2wt operationally distinguishable classical values, define WΣ = max wt 0≤t≤T

to be the solver’s peak online coordination width across the family of cuts Σ = (Σ0 , . . . , ΣT ). 13

Under the bit accounting used above, WΣ ≤ max(Bt + Mt ) t

when every accessible explicit record and internal state is included in Bt + Mt . Conversely, representing Zt by an index costs at most wt bits. Thus WΣ is the sequential, peak-space projection of the coordination region. A neural state with r real coordinates at p-bit operational precision contributes at most rp bits; allowing an exact real number to encode an unbounded stream would leave the finite-space model and is not a finite-information classical baseline. Definition 11 (Semantics-preserving online compiler). Let Πn be a streaming relation problem with update alphabet Un and output relation RΠn ⊆ Un∗ × Yn . A semantics-preserving online compiler consists of a prefix-decodable encoding Encn (u) of each update as one text or multimodal block and an answer decoder Decn such that
(u1:T , y) ∈ RΠn ⇐⇒ Encn (u1 ), . . . , Encn (uT ), Dec−1 n (y) is accepted. The compiler has overhead an if parsing the current block and rendering the final answer use at most an bits of workspace and retain no additional stream-dependent information between update boundaries. The no-retained-information clause prevents the linguistic wrapper itself from hiding a large database. It does not require constant-length text: entity identifiers may use O(log n) bits, provided only the current record is being parsed. Corollary 3 (Online semantic lift). Let Scl (n, ϵ) be a lower bound on the space of every randomized one-pass classical streaming algorithm for Πn with error at most ϵ. If an online compiled AI solver has error at most ϵ, compiler overhead an , and peak classical coordination width WΣ , then WΣ ≥ Scl (n, ϵ) − an − O(log T ). If Πn has a one-pass quantum streaming algorithm using Sq qubits and Cq classical bits, then the compiled task has a quantum recurrent solver using Sq qubits

and

Cq + an + O(log T ) classical bits.

Proof. Use Theorem 2 with the one-pass access model and the exact eventwise compiler above. Substituting CclA,ϵ = Scl (n, ϵ) gives the classical inequality, while the source profile (Sq , Cq ) gives the displayed quantum and classical workspace bounds. Remark 4 (Architecture independence). The classical implication uses only the number of distinguishable states carried across update cuts. The update map may be nonlinear, randomized, and computationally unbounded. It therefore applies equally to finite-precision RNNs, nonlinear SSMs, recurrent transformers, KV-cache systems, scratchpads, and tool-using agents, provided all persistent information is counted in WΣ . Extra local depth cannot reconstruct distinctions that were not retained after the stream passed. Remark 5 (Fixed parameters versus instance-dependent state). The parameters of a pretrained model are part of the fixed algorithm description and are not charged as online memory. Write a recurrent implementation schematically as zt+1 = Fθ (zt , xt ),

p(ot | ct , zt ) = Gθ (ct , zt ). 14

The streaming lower bound already permits Fθ and Gθ to be arbitrarily complicated. Nevertheless, if two realized histories induce the same future-accessible state zt , fixed parameters cannot make their response distributions differ under the same future query. Model weights may store the update rule or a vast read-only lookup table, but the instance-dependent index selecting the realized history must still cross the boundary. Test-time weight updates, adapters, fast weights, or model selection that depend on the stream are therefore part of Zt and are charged to WΣ . Remark 6 (The full-context loophole). If the complete raw transcript remains freely available for random access, the solver is no longer one-pass and Corollary 3 does not apply. One must either charge the stored transcript as external memory and its retrieval as boundary traffic, or analyze a multi-pass model. This is precisely the distinction between explicit dynamic state and the transformer workaround of re-examining its whole context. The access regime, not the linguistic surface, is therefore part of the theorem statement. An L-token context over a vocabulary of size V can itself carry up to L log2 V raw token-index bits, and its accessible KV cache is also stream-dependent state. A sufficiently large context can therefore satisfy the lower bounds in this paper; it is a classical repair with a potentially large WΣ , not a violation of the theorem.

10.1

Technical graph instance: dynamic relation summaries

The first calibration is a direct technical instance of the lift. It has an ordinary graph and database interpretation. There are n named entities. Each update block states one directed relation, for example, “entity u places a one-way dependency on entity v.” Once a block has been processed, it is not supplied again. At the end the solver must estimate the maximum number of reported relations that can run from one side of a bipartition to the other. Formally, removing the fixed grammar leaves the insertion-only Max-DiCut edge stream. Corollary 4 (Dynamic relation-summary separation). For the terminal approximation ratio 0.4844 and failure probability δ, the dynamic relation-summary task has a quantum recurrent solver using   1 5 O log n log δ qubits of online workspace, plus logarithmic compiler workspace. Every finite-information classical recurrent solver in the same one-pass access regime satisfies √ WΣ = Ω( n). Equivalently, its family of effective recurrent coordination states has size √

Kclonline ≥ 2Ω( n) . Proof. Kallaugher, Parekh, and Voronova give a one-pass quantum streaming algorithm with the displayed space bound and approximation ratio. The classical streaming lower bound they √ invoke states that every ratio strictly larger than 4/9 requires Ω( n) bits [23]. The fixed relation grammar is prefix-decodable with O(log n) workspace. Corollary 3 transfers both bounds, and 0.4844 > 4/9. Exponentiating the width lower bound gives the state-count form. This task realizes DeepMind’s schematic update st = f (st−1 , xt ): each sentence modifies a compact synopsis of a growing relational world. The conclusion is stronger than a failure theorem for a feed-forward transformer. Giving the model recurrence repairs the topological √ depth problem, but every classical repair still needs Ω( n) peak retained bits at the target approximation ratio.

15

10.2

Natural AI task: continual requirements auditing

Consider an AI assistant supporting a long-running policy, planning, or engineering process. The participants introduce requirements one at a time; the assistant must update its synopsis without retaining or rereading the whole transcript. At the end, the user asks for the bestachievable compliance score: how many of the accumulated requirements can any coherent plan satisfy? The binary decisions may represent whether to activate a service, approve a proposal, allocate a team, or adopt a design option. Typical utterances are: “If weekend hours are not extended, remote triage must be enabled,” “Either the mobile unit stays onsite or weekend hours are extended,” and “Remote triage and moving the mobile unit offsite may not occur together.” After semantic parsing, these become disjunctions of signed binary decisions. The user-facing problem is requirements auditing; its formal semantic core is Max-kSAT. Definition 12 (Continual requirements-audit task). Fix k ≥ 2. A task instance contains n named binary decisions and a time-ordered dialogue r1 , . . . , rT . Each requirement utterance rt has a certified semantic parse as a clause Ct containing at most k literals. Once rt has been processed, it is unavailable except through the solver’s retained state. On the terminal query, the solver outputs a number Z estimating OPT(C1:T ) = max {t : Ct (a) = 1} , a∈{0,1}n

or equivalently the normalized compliance score OPT(C1:T )/T . The theorem-certified version uses a controlled natural-language grammar, so each requirement can be parsed independently with O(log n) workspace. A benchmark may additionally contain ordinary paraphrases, domain vocabulary, and coreference, but then semantic-parser error is a separate empirical layer. The memory theorem already applies to the exactly parseable subset; a quantum upper bound for the richer surface form additionally assumes a shared online semantic front end. Corollary 5 (Continual requirements-audit separation). For every fixed k ≥ 2, the controlledlanguage continual requirements-audit task admits a one-pass quantum recurrent solver which, with probability at least 1 − δ, outputs Z satisfying OPT(C1:T ) ≥ Z ≥ 0.7172 OPT(C1:T ) using   1 5 O log n log δ qubits of online workspace. It also uses polylogarithmic classical working bits, including O(log n) exact counters. Every finite-information classical recurrent solver attaining that ratio in the same one-pass regime has √ WΣ = Ω( n). Proof. Wang and Yang give the displayed one-pass quantum streaming algorithm for MaxkSAT; its quantum sketches also use polylogarithmic classical control and working bits, and its preprocessing retains logarithmic classical streaming lower bound rules out √ exact counters. The √ every ratio strictly larger than 2/2 ≈ 0.7071 in o( n) space [24]. The controlled requirement grammar is a semantics-preserving online compiler with logarithmic workspace, so Corollary 3 preserves both bounds. This is a natural AI state-tracking problem in the operational sense used by Mozer, Siddiqui, and Liu: the accumulated requirement set is an evolving world state, and its task-sufficient 16

synopsis must be updated as st = f (st−1 , rt ). The assistant is not asked to recall arbitrary past sentences or output a quantum object. It produces one classical planning diagnostic. The result is stronger than the observation that a transformer may lose track of a satisfying assignment: the lower bound ranges over all bounded-space classical update rules, including recurrent repairs. The task also has a clear limitation. It estimates the optimum compliance value; it does not output the optimizing plan. The cited quantum streaming algorithm does not establish a compact quantum advantage for plan construction, and the present paper does not claim one. What is imported and what is new. The Max-DiCut and Max-kSAT quantum algorithms, approximation constants, and classical streaming lower bounds are imported results. Rewording their records as sentences does not create a new quantum algorithm. The new claim developed here is the general transfer principle and the associated AI task model: after fixing an online semantic boundary, a streaming lower bound becomes a lower bound on the peak coordination width of every finite-information recurrent AI implementation, including the standard architectural repairs to transformer state tracking. Continual requirements auditing supplies a practical planning semantics for that theorem. A purported small classical solver must be using uncharged transcript access, unbounded numerical precision, a weaker output guarantee, or a different access model. Finite-size interpretation. These theorems establish asymptotic coordination separations, √ not a practical memory saving at ordinary LLM scales. The Ω( n) bounds hide constants: √ at n = 106 , the scaling term n is only 103 , whereas a 128k-token context over a 105 -word vocabulary can carry about 2.1 × 106 raw token-index bits before counting the physical KV cache. Likewise, the explicit stabilizer expression below is about 5.0×103 bits at n = 100 qubits. √ Moreover, an O(log5 n) quantum upper bound need not beat n at moderate n, especially after constants, fault-tolerance, and interface costs are included. No finite-size crossover or practical quantum-memory advantage is claimed here.

11

Contextual Quantum-AI Application

The previous sections explain what kind of benchmark is needed. Ordinary LSP tasks hide a classical variable and ask later questions about it. Such tasks are useful probes of state tracking, but a classical recurrent model can repair them by storing a sufficient state. To obtain a candidate quantum separation, the hidden state should instead be queried through incompatible contexts. Definition 13 (Contextual LSP benchmark). For each size parameter n, a contextual latentstate-persistence benchmark consists of: Hn Cn {ρh : h ∈ Hn } {Moc : o ∈ Oc }c∈Cn {Ec,o }c,o

: : : : :

allowed histories, allowed query contexts, latent states prepared by histories, query-dependent output measurements, state-update instruments.

At test time the benchmark presents a history ht and a query context ct . The target conditional distribution is Pn (ot | ht , ct ) = Tr(Moctt ρht ), and after observing ot the latent state updates as ρht+1 = Ect ,ot (ρht ).

17

A model is evaluated by the average total-variation distance, log loss, or success probability of its conditional predictions over an adaptive sequence of histories and queries. The intended boundary is the time cut after ht has been processed but before ct is revealed. If the complete history is re-supplied together with the query, then a classical model may recompute the latent state from the raw transcript; in the present accounting that repair is charged to local depth D, not treated as free state tracking. This definition contains ordinary LSP as the jointly classical special case. If all states and measurements are jointly diagonal in a common basis, then there is a classical sufficient variable zt and Proposition 2 applies. The task becomes contextual in the operational sense used here only when the same history can later be queried in contexts that do not admit a small common response chart. From LSP to contextual LSP. The operational modification is small. In an ordinary hidden-state benchmark, the history prepares a latent variable and later questions ask for facts about that variable. In a contextual benchmark, the history prepares a latent object and later questions choose one of several incompatible tests of that object. A language wrapper could describe the history as a lab notebook, simulation trace, symbolic circuit, or world-state update; the mathematical core is that ct is not just a request for a stored fact, but a measurement context. The resulting classical repair options are still allowed. A classical model may store a chart in recurrent memory, write intermediate chart data into a scratchpad, or recompute a chart after seeing the query. The point is that these repairs now have visible costs: stored chart data 7→ M,

written chart data 7→ B,

reconstructed chart data 7→ D.

Definition 14 (Stabilizer contextual LSP). The stabilizer contextual-LSP family Pnstab , the benchmark version of the quantum-memory seed imported from Ref. [3], is obtained by taking Hn to be histories of Clifford gates and previous Pauli measurement outcomes on n qubits. Each history prepares an n-qubit stabilizer state ρh . A query context c ∈ Cn is a commuting family of Pauli observables, the output o is the corresponding string of measurement outcomes, and the update map is the usual stabilizer measurement update. Definition 15 (Semantic stabilizer dialogue). A semantic stabilizer dialogue is a naturallanguage or symbolic-language presentation of Pnstab . The transcript describes Clifford updates and previous Pauli measurement outcomes using an unambiguous finite grammar; the next prompt describes a commuting Pauli context; and the required answer is the corresponding outcome distribution or a sample from it. The semantic target process is still Pnstab ; the text wrapper only supplies a state-tracking interface of the kind used in transformer state-tracking benchmarks. Definition 16 (Adaptive-complete recurrent simulation). A classical recurrent implementation of a contextual-LSP family is adaptive-complete if, for every finite adaptive policy that chooses the next query context as a function of the previous history and outcomes, the implementation reproduces the joint distribution of the full transcript. The boundary state at time t consists of the retained recurrent state together with any explicit transcript crossing the chosen boundary Σt . Thus an implementation using resources (B, M ) has at most 2B+M effective boundary states at each cut. Relation to the genuine-global construction. Reference [3] contains two logically distinct steps. Its finite-causal-witness lemma is already a single-system statement about the n-qubit stabilizer seed: it constructs the finite adaptive interface Wn and proves the causal-state lower bound used below. A subsequent, optional flag lift embeds that seed into a genuinely global 18

multipartite model and transfers the same cost by conditioning on the flag. The present LSP benchmark imports only the first step. It therefore needs no k = 1 or single-party reduction from the genuinely global theorem, and its quantum upper bound remains the n-qubit seed realization. Applying the separate flag lift would instead produce a genuinely global restriction with a small additional flag-memory overhead, but that extra physical structure is not used in the AI state-tracking claim. Lemma 1 (Imported finite causal stabilizer witness). For every n ≥ 2, there is a finite adaptive interface Wn ⊂ Pnstab such that every exact finite-state classical causal online realization of Wn has at least Q 2n nj=1 (2j + 1) Kn ≥ 5 · 3n−2 boundary states. Consequently, every exact adaptive-complete classical recurrent implementation of Pnstab satisfies B + M ≥ log2 Kn . Proof. Karanjai–Wallman–Bartlett show that every set of more than mn = 5 · 3n−2 pure nqubit stabilizer states admits a stabilizer partitioning measurement [10]. For every subset of mn + 1 preparations, include one such measurement and, after each relevant outcome, one allowed single-shot test distinguishing the resulting orthogonal pair. The stabilizer preparation and measurement sets are finite for fixed n, so their union defines a finite interface Wn . If one causal boundary state occurred with positive probability after all preparations in one of these subsets, its common response kernel would assign positive probability to some partitioning outcome and successor state. Two preparations would then reach orthogonal postmeasurement records through that same successor state, while the subsequent distinguishing test requires different certain outcomes, a contradiction.QThus one causal state can occur in the support of at most mn pure preparations. There are 2n nj=1 (2j + 1) pure stabilizer states, giving the stated count. This finite-witness upgrade from the KWB overlap theorem to arbitrary finite-state causal realizations is exactly the single-system “finite causal witness from the stabilizer overlap bound” lemma of Ref. [3], restated here to make the reduction self-contained. It precedes, and does not rely on, that reference’s genuinely global flag-lift theorem. An exact adaptive-complete implementation of the full process remains exact when restricted to Wn . Its complete future-accessible transcript and retained state have at most 2B+M values, so 2B+M ≥ Kn . Corollary 6 (Imported stabilizer latent-state separation). The family Pnstab is exactly generated by a quantum recurrent model using n qubits of latent memory. Any exact adaptive-complete finite-state classical causal recurrent implementation, with all future-accessible boundary information counted, satisfies B + M = Ω(n2 ). More explicitly, for n ≥ 2, B + M ≥ log2

2n

Qn

j j=1 (2 + 1) 5 · 3n−2

!

1 = n2 + 2



 3 − log2 3 n + O(1) = Ω(n2 ). 2

Proof. The quantum implementation stores the physical n-qubit stabilizer state and applies the requested Clifford or Pauli-measurement update. Restricting an exact adaptive-complete classical implementation to the finite interface Wn preserves its boundary-state set. Lemma 1 therefore gives the displayed ratio and its logarithm. Expanding log2 (2j + 1) = j + log2 (1 + 2−j ) gives the quadratic asymptotic. The factor in this count is 2j + 1, exponential in j. As a low-dimensional check, the formula gives 23 (3)(5)(9) = 1080 pure stabilizer states at n = 3; this factor is what produces the quadratic logarithmic growth. 19

Corollary 7 (Contextual quantum-AI state-tracking separation). Relative to the boundary after the transcript has been semantically processed and before the next query context is revealed, the text-wrapped stabilizer dialogue is generated by a quantum recurrent model with n qubits of latent memory. Any exact adaptive-complete finite-state classical causal recurrent solver, with all future-accessible semantic boundary information counted, satisfies B + M = Ω(n2 ). Proof. The controlled grammar is an exact boundary-preserving semantic compiler: removing the linguistic surface leaves the stabilizer contextual-LSP process Pnstab , each current block is parsed with O(log n) workspace, and no parser record survives the semantic boundary. A quantum solver applies each decoded update to the physical n-qubit latent state. Theorem 2, applied to the imported finite-state lower bound in Lemma 1, gives the stated Ω(n2 ) classical bound. Remark 7. This corollary is the sense in which an NLP-style task can carry a provable quantum coordination advantage. The advantage belongs to the noncommuting state-tracking problem preserved by the text, not to ordinary natural language understanding by itself. If the full raw transcript is re-supplied and a classical model recomputes a stabilizer tableau after each prompt, the stored or retransmitted transcript is charged to B + M and its processing to D; neither resource is free. Remark 8. This benchmark is intentionally quantum-native. Rephrasing it as natural language does not make the advantage a property of ordinary language modeling; it only gives a userfacing wrapper around a noncommuting state-tracking task. Its value is that it isolates the exact technical target: prove the reduction from an adaptive state-tracking interface to causal boundary-state complexity. The finite witness above achieves that reduction exactly; robust approximate and natural-task versions remain open. Scope of the transferred bound. The displayed Ω(n2 ) separation applies to every exact finite-state classical causal online realization of the adaptive-complete interface; it is not restricted to a preselected chart or neural architecture. The finite witness is what upgrades the KWB overlap count to this general causal class. The theorem still does not cover constant-error approximation, a batch algorithm with free random access to the full transcript, or uncounted infinite-precision state. Those are different approximation or access models. Why adaptive completeness matters. A one-step benchmark distribution is weaker than a process simulator. A model might predict the next answer well on a fixed distribution of histories without carrying enough state to answer all future compatible queries. The stabilizer lower-bound route therefore needs an adaptive benchmark: after any history that the model itself has helped generate, an evaluator may choose a new commuting Pauli context and continue. This is the operational content of state tracking, and it is what turns a conditional prediction benchmark into a candidate memory lower-bound problem. Evaluation protocol. An evaluator can implement adaptive completeness without inspecting the model’s internal state. At the start of each trial it resets the model, supplies an allowed preparation-and-update history, and then selects each next commuting Pauli context as a function of the full interaction transcript. It records the model’s response, applies the corresponding target-process update, and continues for a prescribed horizon. Repeated trials estimate the joint distribution of complete adaptive trajectories, which is compared with the target process in total variation or log loss. The policy family must include context choices that distinguish histories

20

merged by a candidate simulator; a fixed i.i.d. test set does not provide this guarantee. Constructing an efficient worst-case policy, or a finite certificate that is complete for a given model class, remains an open algorithmic problem. Classical-baseline audit. The logical strength of each result is summarized below. Here general always means general within the displayed one-way, one-pass, or causal access model, not a batch algorithm with free access to the complete input. Result State-count and separation criteria Semantic coordination transfer Synopsis and matchedentity QA Online semantic lift and its two tasks Strong k-contextuality of Teo et al. Imported stabilizer witness Compiled contextual AI dialogue

12

Classical baseline The explicitly named class C

Status Conditional on C

The named source access model, with all compiler state charged Arbitrary randomized one-way protocol

General transfer

Arbitrary randomized one-pass finiteinformation update rule Finite-state HMM or finite-precision autoregressive realization Arbitrary exact finite-state causal online realization Arbitrary exact finite-state causal online realization

General one-way General one-pass Interface-limited Ref. [3], exact General transfer

causal

Discussion: Calibrations and Extensions

The task families above play three different roles and should not be read as coequal headline contributions. 1. Classical-looking calibrations. Matched-entity QA and continual requirements auditing instantiate established one-way or streaming separations inside ordinary database and planning semantics. They validate the boundary accounting and the semantic lifts, but their underlying quantum algorithms and lower bounds are imported. In particular, the requirements-audit advantage comes from streaming Max-kSAT and is not claimed to arise from contextuality. 2. Quantum-native compiler test. Stabilizer measurement tracking imports the clean finite witness of Ref. [3]. The new role it plays here is to test whether a semantic statetracking interface preserves an adaptive causal-state separation. Its limitations are explicit: adaptive completeness is required, the source theorem is exact, and the semantics remain quantum-native unless a certified wrapper is used. 3. Extensions toward natural processes. Quantum predictive-memory models provide classical stochastic processes with compact quantum representations [6, 7]. Contextual interactive dialogues, scientific time series, and embodied-agent histories are further targets, but difficult state tracking alone does not imply noncommutativity. A convincing extension must identify a concrete query family with a large classical causal-state lower bound and a compact quantum realization.

13

Open Problems

1. Foundational robustness. Identify equivalence classes of computational boundaries under which the B, M, D region is stable, and separate representation or simulation cost from the cost of learning a generator. Without these distinctions, a lower bound may partly 21

reflect bookkeeping or training assumptions rather than an intrinsic coordination obstruction. 2. Robust and efficient witnesses. Extend the exact stabilizer theorem to ϵ-approximate causal simulation and replace the potentially large finite witness by efficient adaptive evaluator policies and statistical certificates. Semantic wrappers must preserve the same complete causal interface, including gates, measurements, randomness, and updates. 3. Finite and physical advantage. Determine constants, crossover scales, matching classical upper bounds, and actual context or KV-cache costs. A physical comparison must also include coherence time, error correction, refresh, and classical–quantum input/output overhead over the full stream. 4. Natural tasks and outputs. Find noncommuting latent-state processes closer to practical generation while retaining provable causal-state lower bounds. This includes classicallooking interactive benchmarks, natural-language variants with controlled parser error, and strengthening the requirements-audit result from value estimation to construction of an approximately optimal plan.

Acknowledgements The author acknowledges the use of AI-assisted tools during the preparation of this draft for literature exploration, mathematical checking, language polishing, and organization. The author is solely responsible for all claims, interpretations, and conclusions.

References [1] J.-t. Huang, K. Sun, W. Wang, and M. Dredze. On the failure of latent state persistence in large language models. arXiv:2505.10571, 2025. [2] M. C. Mozer, S. A. Siddiqui, and R. Liu. The topological trouble with transformers. arXiv:2604.17121, 2026. [3] M. Yang. Genuine global Kochen–Specker contextuality as classical coordination cost. arXiv:2606.23577, 2026. [4] X. Gao, E. R. Anschuetz, S.-T. Wang, J. I. Cirac, and M. D. Lukin. Enhancing generative models via quantum correlations. Physical Review X 12, 021037 (2022). [5] K. Gili, M. Mauri, and A. Perdomo-Ortiz. Generalization metrics for practical quantum advantage in generative models. Physical Review Applied 21, 044032 (2024). doi:10.1103/PhysRevApplied.21.044032. [6] M. Gu, K. Wiesner, E. Rieper, and V. Vedral. Quantum mechanics can reduce the complexity of classical models. Nature Communications 3, 762 (2012). [7] A. J. P. Garner, Q. Liu, J. Thompson, V. Vedral, and M. Gu. Provably unbounded memory advantage in stochastic simulation using quantum mechanics. New Journal of Physics 19, 103009 (2017). [8] M. Kleinmann, O. Gühne, J. R. Portillo, J.-Å. Larsson, and A. Cabello. Memory cost of quantum contextuality. New Journal of Physics 13, 113011 (2011).

22

[9] G. Fagundes and M. Kleinmann. Memory cost for simulating all quantum correlations of the Peres–Mermin scenario. Journal of Physics A: Mathematical and Theoretical 50, 325302 (2017). [10] A. Karanjai, J. J. Wallman, and S. D. Bartlett. Contextuality bounds the efficiency of classical simulation of quantum processes. arXiv:1802.07744. [11] S. Prakash. Quantum memory advantage from contextuality. arXiv:2607.00507, 2026. [12] B. Z. Li, Z. C. Guo, and J. Andreas. (How) do language models track state? In Proceedings of the 42nd International Conference on Machine Learning, PMLR 267, 34429–34452 (2025). [13] W. Merrill, J. Petty, and A. Sabharwal. The illusion of state in state-space models. In Proceedings of the 41st International Conference on Machine Learning, PMLR 235, 35492– 35506 (2024). [14] B. Peng, S. Narayanan, and C. Papadimitriou. On limitations of the transformer architecture. arXiv:2402.08164, 2024. [15] M. H. Teo, W. Yang, J. Sud, T. Tomesh, F. T. Chong, and E. R. Anschuetz. kContextuality as a heuristic for memory separations in learning. In 2025 IEEE International Conference on Quantum Computing and Engineering (QCE), 2399 (2025). doi:10.1109/QCE65121.2025.00260. [16] A. Vaswani et al. Attention is all you need. In Advances in Neural Information Processing Systems, 2017. [17] A. Nayak. Optimal lower bounds for quantum automata and random access codes. In Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 369–376 (1999). [18] H. Fawzi, J. Gouveia, P. A. Parrilo, R. Z. Robinson, and R. R. Thomas. Positive semidefinite rank. Mathematical Programming 153, 133–177 (2015). [19] Z. Bar-Yossef, T. S. Jayram, and I. Kerenidis. Exponential separation of quantum and classical one-way communication complexity. In Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 128–137 (2004). doi:10.1145/1007352.1007379. [20] I. Kerenidis and R. Raz. The one-way communication complexity of the Boolean hidden matching problem. arXiv:quant-ph/0607173. [21] S. Abramsky and A. Brandenburger. The sheaf-theoretic structure of non-locality and contextuality. New Journal of Physics 13, 113036 (2011). [22] S. Abramsky. Relational databases and Bell’s theorem. arXiv:1208.6416. [23] J. Kallaugher, O. Parekh, and N. Voronova. Exponential quantum space advantage for approximating maximum directed cut in the streaming model. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 1805–1815 (2024). doi:10.1145/3618260.3649709. [24] H. Wang and G. Yang. Exponential quantum space advantage for approximating MaxkSAT in the streaming setting. arXiv:2606.05366, 2026.

23

Related documents

• Delivery, Not Storage: Cue-Anchored Working Memory as a Harness Property for Coding Agents#394480
• Decision Making : A Quantum Mechanical Analysis Based On Time Evolution of Quantum Wave Function and of Quantum Probabilities during Perception and Cognition of Human Subjects#711746
• Quantum mind#1179911
• Circuit Hypernetworks for Quantum-Augmented Diffusion Language Models#1051064
• Staged Hybridisation for Visual Quantum Reinforcement Learning via Knowledge Distillation#321831