1 Introduction↩︎

Computation and communication are usually introduced as distinct notions. Computation is the processing of information inside a machine; communication is the transmission of information between machines. This distinction is useful in engineering, but it is not fundamental from the point of view of information flow.

Consider a Turing machine transition \[\delta(q,s)=(q',s',\mathrm{move}).\] The usual reading is that the machine has performed one elementary computational step. But the same step may be read as a local communication process: the tape cell sends the current symbol \(s\) to the finite controller; the controller sends back a new symbol \(s'\); and the controller sends a movement command to the head. Thus a Turing step is a local exchange of information between a controller and a storage medium.

Under this reading, \[\text{computation} = \text{internal information transfer plus state update},\] while \[\text{communication} = \text{information transfer across a chosen boundary}.\] Memory is the local snapshot retained after information transfer. Time, space, and communication complexity are then not unrelated quantities. They are projections of a more general question: how much coordination is required to maintain and update a global information state?

Quantum foundations already provide two mature instances of this question. Bell nonlocality shows that some multipartite correlations cannot be simulated by zero-communication local hidden-variable models. Classical simulation must then pay communication. Kochen–Specker contextuality shows that some measurement statistics cannot be simulated by a single noncontextual hidden state. Classical simulation must then pay memory, hidden state, or state update complexity.

This note asks whether genuine global Kochen–Specker contextuality gives the next member of the same pattern. In such a multipartite model, each local part may be classically explainable, and each observed block may even admit an appropriate generalized Bell-local explanation, while the collection of all blocks cannot be glued into one global noncontextual hidden-variable model. We propose that this residual global obstruction should lower-bound a joint classical coordination cost involving communication, memory, and local computation.

1.0.0.1 Informal thesis.

\[\begin{array}{rcl} \text{Bell nonlocality} &\Longrightarrow& \text{communication cost},\\[2mm] \text{KS contextuality} &\Longrightarrow& \text{memory/space cost},\\[2mm] \text{genuine global KS contextuality} &\Longrightarrow& \text{joint classical coordination cost}. \end{array}\]

2 Turing Machines as Boundary Communication↩︎

We now make the opening interpretation slightly more formal. Let \[\mathcal{M}=(Q,\Gamma,\delta)\] be a deterministic single-tape Turing machine, with finite control states \(Q\), tape alphabet \(\Gamma\), and transition map \[\delta(q,s)=(q',s',d), \qquad d\in\{-1,0,+1\}.\] At time \(t\), write the configuration as \[c_t=(q_t,h_t,\tau_t),\] where \(q_t\in Q\) is the control state, \(h_t\in\mathbb{Z}\) is the head position, and \(\tau_t:\mathbb{Z}\to\Gamma\) is the tape contents. Let \[s_t=\tau_t(h_t)\] be the symbol at the active tape cell. The global update is local: \[(q_t,h_t,\tau_t(h_t)) \longmapsto (q_{t+1},h_{t+1},\tau_{t+1}(h_t)),\] while every inactive cell \(i\neq h_t\) keeps \(\tau_{t+1}(i)=\tau_t(i)\).

This local update can be represented as a two-component exchange across the active boundary between the finite controller and the active tape cell: \[\begin{array}{rcl} \text{cell}\to\text{controller} &:& s_t,\\ \text{controller}\to\text{cell} &:& s'_t,\\ \text{controller}\to\text{head token} &:& d. \end{array}\] Thus one Turing step has an internal boundary transcript of length at most \[b_{\mathcal{M}} = 2\lceil\log_2|\Gamma|\rceil+\lceil\log_2 3\rceil\] bits under this explicit read-write-move convention. Other conventions shift this constant, but not the point: a sequential computation is a repeated local communication process plus state update.

The relevance for this paper is not the constant \(b_{\mathcal{M}}\). The point is that the same process can be cut in different ways. If the boundary is drawn between two laboratories, the transcript contributes to communication cost. If the boundary is drawn between a controller and its retained state, the same information appears as memory. If the transcript is generated rather than stored, it appears as local computation depth.

This gives a technical version of the informal \((B,M,D)\) picture. For a compiled task \(T\), let \(\mathcal{G}_D\) be the set of global assignments that can be generated by the chosen local machine model within depth \(D\). Define the depth-restricted covering number \[\chi_G^D(T) = \min\Bigl\{ K:\exists g_1,\ldots,g_K\in\mathcal{G}_D \text{ covering all contexts of }T \Bigr\}.\] Then any cover-admissible classical simulator with communication \(B\), memory \(M\), and local depth \(D\) must satisfy \[2^{B+M}\geq \chi_G^D(T),\] or equivalently \[B+M\geq \log_2\chi_G^D(T).\] If one wants \(D\) explicitly as a lower-bound variable, define the inverse trade-off function \[D_T(K)=\min\{D:\chi_G^D(T)\leq K\}.\] Then every such simulator also satisfies \[D\geq D_T(2^{B+M}).\] In this form, the Turing-machine reading is no longer only motivational: it specifies how local computation depth trades against communication and memory inside the same covering-number obstruction.

Bridge to global contextuality↩︎

The connection to global contextuality is the following. In a measurement scenario, let \(V\) be the set of all measurement labels and let \(\mathcal{C}\) be the family of compatible contexts. A deterministic global noncontextual chart is a function \[g\in \prod_{v\in V} A_v,\] assigning one outcome to every measurement, independently of the context in which that measurement later appears. A GNCHV model is a random choice of such charts before the measurement context is used. Thus, after all boundary transcripts, memory states, and bounded-depth local computations have been fixed, a classical noncontextual simulator contributes exactly one chart \[g_{t,s}\in\mathcal{G}_D.\] The pair \((t,s)\) is the classical coordination data selecting this chart.

Local noncontextuality and \(\mathsf{GLHV}\) say that the small pieces are classically explainable: each local subsystem, and even each observed multipartite block, admits an appropriate classical description. Global contextuality says that these descriptions cannot be chosen as restrictions of one common global chart. In other words, the obstruction is not local computation inside one block, and not Bell nonlocal communication between the tested parties; it is a failure of global gluing.

For a support or relation version of the empirical model, define the support task \(T_p\) by \[W_C=\operatorname{supp}(p_C) \qquad (C\in\mathcal{C}).\] If one chart \(g\) satisfies \(g|_C\in W_C\) for every context, then the support data admit a zero-cost global explanation. If no such chart exists, then a classical simulator can only succeed by selecting different charts for different contexts. The number of charts available to a simulator with communication \(B\), memory \(M\), and local depth \(D\) is at most \[2^{B+M}\] inside \(\mathcal{G}_D\). Hence support-level global contextuality gives the resource inequality \[2^{B+M}\geq \chi_G^D(T_p).\] For probabilistic, rather than support-level, global contextuality, the same bridge is replaced by an approximate version: distance to the GNCHV polytope, contextual fraction, or fractional covering measures how much context-dependent chart selection is still required.

3 A First Depth-Restricted Covering Calculation↩︎

The previous section defines \(D_T(K)\), but a definition is not yet a calculation. We now give a small support-level gluing task where the \((B,M,D)\) trade-off can be computed exactly. This example is not meant to be a physical global-KS construction; its role is to show how the computation axis enters the same covering machinery.

Let \(n\geq2\). For each vertex \(x\in\{0,1\}^n\) of the \(n\)-dimensional hypercube, introduce one binary variable \(v_x\). For each edge in direction \(i\), written \[C_{x,i}=\{v_x,v_{x\oplus e_i}\} \qquad (x_i=0),\] impose the parity relation \[a\oplus b=1,\] except on the distinguished edge \[C_{0,1}=\{v_{0^n},v_{e_1}\},\] where the relation is instead \[a\oplus b=0.\] Call this compiled task \(Q_n\).

Now restrict the allowed charts. Let \(\mathcal{G}_D\) consist of affine parity charts \[g_{S,c}(x)=c\oplus\bigoplus_{i\in S}x_i, \qquad c\in\{0,1\},\] with \[|S|\leq 2^D.\] This is the natural fan-in-two XOR-tree model: depth \(D\) can combine at most \(2^D\) input coordinates into one parity value.

For a cover-admissible simulator, \(K\leq2^{B+M}\). Therefore, if \(B+M\geq1\), the twisted hypercube gives the explicit trade-off \[D \geq \max\left\{ 0,\left\lceil \log_2 n-(B+M)\right\rceil \right\}.\] With no coordination bit, \(K=1\), perfect support-level simulation is impossible for any depth because the task has no global section. Each extra coordination bit doubles the number of available charts and can reduce the required local parity depth by at most one.

The twisted hypercube is only a combinatorial model of gluing failure. Its purpose is to make the \(D\)-axis computable in a transparent setting. In a genuine global-KS example, such as the Hardy construction studied later, the task \(T_p\) is obtained from the supports of a physical empirical model and the admissible charts are GNCHV assignments. The same depth-restricted covering calculation is then the object one would need to compute.

4 A Cautionary Test: Tseitin Contradictions↩︎

It is tempting to look for stronger examples among classical hard contradictions. Tseitin systems on expander graphs are a natural first candidate: they are mod-2 parity contradictions and have strong proof complexity lower bounds [2], [3]. However, they do not make the global covering number large. This illustrates an important difference between proof complexity and coordination covering.

Let \(G=(V,E)\) be a connected graph with \(|V|\geq2\). A charge function is a map \[c:V\to\{0,1\}.\] Assume it has odd total charge, \[\bigoplus_{v\in V} c(v)=1.\] The Tseitin task \(T_{\rm Ts}(G,c)\) has one binary variable \(x_e\) for each edge \(e\in E\). For each vertex \(v\), the context is the incident edge set \[C_v=\{e\in E:e\ni v\},\] and the winning relation is \[\bigoplus_{e\ni v} x_e=c(v).\]

Thus large proof-complexity lower bounds for Tseitin formulas do not imply large global contextual covering numbers. Proof complexity asks how hard it is to derive a contradiction; \(\chi_G\) asks how many global charts are needed to cover the local constraints. A contradiction can be proof-theoretically hard while being cover-theoretically easy.

The right preliminary screen for large \(\chi_G\) is a fractional covering quantity. Let \(\Delta(\mathcal{G})\) denote distributions over deterministic global assignments, and define \[\gamma_G(T) = \max_{\nu\in\Delta(\mathcal{G})} \min_{C\in\mathcal{C}} \Pr_{g\sim\nu}[g|_C\in W_C].\] This is the largest coverage probability that can be guaranteed uniformly over contexts by randomizing over global charts. It should not be confused with \(\beta_G(T)\): \(\beta_G(T)\) is the best average success of one chart under a chosen context distribution, whereas \(\gamma_G(T)\) asks for a distribution over charts that covers every context with uniformly high probability.

It is also different from the contextual fraction. For a probabilistic model \(p\), the noncontextual fraction can be written as \[\operatorname{NCF}(p) = \max\{\lambda:\; p=\lambda p_{\mathsf{NC}}+(1-\lambda)p' \text{ for some }p_{\mathsf{NC}}\in\mathsf{NC}\},\] and the contextual fraction is \(1-\operatorname{NCF}(p)\). This is a probabilistic distance-to-\(\mathsf{NC}\) quantity. By contrast, \(\chi_G\) and \(\gamma_G\) are support-level or relation-level covering quantities. They are useful for the elementary bit-counting bounds proved here, while contextual-fraction methods would be the natural tool for sharper approximate simulation bounds.

Consequently, any task family with very large \(\chi_G(T_n)\) must have very small uniform fractional coverage \(\gamma_G(T_n)\), not merely a hard refutation in a proof system. This suggests that good candidates should have delocalized violation structure: every chart should miss many contexts, and no distribution over charts should cover all contexts with substantial probability. Expander-code, locally testable code, or quantum-LDPC-style constraint systems are natural places to look, but they require separate analysis.

5 Related Work↩︎

Bell nonlocality and communication complexity have a long connection, starting from the use of entanglement to reduce communication in distributed tasks and from results showing that stronger-than-quantum nonlocal boxes can trivialize communication complexity. See, for example, Buhrman, Cleve, Massar, and de Wolf [4], Brassard et al. [5], and later graph- and inequality-based formulations.

The memory cost of contextuality has been studied from a complementary angle: instead of asking how much information must cross a spatial boundary, one asks how much internal state is needed for a classical machine to reproduce contextual correlations across measurement contexts. See Kleinmann et al. [6], Fagundes and Kleinmann [7], and Karanjai, Wallman, and Bartlett [8].

The mathematical unity of nonlocality and contextuality is expressed by the sheaf-theoretic framework of Abramsky and Brandenburger [9]. Quantitative versions include the contextual fraction [10]. Recent work on generalized Bell scenarios and global Kochen–Specker contextuality suggests a third case: models that are neither locally contextual nor generalized-Bell-nonlocal, but still fail to admit a global noncontextual explanation [1], [11].

To move beyond specially designed games, we also use the standard view of constraint satisfaction problems and relational structures as local-to-global consistency problems. The quantum-monad formulation of Abramsky et al. [12] connects relational structures, homomorphism games, and contextuality-powered quantum advantage. The valuation-algebra view of Abramsky and Caru [13] similarly treats contextuality as a general theory of disagreement among locally consistent information sources; the database reading of local consistency and global joins is developed in Ref. [14]. Measurement-based quantum computation provides a complementary route from general quantum algorithms to local measurement patterns with classical feed-forward [15]–[17]. The computational role of contextuality and magic is studied, for example, in Refs. [8], [18]. The depth axis is also motivated by shallow-circuit separations between quantum and classical models [19].

6 Empirical Models and Relation Tasks↩︎

We use a finite relation-task presentation. Let \(\mathcal{C}\) be a finite set of contexts. Each context \(C\in\mathcal{C}\) has a set of possible outcomes \(O_C\) and a winning set \[W_C \subseteq O_C.\] A strategy for the task produces, for each context \(C\), a probability distribution \(p_C\) on \(O_C\). It wins context \(C\) with probability \[p_C(W_C)=\sum_{a\in W_C} p_C(a).\]

When the contexts arise from compatible measurements, the family \[p=\{p_C\}_{C\in\mathcal{C}}\] is an empirical model. A perfect quantum strategy satisfies \[p_C(W_C)=1 \qquad\text{for all } C\in\mathcal{C}.\]

If one global assignment covers all contexts, the relation task has a deterministic global noncontextual solution. Contextuality appears when no single global assignment covers all contexts.

For probabilistic empirical models, a global noncontextual hidden-variable model, abbreviated \(\mathsf{GNCHV}\), is a probability distribution \(\lambda\) over global assignments such that \[p_C(a) = \sum_{g:\,g|_C=a}\lambda(g) \qquad (C\in\mathcal{C},\;a\in O_C).\] Thus a \(\mathsf{GNCHV}\) model is a context-independent random choice of one global chart. A local subsystem is noncontextual when its restricted empirical model admits the analogous representation on that subsystem.

In a multipartite block with parties \(i=1,\ldots,r\), settings \(\mathbf{x}=(x_1,\ldots,x_r)\), and outcomes \(\mathbf{a}=(a_1,\ldots,a_r)\), we use \(\mathsf{GLHV}\) for a generalized Bell-local hidden-variable model of the form \[p(\mathbf{a}|\mathbf{x}) = \sum_\lambda q_\lambda \prod_{i=1}^r p_i(a_i|x_i,\lambda),\] with the local response \(p_i\) interpreted as a noncontextual response over the compatible measurements available to party \(i\). This is stronger than mere no-signalling and is the sense in which the block has no generalized Bell-nonlocality. In the worked examples below, the \(\mathsf{GLHV}\) certificates are imported from Ref. [1].

7 From Games to General Tasks↩︎

The previous section is phrased in the language of relation tasks, which makes it resemble Bell games or KS parity games. The purpose of this section is to explain how the same language applies to a broad class of ordinary tasks. The key move is to view a task as a local constraint system.

This is the usual constraint-satisfaction form. It includes Boolean CSPs, graph coloring, graph homomorphism, database consistency constraints, local checks in distributed protocols, and many verification problems. In this representation, each hyperedge \(e\) is a context: \[C_e=e,\qquad W_{C_e}=R_e.\] Thus the task \(T\) induces a relation task \[\mathsf{Rel}(T)=\{(C_e,W_{C_e})\}_{e\in E}.\]

This turns the question “does the task have a globally consistent classical solution?” into the question “does the locally observed empirical model admit a global classical explanation?” The distinction is important:

• If there is one global assignment \(y\) satisfying all \(R_e\), then the compiled task is classically satisfiable.

• If local empirical distributions satisfy every \(R_e\) but cannot be glued into a single global hidden-variable model, then the model exhibits a contextual obstruction.

• If the obstruction only appears after combining otherwise classical local and blockwise explanations, it is a candidate for global contextuality.

The framework is therefore not restricted to hand-built games. It applies to any task that admits a useful local-constraint compilation. The price of this generality is that it does not apply uniformly to all function-computation tasks. A task of the form \[f(x_1,\ldots,x_k)\] where each party must output the same global value cannot be solved without communicating the relevant input information; entanglement or contextuality does not violate no-signalling. The natural quantum advantage tasks in this framework are instead relation, consistency, and sampling tasks, where local outputs are not required to reveal all remote inputs but must jointly satisfy a global relation.

7.1 General coordination problem↩︎

For a compiled task \(T\), define the classical coordination region by applying the cost definition to the induced empirical model: \[\mathsf{Cost}_C^\epsilon(T) := \mathsf{Cost}_C^\epsilon(p_T).\] The central question becomes: \[\text{How far from the origin is } \mathsf{Cost}_C^\epsilon(T)?\] Equivalently, how much communication, memory, or local computation is required for a classical system to coordinate local views into a globally consistent behavior?

The covering numbers below now have a direct task-theoretic meaning. The quantity \(\chi_G(T)\) counts how many global classical explanations are needed to cover all local constraints of the compiled task. If one explanation does not suffice, the classical protocol must coordinate among several explanations using communication, memory, computation, or a mixture of these resources.

7.2 Advantage scale: states versus bits↩︎

This proposition separates two notions of quantum advantage. Let \[K_C^\eta(T)\] be the minimum number of classical coordination states needed to reach success probability at least \(\eta\), and let \[\kappa_C^\eta(T)=\log_2 K_C^\eta(T)\] be the same cost measured in bits. If a quantum procedure wins one copy with probability \(\omega_Q(T)\), while one global classical assignment wins at most \(\beta_G(T)<\omega_Q(T)\), then matching the \(m\)-copy quantum success \(\omega_Q(T)^m\) requires \[K_C^{\omega_Q^m}(T^m) \geq \left(\frac{\omega_Q(T)}{\beta_G(T)}\right)^m\] and therefore \[\kappa_C^{\omega_Q^m}(T^m) \geq m\log_2\!\left(\frac{\omega_Q(T)}{\beta_G(T)}\right).\]

Thus the repeated-task bound is exponential in the raw number of classical coordination states, but linear in the number of communication or memory bits. For the seven-test Hardy task studied below, \[\frac{\omega_Q}{\beta_G}=1+\frac{q}{6},\] so the lower bound is \[K_C\geq (1+q/6)^m, \qquad B+M\geq m\log_2(1+q/6).\] At \(q=1/4\), this is \[K_C\geq (25/24)^m, \qquad B+M\geq 0.0589\,m.\]

This is already a genuine coordination advantage, but it is not an exponential lower bound in bits. To obtain a quadratic or exponential bit-complexity separation, one needs a family of compiled tasks \(\{T_n\}\) whose global contextual covering number grows faster with the problem size: \[\log_2 \chi_G(T_n)=\Omega(n^2) \quad\text{gives a quadratic bit lower bound,}\] whereas \[\log_2 \chi_G(T_n)=\Omega(2^n) \quad\text{would give an exponential bit lower bound.}\] The memory-cost literature for stabilizer-like quantum subtheories suggests that quadratic bit growth is a realistic target in some structured task families [8]. The present Hardy construction does not prove such a scaling; it proves a constant-rate lower bound under parallel repetition.

7.3 Examples of compiled tasks↩︎

1. CSP and graph problems. Variables are vertices or logical variables, and hyperedges are clauses, edges, or local graph constraints. Classical coordination cost measures the resources required to make local constraint choices globally consistent.

2. Distributed consistency. Variables are local replicas, log positions, or transaction states. Hyperedges encode local consistency, serializability, or agreement checks. Communication and memory are the usual resources used to maintain global consistency.

3. MBQC patterns. Variables are local measurement outcomes and contexts are compatible measurement patterns. Classical feed-forward is a coordination mechanism, while the resource state supplies nonclassical correlations. Contextuality or magic marks the part of the pattern that cannot be absorbed into a low-cost classical simulation.

4. Sampling and generation. Variables are local pieces of a sample, such as tokens, patches, or latent factors. Hyperedges encode local semantic, syntactic, or structural constraints. A contextuality-style analysis asks whether the local marginals arise from one global latent-variable model or whether a richer coordination mechanism is required.

7.4 Computer-science reading↩︎

The same formalism can be read without quantum terminology. A relation task is a local-to-global consistency problem: \[\forall C\in\mathcal{C},\quad x_C\in W_C \qquad\Longrightarrow?\qquad \exists x\in\prod_{v\in V}A_v \text{ such that } x|_C=x_C \text{ for all }C.\] In the support version used here, a single global chart solves the task iff \[\exists x\in\prod_{v\in V}A_v \quad \forall C\in\mathcal{C},\quad x|_C\in W_C.\] Contextuality is the failure of this implication when all local pieces are individually meaningful.

For a CSP, \(V\) is the set of variables and each context \(C\) is the scope of a constraint. For a database, the local data are relations \(\{R_C\}_{C\in\mathcal{C}}\), and global consistency asks whether there exists a joint relation \(J\) such that \[\pi_C(J)=R_C \qquad(C\in\mathcal{C}),\] where \(\pi_C\) is projection onto the attributes in \(C\). For a distributed system, a context is a node neighborhood or local view; the global chart is a network-wide state whose restrictions match all local views: \[X|_{N_r(v)}=x_{N_r(v)} \qquad(v\in V_{\rm net}).\] The coordination cost \(\kappa_D(T)=\log_2\chi_G^D(T)\) is therefore the number of bits needed to select among global configuration templates compatible with the local views.

For MBQC, the local variables are measurement outcomes and the classical control data used for feed-forward. A low-cost classical chart would preassign outcomes for all measurement branches: \[s_v=s_v(m_v), \qquad m_v=f_v(x,s_{<v}),\] so contextuality marks the part of the measurement pattern that cannot be absorbed into such a branch-independent classical explanation.

8 Classical Coordination Cost↩︎

We now define the cost region. A classical distributed protocol may use communication, internal memory, and local computation to generate outputs. For a protocol \(\Pi\), write \[\mathrm{cost}(\Pi)=(B(\Pi),M(\Pi),D(\Pi)),\] where \(B\) is total communication in bits, \(M\) is the maximum amount of classical internal memory in bits, and \(D\) is a local computation depth or step bound. The precise choice of \(D\) depends on the computational model; our covering theorem below uses only \(B\) and \(M\), and then refines the covering number by imposing a \(D\)-computability restriction.

The convention is that memory is measured in bits. If a simulation model is specified instead by a finite set of \(S_M\) internal memory states, then in the present notation \[M=\lceil\log_2 S_M\rceil,\] and the covering lower bound may equivalently be read as \[B+\log_2 S_M\geq \log_2\chi_G(T)\] up to integer rounding. This is the conversion used when comparing with memory-cost results stated in terms of the number of hidden states.

The depth parameter \(D\) is a classical postprocessing or chart-generation depth, not a quantum circuit depth. Depending on the application it may mean the depth of a classical circuit generating a global chart, the number of local update rounds in a simulator, or a restricted family of admissible postprocessing maps. The twisted-hypercube example below uses a concrete fan-in-two XOR-tree depth.

The communication-complexity literature studies projections of \(\mathsf{Cost}^\epsilon_C(p)\) onto the \(B\)-axis. The memory-cost literature studies projections onto the \(M\)-axis. The present proposal is to study the full region, especially for globally contextual empirical models.

9 Global Contextual Covering Number↩︎

Thus \(\chi_G(T)=1\) exactly when one global assignment satisfies all contexts. If \(\chi_G(T)>1\), a classical explanation must switch among several global assignments.

Communication and memory contribute directly to this chart-selection budget: \[B+M\geq \kappa_D(T).\] Local computation depth is not itself measured in bits, but it changes the available chart class. The number of coord-bits saved by allowing depth \(D\) instead of depth \(0\) is \[\Delta_D(T) = \kappa_0(T)-\kappa_D(T) = \log_2\!\left(\frac{\chi_G^0(T)}{\chi_G^D(T)}\right),\] whenever the two covering numbers are finite.

9.1 Resource-sensitive covers↩︎

The ordinary covering number only sees the total number of available charts. It therefore gives a sum bound in \(B+M\), not a genuine separation between communication and memory. To expose such trade-offs one must keep track of how charts are selected.

This definition is deliberately model-dependent: different choices of \(\mathfrak S_B\) give different notions of communication. That dependence is a feature rather than a bug, because a true \(B\)-versus-\(M\) theorem cannot be obtained from an unstructured count alone.

Thus the present lower bound is exactly the unstructured projection of a more refined question. To prove that communication and memory are not interchangeable, one must impose an operationally meaningful selector class \(\mathfrak S_B\), such as rectangle selectors in a two-party communication task or protocol-tree selectors in a distributed task.

9.2 Two-party rectangle selectors↩︎

The standard two-party case makes the previous paragraph concrete. Suppose the contexts are indexed by pairs \[(x,y)\in X\times Y,\] where Alice knows \(x\) and Bob knows \(y\). A deterministic \(B\)-bit communication protocol induces a transcript map \[\sigma:X\times Y\to\mathcal{T}, \qquad |\mathcal{T}|\leq 2^B.\] For every transcript \(t\), the fiber \[\sigma^{-1}(t)\] is a combinatorial rectangle \(A_t\times B_t\subseteq X\times Y\). This is the usual rectangle property of deterministic communication protocols [20].

This number refines the ordinary global covering number. Always \[\chi_G^D(T)\leq \operatorname{rect}_G^D(T),\] because every rectangle cover is in particular a cover by charts. The inequality can be strict when the set of contexts won by one chart is nonrectangular and must be decomposed into several communication rectangles.

With memory, the analogous object is a collection of at most \(2^M\) chart libraries, each addressed by a \(B\)-bit rectangle selector. This gives a genuine place to formulate \(B\)-versus-\(M\) questions: communication restricts the geometry of the selector fibers, while memory controls how many such chart libraries are available. The present paper does not compute a nontrivial separation for this refined region, but the definition identifies the next combinatorial object that must be analyzed.

10 Approximate and Repeated Tasks↩︎

Define the best single-assignment success fraction \[\beta_G(T)= \max_g \Pr_{C\sim \mu}[g|_C\in W_C],\] where \(\mu\) is a distribution over contexts. For the uniform distribution, \(\beta_G(T)\) is the largest fraction of contexts covered by one global assignment.

For \(m\) independent copies of the task, a deterministic global assignment is equivalently a tuple of copywise assignments \(g_1,\ldots,g_m\). The assignment \(g_i\) wins at most a \(\beta_G(T)\)-fraction of contexts in copy \(i\), and the product context distribution gives total success at most \(\beta_G(T)^m\). If a classical protocol with \(K\) coordination states succeeds with probability at least \(1-\epsilon\), then \[K\beta_G(T)^m \geq 1-\epsilon.\] Using \(K\leq 2^{B+M}\), we obtain:

For constant \(\epsilon<1\), the leading term is linear in \(m\) whenever \(\beta_G(T)<1\).

11 Scaling Laws for Task Families↩︎

We now state the general asymptotic reading of the preceding bounds. Let \(\{T_n\}\) be a family of relation tasks, where \(n\) is the problem size, and let \(D_n\) be the allowed local computation depth. The relevant quantities are: \[\chi_G^{D_n}(T_n), \qquad \beta_G(T_n), \qquad \gamma_G(T_n), \qquad \operatorname{rect}_G^{D_n}(T_n)\] when a two-party communication structure is present.

The last line is the important bookkeeping point: an exponential number of charts gives only a linear bit lower bound. Exponential bit lower bounds require a doubly exponential number of charts, or a different lower-bound mechanism.

Writing \(\beta_n=1-\delta_n\), the leading rate is \[\log_2(1/\beta_n) = \frac{\delta_n}{\ln 2}+O(\delta_n^2) \qquad(\delta_n\to0).\] Hence a constant soundness gap gives a linear-in-\(m\) bit lower bound, a gap \(\delta_n=1/\operatorname{poly}(n)\) gives only \(m/\operatorname{poly}(n)\), and a one-copy lower bound of order \(\Omega(n^r)\) requires roughly \[\beta_n\leq 2^{-\Omega(n^r)}\] or an equivalent amplification mechanism.

This proposition explains why simply increasing the size of a contradictory constraint system is not enough. If random global charts can cover every context with noticeable probability, then the integral cover is small up to a logarithmic factor. Strong growth of \(\chi_G\) requires delocalized violation: no distribution over classical charts should cover every context with substantial probability.

Finally, in a two-party setting one obtains a genuine communication scaling law from the rectangle refinement: \[B_n \geq \log_2 \operatorname{rect}_G^{D_n}(T_n)\] for memory-free deterministic cover-admissible protocols. Thus \[\operatorname{rect}_G^{D_n}(T_n)\geq 2^{\Omega(n)} \quad\Longrightarrow\quad B_n=\Omega(n),\] and stronger rectangle growth gives stronger communication lower bounds. With memory, the corresponding question is the structured region \(\mathsf R_{\mathfrak S}(T_n)\): memory supplies multiple chart libraries, while communication restricts which chart in a library can be selected by rectangle-shaped transcript fibers.

These scaling laws give a precise search criterion for strong separations. One must find natural global-contextual task families for which at least one of the quantities \[\chi_G^{D_n}(T_n),\qquad \operatorname{rect}_G^{D_n}(T_n),\qquad 1/\beta_G(T_n),\qquad 1/\gamma_G(T_n)\] grows rapidly with \(n\). The Hardy and KCBS examples below prove positivity of the coordination cost; a strong separation would require a family with much faster asymptotic growth.

12 A Lifting Criterion for Strong Separations↩︎

The preceding section says what a strong separation must look like. It does not say how to find one. A useful strategy is not to start from Bell communication-complexity separations, because those usually reintroduce ordinary nonlocality. Instead, one can start from a KS-contextual task family whose classical simulation already has a strong memory lower bound, and then try to embed it into a genuinely global-KS construction.

The parameter controlling such an embedding is a domination weight. For an empirical model \(S=\{S_C\}_{C\in\mathcal{C}}\), define \[\pi_{\mathsf{NC}}(S) = \max_{N\in\mathsf{NC}} \min_{C,o:\,S_C(o)>0}\frac{N_C(o)}{S_C(o)},\] where the maximum ranges over noncontextual empirical models \(N\) on the same finite scenario. Equivalently, \(\pi_{\mathsf{NC}}(S)\) is the largest weight \(p\) for which there exists a noncontextual model \(N\) satisfying \[N_C(o)\geq p\,S_C(o) \qquad \text{for every context }C\text{ and outcome }o.\] The maximum exists because the noncontextual models form a compact polytope and the displayed objective is continuous. Because full-support noncontextual models exist on every finite scenario, \(\pi_{\mathsf{NC}}(S)>0\). If \(\pi_{\mathsf{NC}}(S_n)\) is bounded below by a constant along a seed family, then the flag used below can also have constant probability. For a contextual seed \(S\), one also has \(\pi_{\mathsf{NC}}(S)<1\); otherwise some noncontextual \(N\) would satisfy \(N_C(o)\geq S_C(o)\) for all \(C,o\), hence \(N=S\) by normalization, contradicting contextuality.

The following elementary construction gives the abstract form of such an embedding. Let \(S=\{S_C\}_{C\in\mathcal{C}}\) be any empirical model on a finite measurement scenario, and let \(N=\{N_C\}_{C\in\mathcal{C}}\) be a full-support noncontextual empirical model on the same scenario. Choose \[0<p<1, \qquad p\leq \min_{C,o:\,S_C(o)>0}\frac{N_C(o)}{S_C(o)}.\] Then \[R_C(o)=\frac{N_C(o)-pS_C(o)}{1-p}\] is again an empirical model: nonnegativity follows from the choice of \(p\), normalization is immediate, and no-disturbance is preserved because \(R\) is an affine combination of the no-disturbing models \(N\) and \(S\). Introduce a binary flag measurement \(A\) and define the extended model \(G^{p,N}(S)\) on contexts \(\{A\}\cup C\) by \[G^{p,N}_{A,C}(1,o)=pS_C(o), \qquad G^{p,N}_{A,C}(0,o)=(1-p)R_C(o).\] The unconditioned marginal on the original measurements is \(N\): \[\sum_{a\in\{0,1\}}G^{p,N}_{A,C}(a,o)=N_C(o).\] Thus the original subsystem is locally noncontextual after the flag is ignored, while conditioning on \(A=1\) recovers the seed model \(S\).

This lift should be read as a clean mathematical mechanism, not as a complete physical construction by itself. At the level of a single tested block \(\{A\}\cup C\), the model is just an ordinary joint distribution and hence has a blockwise classical explanation. What fails is the gluing of those blockwise explanations into one context-independent global chart. To obtain the exact “local NCHV plus \(\mathsf{GLHV}\)-local blocks” property in a concrete multipartite experiment, one must realize this hiding mechanism inside a physical scenario such as the polarization-path or postselected constructions of Ref. [1].

There is also a support-versus-distribution distinction. The unconditioned support of \(G^{p,N}(S)\) may be easy to cover, because the \(A=0\) filler branch can contain many classical outcomes. The lift is therefore a strong tool for exact probabilistic simulation, approximate simulation with controlled conditioning, or explicitly flagged tasks. It should not be interpreted as automatically producing a large bare support-covering number \(\chi_G(G^{p,N}(S))\).

We isolate the required reduction in a form that can be checked independently of any particular construction. Let \(S\) be a KS-contextual seed task and let \(G\) be a larger multipartite task. We say that \(S\) is a flag reduction of \(G\) if there is an event \(F\) of positive probability and a relabelling of the contexts and outcomes in the conditional model \(G\mid F\) such that the relabelled conditional model is exactly \(S\). The reduction is cost-preserving for a class of classical simulators if postselecting a simulator for \(G\) on \(F\), and then applying the relabelling, produces a simulator for \(S\) with no larger set of internal classical states or global charts.

The same reduction has an approximate version. Suppose the target model \(G\) has flag probability \(p_F>0\), independent of the post-flag context, and a classical simulator \(\widehat G\) satisfies \[\mathsf{TV}(\widehat G_C,G_C)\leq \epsilon\] for every flagged context \(C\). If \(\epsilon<p_F\), then the simulator’s conditional distribution given \(F\) is well-defined and satisfies \[\mathsf{TV}(\widehat G_C(\,\cdot\,|F),G_C(\,\cdot\,|F)) \leq \frac{2\epsilon}{p_F}.\] Indeed, for the event \(F\), the subnormalized measures \(\widehat G_C(\cdot,F)\) and \(G_C(\cdot,F)\) differ by at most \(\epsilon\) in total variation, and their total masses differ by at most \(\epsilon\). Normalizing by \(p_F\) therefore costs at most another \(\epsilon/p_F\). Thus an \(\epsilon\)-accurate simulator for the lifted model gives a \((2\epsilon/p_F)\)-accurate simulator for the seed.

Consequently, if simulating \(S_n\) within error \(\delta\) requires \(L(n,\delta)\) bits of memory or coordination, then simulating a lifted model \(G_n\) within error \(\epsilon\) requires at least \[L\!\left(n,\frac{2\epsilon}{p_{F,n}}\right)\] bits, as long as the flag reduction is cost-preserving. Constant flag probability preserves approximate lower bounds up to constant factors.

Putting these observations together gives the strong-separation transfer principle.

This is the clean abstract main theorem. It says that any KS seed lower bound can be turned into a genuine-global-KS lower bound at the level of finite empirical models and conditioning-closed simulator classes. The theorem is unconditional in that category: the lift \(G_n=G^{p_n,N_n}(S_n)\) is explicit. What remains construction-dependent is whether a given lifted family has the desired physical realization as a multipartite experiment with local NCHV and \(\mathsf{GLHV}\)-local tested blocks. Thus the theorem should not be read as a finished physical strong-separation construction; it is an unconditional abstract reduction whose physical instantiation requires additional certificates.

For example, Karanjai, Wallman, and Bartlett show that exact classical simulation of the qubit stabilizer subtheory requires memory growing quadratically in the number of qubits [8]. If the stabilizer seed is represented inside a conditioning-closed simulator class \(\mathcal{P}\), then the abstract lift gives a family \(G_n\) with \[K_{\mathcal{P}}(G_n)\geq K_{\mathcal{P}}(S_n),\] and hence, for the corresponding memory measure, \[M(G_n)\geq M(S_n)=\Omega(n^2).\] This is the proposed route from existing stabilizer memory lower bounds to a quadratic genuine-global-KS separation. The remaining work is not the abstract reduction, but the model alignment and physical realization.

For exact simulation, the probability of the flag does not affect the memory or state-count inheritance: conditioning does not create new classical states. For approximate simulation or for unconditioned success-probability games, the flag probability matters through the \(2\epsilon/p_F\) amplification above. This is why a constant-probability flag is the clean target for an unconditional quantitative separation.

The resulting search problem is therefore concrete: \[\begin{array}{ll} \text{(i)} & \text{choose a KS seed family }S_n\text{ with a proved lower bound;}\\ \text{(ii)}& \text{build a global lift }G_n\text{ with a positive-probability flag;}\\ \text{(iii)}& \text{prove local NCHV and blockwise } \mathsf{GLHV}\text{-locality for }G_n;\\ \text{(iv)}& \text{prove that postselection on the flag preserves the classical model class.} \end{array}\] The last two items are the genuinely global part of the problem. They are also what distinguishes this route from importing an ordinary Bell communication-complexity separation.

This also clarifies the relation with known strong separations. In Bell or nonlocal-game separations, one normally proves a lower bound on communication directly: a quantum strategy uses shared entanglement and little or no communication, while every classical strategy needs a large transcript. This is a strong result on the \(B\)-axis, but the source of the advantage is ordinary nonlocality. In KS and stabilizer-simulation separations, one proves that a classical simulator needs many internal states or many bits of memory; this is a strong result on the \(M\)-axis, but the source of the advantage is local contextuality. The lifting programme above aims at a different statement: \[\text{strong KS memory lower bound} \quad\Longrightarrow\quad \text{strong genuine-global-KS coordination lower bound}.\] The lower-bound technology is inherited from the KS seed, while the lift changes the attribution of the obstruction: after lifting, the local marginals and the tested Bell-like blocks are classically explainable, but the whole network still cannot be glued into one GNCHV model.

13 Recovering the Bell and KS Readings↩︎

13.1 GHZ/Mermin↩︎

In the three-party GHZ game, there are four contexts: \[000,\;011,\;101,\;110.\] Any deterministic classical assignment satisfies at most three of the four parity constraints, while the quantum GHZ strategy satisfies all four. Thus \[\beta_G=3/4.\] For \(m\) repetitions, \[B+M \geq m\log_2(4/3)+\log_2(1-\epsilon).\] When memory is treated as fixed or free, this is read as a communication lower bound. It is the Bell/nonlocal projection of the coordination-cost framework.

13.2 Mermin–Peres square↩︎

The Mermin–Peres square has six contexts: three rows and three columns. Because of the parity contradiction, any deterministic noncontextual assignment satisfies at most five of the six constraints, whereas quantum observables satisfy all six. Hence \[\beta_G=5/6.\] For \(m\) repetitions, \[B+M \geq m\log_2(6/5)+\log_2(1-\epsilon).\] In a single-system simulation where there is no communication resource, this becomes a memory lower bound. It is the KS/contextual projection of the same coordination-cost framework.

14 Toward Genuine Global Contextuality↩︎

The preceding examples are sanity checks: GHZ is naturally read through nonlocality, and Mermin–Peres through local contextuality. The new target is a genuinely global contextual model satisfying: \[\begin{array}{ll} \text{(i)} & \text{local subsystems admit noncontextual explanations},\\ \text{(ii)} & \text{observed multipartite blocks admit generalized Bell-local explanations},\\ \text{(iii)} & \text{the whole model admits no global noncontextual hidden-variable model}. \end{array}\] For such a model, the same quantities \(\chi_G\) and \(\beta_G\) can be computed relative to global noncontextual assignments. If \(\beta_G<1\), the same repeated-task argument gives \[B+M \geq m\log_2(1/\beta_G)+\log_2(1-\epsilon).\] If one also restricts local computation depth \(D\), use the depth-restricted covering number \(\chi_G^D(T)\) defined above. Then \[B+M \geq \log_2 \chi_G^D(T).\] This expresses a communication–memory–computation trade-off: more local computation may reduce the number of classical explanations that must be communicated or stored, while restricted local computation forces larger communication or memory. Equivalently, one may use the inverse trade-off function \(D_T(K)\) to state a lower bound on local depth for a given coordination budget \(K\leq2^{B+M}\). This is still a coarse trade-off: the bound depends on the total number of available coordination states, not on a separate lower bound forcing both \(B>0\) and \(M>0\).

15 A Worked Global-Contextual Example↩︎

We now apply the covering idea to a genuinely global contextual construction, namely the \(2\times4\) polarization-path obstruction in Ref. [1]. The point of this example is that the relevant data are locally noncontextual and admit a \(\mathsf{GLHV}\) block description, but cannot be glued into one GNCHV model.

We use Ref. [1] for the local NCHV and \(\mathsf{GLHV}\) certificates. The calculation below does not rederive those certificates. Its contribution is to take the support obstruction from that construction, compile it into a seven-test relation task, and compute the resulting global-covering lower bound.

15.1 The Hardy support structure↩︎

There are six binary observables \[X_1,\;Y_1,\;X_1',\;Y_1',\;X_2,\;Y_2.\] The first two act on Bob’s polarization degree of freedom, the primed observables act on Bob’s path degree of freedom, and \(X_2,Y_2\) act on Alice. The compatible triples used in the Hardy obstruction are: \[\begin{array}{lll} (X_1,Y_1',Y_2),& (Y_1,X_1',Y_2),& (Y_1,Y_1',X_2),\\[1mm] (X_1,X_1',X_2).& \end{array}\] The quantum construction enforces six zero-probability events: \[\begin{align} p(x_1{=}1,\,y_1'{=}1,\,y_2{=}1)&=0, \tag{1}\\ p(y_1{=}1,\,x_1'{=}1,\,y_2{=}1)&=0, \tag{2}\\ p(y_1{=}1,\,y_1'{=}1,\,x_2{=}1)&=0, \tag{3}\\ p(x_1{=}1,\,y_1'{=}0,\,y_2{=}0)&=0, \tag{4}\\ p(y_1{=}0,\,x_1'{=}1,\,y_2{=}0)&=0, \tag{5}\\ p(y_1{=}0,\,y_1'{=}0,\,x_2{=}1)&=0, \tag{6} \end{align}\] and a positive target event \[p_{\rm Q}(x_1{=}1,x_1'{=}1,x_2{=}1) = q = h_0^2(1-h_0^2)>0. \label{eq:ourHardyTarget}\tag{7}\]

The logical contradiction is simple. Suppose a deterministic global assignment has \[x_1=x_1'=x_2=1.\] If \(y_1'=0\), then the zero constraints force \[y_2=1.\] Indeed, \(y_2=0\) would trigger Eq. 4 . Now Eq. 2 , together with \(x_1'=1\) and \(y_2=1\), forces \(y_1=0\), whereas Eq. 6 , together with \(y_1'=0\) and \(x_2=1\), forces \(y_1=1\). This is impossible. If \(y_1'=1\), then the zero constraints force \[y_2=0.\] Here \(y_2=1\) would trigger Eq. 1 . Now Eq. 3 , together with \(y_1'=1\) and \(x_2=1\), forces \(y_1=0\), whereas Eq. 5 , together with \(x_1'=1\) and \(y_2=0\), forces \(y_1=1\). This is impossible. Thus any GNCHV global assignment satisfying all six zero constraints must have \[p(x_1{=}1,x_1'{=}1,x_2{=}1)=0.\]

Equivalently, every GNCHV model satisfies the Hardy witness inequality \[\begin{align} \mathcal{W}_H &= p(x_1{=}1,x_1'{=}1,x_2{=}1) -p(x_1{=}1,y_1'{=}1,y_2{=}1) \\ &\quad -p(y_1{=}1,x_1'{=}1,y_2{=}1) -p(y_1{=}1,y_1'{=}1,x_2{=}1) \\ &\quad -p(x_1{=}1,y_1'{=}0,y_2{=}0) -p(y_1{=}0,x_1'{=}1,y_2{=}0)\\ &\quad -p(y_1{=}0,y_1'{=}0,x_2{=}1) \leq 0, \end{align}\] while the quantum model has \[\mathcal{W}_H=q>0.\]

15.2 The associated seven-test game↩︎

Define a relation game \(H_q\) with seven equally likely tests:

• six zero tests, one for each event in Eqs. 1 –6 ; on such a test the players win unless the corresponding forbidden event occurs;

• one target test on context \((X_1,X_1',X_2)\); on this test they win iff \(x_1=x_1'=x_2=1\).

Thus a perfect cover of the seven labelled tests already requires at least one coordination bit. The repeated-task bound below is stronger for comparing against the quantum success probability, because it uses the single-chart success fraction \(\beta_G(H_q)=6/7\) rather than the perfect-cover number \(\chi_G(H_q)=2\).

The quantum strategy wins all six zero tests with probability one, and wins the target test with probability \(q=h_0^2(1-h_0^2)\). Under the uniform input distribution, \[\omega_Q(H_q)=\frac{6+q}{7} > \frac{6}{7} = \beta_G(H_q).\] The maximal value of \(q\) is \(1/4\), attained at \(h_0^2=1/2\), giving \[\omega_Q=\frac{25}{28}.\]

15.3 Coordination lower bound↩︎

Consider \(m\) independent repetitions of the seven-test Hardy game, with the winning condition that all copies are won. A single global assignment wins with probability at most \[\left(\frac{6}{7}\right)^m.\] If a classical protocol can coordinate among at most \(K\) deterministic global assignments, a union bound gives success probability at most \[K\left(\frac{6}{7}\right)^m.\] To match the quantum success probability \[\left(\frac{6+q}{7}\right)^m,\] one must have \[K \geq \left(\frac{6+q}{6}\right)^m = (1+q/6)^m.\] Since a protocol with \(B\) bits of communication and \(M\) bits of coordination memory has at most \(2^{B+M}\) coordination states, we obtain \[B+M \geq m\log_2(1+q/6).\] At the balanced point \(q=1/4\), \[B+M \geq m\log_2(25/24) \approx 0.0589\,m.\]

This is the first explicit lower bound in the present framework coming from a genuinely global contextual construction rather than from ordinary Bell nonlocality or an isolated local KS scenario. The bound is modest because the Hardy success gap is modest, but it has the desired logical form: \[\text{NCHV-local}+\mathsf{GLHV}+\text{not GNCHV} \quad\Longrightarrow\quad \text{positive classical coordination cost}.\]

16 A Postselected KCBS Global-Contextual Task↩︎

The Hardy task is support-based and gives a small constant. The \(2\times3\) KCBS construction of Ref. [1] gives a different kind of example: after postselecting Alice’s outcome \(A_1=+1\), Bob’s conditional qutrit state violates the KCBS inequality, even though the unconditional Bob marginal is KCBS-noncontextual and the tested multipartite scenario has a \(\mathsf{GLHV}\) certificate at the reported point \(c_0=1/4\). This gives a stronger conditional coordination rate.

Consider the five KCBS contexts \[C_j=\{B_j,B_{j+1}\}, \qquad j=0,\ldots,4\] with indices modulo five, and define the anti-correlation relation task \[W_j=\{(b_j,b_{j+1}): b_jb_{j+1}=-1\}.\] This is the usual odd-cycle parity obstruction.

For the conditional state \(|0\rangle\) in the KCBS construction, Ref. [1] gives \[\langle D\rangle_{A_1=+1} = 5-4\sqrt5, \qquad D=\sum_{j=0}^{4}B_jB_{j+1}.\] By symmetry each adjacent product has expectation \[\langle B_jB_{j+1}\rangle = \frac{5-4\sqrt5}{5} = 1-\frac{4}{\sqrt5}.\] Therefore the conditional quantum winning probability for one KCBS anti-correlation test is \[\omega_Q^{\rm cond} = \Pr[b_jb_{j+1}=-1\mid A_1=+1] = \frac{1-\langle B_jB_{j+1}\rangle}{2} = \frac{2}{\sqrt5}.\] This exceeds the global noncontextual value \(4/5\).

For \(m\) independent postselected KCBS tests, matching the conditional quantum success probability requires \[K \geq \left( \frac{2/\sqrt5}{4/5} \right)^m = \left(\frac{\sqrt5}{2}\right)^m.\] Thus every cover-based classical simulation of the conditional branch satisfies \[B+M \geq m\log_2\!\left(\frac{\sqrt5}{2}\right) \approx 0.1610\,m.\]

This rate is larger than the Hardy rate \(m\log_2(25/24)\). Its status is different, however: it is a postselected, inequality-based lower bound. At the \(\mathsf{GLHV}\)-certified point \(c_0=1/4\), Ref. [1] reports that the branch \(A_1=+1\) occurs with probability \(1/16\). Thus the statement above should not be read as an unconditional success-probability separation. Rather, it says that once the globally contextual postselected branch is selected, the resulting KCBS statistics require a larger classical chart-coordination rate.

The flagged \(3\times3\) qutrit Werner-local construction in Ref. [1] gives a state-level version of the same conditional mechanism. At the reported point \(\epsilon=w=1/2\), Alice’s flag outcome has probability \(2/3\), and Bob’s conditional KCBS value is \[\langle D\rangle_{B|0} = \frac{35-33\sqrt5}{12}.\] By the same five-cycle anti-correlation conversion, the conditional winning probability is \[\omega_Q^{\rm flag} = \frac{1}{2}\left( 1-\frac{1}{5}\frac{35-33\sqrt5}{12} \right) \simeq 0.82325.\] Since the classical value is still \(4/5\), the corresponding repeated-branch rate is \[B+M \geq m\log_2\!\left(\frac{\omega_Q^{\rm flag}}{4/5}\right) \simeq 0.0413\,m.\] This is weaker than both the \(2\times3\) postselected KCBS rate and the Hardy rate, so we record it only as a state-level consistency check rather than as a main quantitative example.

17 Discussion↩︎

The proposed framework reframes several known facts in a common language. Nonlocality, contextuality, and global contextuality are not merely labels for different quantum phenomena. They are obstructions to low-cost classical coordination. Classical simulation can overcome such obstructions by paying communication, by storing more hidden state, by doing more local computation, or by some combination of the three.

The main claim can therefore be stated as follows: \[\text{global contextuality lower-bounds the distance of } \mathsf{Cost}^\epsilon_C(p) \text{ from the origin}.\] The covering-number bound provides a first, simple version of this claim. A full theory should refine it by using approximate polytopes, information complexity, memory-state lower bounds, and computation-depth restrictions.

Scope and limitations↩︎

The current results should be read as a first covering-number theory, not as a complete complexity theory of global contextuality. There are several important limitations.

First, the main inequalities are mostly sum bounds such as \[B+M\geq \log_2\chi_G(T).\] They show that a classical cover-admissible simulator needs enough total coordination capacity to select among sufficiently many global charts. They do not by themselves prove that communication and memory are simultaneously necessary, nor do they identify an optimal trade-off curve between the \(B\)-axis and the \(M\)-axis. The resource-sensitive covering region defined above is a first formal interface for this problem, but a sharper theory would need to compute it for concrete communication structures, memory update rules, and local-depth models.

A related refinement would replace the worst-case transcript length \(B\) by an information cost, for example a quantity of the form \[I(C;T_{\rm tr})+H(S_{\rm mem}),\] where \(C\) is the queried context, \(T_{\rm tr}\) is the transcript, and \(S_{\rm mem}\) is the simulator’s internal coordination state. Such a theory would be closer to information complexity, but it is not developed here.

Second, the protocol model is intentionally restricted. A cover-admissible protocol is one in which a transcript-memory pair determines a context-independent global chart. This is the right model for the elementary covering argument, but it is not identical to the sequential automaton memory models used in parts of the KS simulation literature. Relating these models requires an operational reduction that is not supplied here.

Third, the computation-depth axis depends on a chosen local computation model. The twisted hypercube calculation makes this dependence explicit by using a fan-in-two parity-tree model, where depth \(D\) can combine at most \(2^D\) input coordinates. This gives an exact and useful toy calculation, but it is not a physical global-KS example. The analogous calculation for the Hardy support task, or for a stronger GNCHV obstruction, remains open.

Fourth, the genuinely global-contextual examples still have modest or qualified quantitative strength. The Hardy support task gives an unconditional positive coordination cost, but the constant \(\log_2(25/24)\) is small. The KCBS branch gives the larger rate \(\log_2(\sqrt5/2)\), but it is postselected and should not be read as an unconditional success-probability separation. Strong bit-complexity separations would require natural task families with much larger growth of \(\log_2\chi_G(T_n)\), \(\log_2\chi_G^D(T_n)\), or \(\log_2\operatorname{rect}_G^D(T_n)\).

Outlook: quantum networks↩︎

The same resource accounting is natural for quantum networks and quantum internet scenarios, where remote nodes are connected by quantum channels, entanglement distribution, local operations, and classical control messages [21], [22]. A network task has local node views, edge or small-block tests, and a desired global correlation. In the notation of this paper one may write a network support task as \[T_{\rm net}=(\mathcal{C}_{\rm node}\cup\mathcal{C}_{\rm edge}\cup\mathcal{C}_{\rm block},\{W_C\}),\] and a classical network simulator with communication \(B_{\rm net}\), node memory \(M_{\rm node}\), and local processing depth \(D\) obeys the same covering constraint \[B_{\rm net}+M_{\rm node} \geq \kappa_D(T_{\rm net}) = \log_2\chi_G^D(T_{\rm net})\] whenever the cover-admissible reduction applies. Genuine global KS contextuality is then a network-level obstruction: every local node and every tested block may have a classical explanation, while the whole network lacks a single globally consistent hidden-state chart. This is close in spirit to the broader study of nonclassicality in networks, including bilocal and network-locality constraints [23], but the present focus is the KS-style global-chart obstruction and its coordination cost.

Outlook: generative models↩︎

The same language also suggests a cautious connection to generative modeling. A generative model is asked to produce a global sample \[x=(x_v)_{v\in V}\] whose local windows, modalities, or semantic constraints match a family of observed local distributions \[\{p_C\}_{C\in\mathcal{C}}.\] In a classical latent-variable generator, one may view the latent state, the attention transcript, cached internal state, and sampling depth as coordination resources. Abstractly, the generator selects a chart or a mixture of charts and then emits local pieces that must glue into one coherent sample.

This does not mean that the present framework proves an advantage for current large language models or diffusion models. Rather, it gives a possible lower bound language for a narrower question: when do locally consistent generative constraints fail to admit a low-cost global latent explanation? For a support-level generative task \(T_p\), if the local supports define a contextual or globally contextual obstruction, then any cover-admissible classical generator with communication \(B\), memory \(M\), and local depth \(D\) must satisfy \[2^{B+M}\geq \chi_G^D(T_p).\] Equivalently, if only \(K\) latent charts are available, then the generator requires \[D\geq D_{T_p}(K).\]

This perspective is compatible with the quantum generative-model literature, where quantum circuits are used as Born-rule samplers or adversarial generators [24]–[26]. It is also consistent with the more cautious quantum-machine-learning literature: expressive quantum samplers do not by themselves remove the difficulties of training, data access, model selection, or classical learnability from samples [27], [28]. Thus the claim suggested here is not a practical quantum advantage claim for present-day generative AI systems. It is a structural claim: global contextuality can be read as an obstruction to low-cost classical generative coordination.

The present worked example gives the correct qualitative phenomenon but only a modest quantitative rate: exponentially many classical coordination states in the number of repetitions, equivalently a linear number of coordination bits. One clear next step is to identify natural compiled task families for which \(\log_2\chi_G(T_n)\) is quadratic or exponential in the task size.

Acknowledgements↩︎

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

References↩︎