We formulate classical simulation of quantum correlations as coordination across a spacetime separator. All past-dependent information capable of influencing the future must cross the separator either through communicated messages or through a persistent classical state. We prove a general lower bound on this classical coordination cost in terms of the nonnegative rank of the separator correlation matrix, with approximate and amortized extensions governed by approximate nonnegative rank and Wyner common information. For sequential processes, we introduce a causal positive-realization rank that enforces consistent response and state-update maps, and we explain how bounded local computation and support-covering models arise as restricted cases. We apply the framework to genuine global Kochen--Specker contextuality, in which local subsystems are noncontextual and the tested multipartite blocks are generalized-Bell-local, while the complete empirical model has no global noncontextual explanation. At the symmetric point of a polarization--path Hardy construction, exact classical simulation requires two coordination bits, whereas the corresponding quantum separator requires one qubit. Under exact repetition, the classical lower bound is the base-two logarithm of three bits per copy; with asymptotically vanishing error, it becomes one and a half classical bits per copy, compared with one qubit per copy. We further construct a finite stabilizer--Peres--Mermin family for which the exact classical coordination cost grows quadratically with system size, while the quantum boundary cost grows only linearly. The separation applies to arbitrary finite-state causal online simulators. Establishing a constant-error quadratic separation and an intrinsic construction without flag conditioning remain open.
Comments
44 pages. Added general nonnegative-rank coordination bounds, exact and asymptotic Hardy separations, an exact quadratic separation, and clarified the GLHV assumptions and support-covering framework. Comments and suggestions are welcome on alphaXiv
We formulate classical simulation of quantum correlations as coordination across a spacetime separator. All past-dependent information capable of influencing the future must cross the separator either through communicated messages or through a persistent classical state. We prove a general lower bound on this classical coordination cost in terms of the nonnegative rank of the separator correlation matrix, with approximate and amortized extensions governed by approximate nonnegative rank and Wyner common information. For sequential processes, we introduce a causal positive-realization rank that enforces consistent response and state-update maps, and we explain how bounded local computation and support-covering models arise as restricted cases. We apply the framework to genuine global Kochen--Specker contextuality, in which local subsystems are noncontextual and the tested multipartite blocks are generalized-Bell-local, while the complete empirical model has no global noncontextual explanation. At the symmetric point of a polarization--path Hardy construction, exact classical simulation requires two coordination bits, whereas the corresponding quantum separator requires one qubit. Under exact repetition, the classical lower bound is the base-two logarithm of three bits per copy; with asymptotically vanishing error, it becomes one and a half classical bits per copy, compared with one qubit per copy. We further construct a finite stabilizer--Peres--Mermin family for which the exact classical coordination cost grows quadratically with system size, while the quantum boundary cost grows only linearly. The separation applies to arbitrary finite-state causal online simulators. Establishing a constant-error quadratic separation and an intrinsic construction without flag conditioning remain open.
A set of quantum data can look classical in every local test and still fail to admit a single classical explanation of the whole composite system. We formulate this failure as global contextuality. Here global means global in the physical sense of the whole multipartite system, not the local/global terminology of sheaf theory. Each party's local statistics are noncontextual and each measured multipartite context admits a generalized local hidden-variable description, but the GLHV block descriptions cannot be promoted to a single noncontextual hidden-variable model for the whole system. Three bipartite constructions exhibit this separation. A polarization-path construction gives a direct global obstruction. A qubit-qutrit KCBS construction gives an algebraic scenario-level example, with explicit formulas for the unconditional KCBS operator, the correlation-polytope constraints, and the postselected violation. A flagged qutrit Werner-local state gives a state-level example: the state is entangled and local for all projective measurements, its local qutrit marginals do not violate KCBS, yet postselection rules out a single GNCHV model. We also spell out the classical composition lemma: classical conditional hidden variables can be absorbed into a larger hidden variable, whereas quantum contextual data need not allow such a factorization. Within the general Bell-type framework considered here, with arbitrary parties and arbitrary local compatible contexts, but no cross-party joint measurements, the absence of local contextuality and GLHV-type generalized Bell nonlocality does not imply the existence of a global noncontextual hidden-variable model. Global contextuality is thus a compositional obstruction to classical explanation.
Bell nonlocal correlations cannot be reproduced by local hidden-variable models without communication, making classical communication cost a natural quantitative measure of nonlocality. Although finite communication always suffices to simulate any correlation in a fixed finite Bell scenario, determining the minimum amount needed to (exactly) simulate any given nonlocal correlation remains challenging, especially in the average-cost setting. Here, we derive lower bounds on input-average communication cost from nonlocal games, allowing variable-length, fully interactive two-way protocols. When applied to parallel games, these bounds yield explicit finite quantum correlations for which the exact simulation cost exceeds any prescribed finite input-average communication budget. For n parallel Magic-Square-winning correlations, we prove a lower bound of nlog2(3/2) bits and give a one-way communication protocol that attains this rate asymptotically. For the quantum correlation maximally winning the n-copy of the Clauser--Horne--Shimony--Holt nonlocal game, we obtain an input-average lower bound of approximately 0.04627n bits for exact simulation. Finally, we formulate a hierarchy of lower bounds and complementary upper bounds using deterministic correlations up to chosen communication costs. Both recover the exact input-average cost at their final levels, and if the bounds agree at lower levels, their common value yields the exact input-average cost without needing to consider all communication strategies.
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(logN) qubits and Ω(N) classical boundary bits. Continual requirements auditing inherits a Max-kSAT streaming separation: a recurrent solver uses O(log5nlog(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≥21n2+(23−log23)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.
The emergence of classicality is fundamentally driven by the interaction between a quantum system and its environment. Foundational open-system approaches, notably the Caldeira-Leggett model, successfully captured how these interactions lead to macroscopic effects like quantum dissipation and decoherence. However, these approaches often leave the precise definitions of classicality and quantumness ambiguous. In quantum information theory, this boundary is a heavily scrutinized question, and Kochen-Specker contextuality emerges as a hallmark of nonclassicality. It is therefore natural to investigate whether decoherence can actually suppress this property. Taking this path creates an apparent conundrum, once there exist two distinct manifestations of quantum contextuality: state-dependent and state-independent ones. While state-dependent contextuality naturally vanishes under state degradation, state-independent contextuality could persist for any quantum state, since it shows up even for the maximally mixed state! In this paper, we resolve this apparent paradox by analyzing sequential measurement implementations of the paradigmatic Klyachko, Can, Binicioğlu, and Shumovsky (KCBS) and Peres-Mermin prepare-and-measure scenarios under the influence of depolarizing channels. By introducing noise both prior to and in between measurements, and by analyzing the resulting sequential correlators in both the Schrödinger and Heisenberg pictures, we show how open-system dynamics suppress the correlations required to witness contextuality, leading to classicalization.
Bell's theorem implies that the outcomes of local measurements on two maximally entangled systems cannot be simulated without classical communication between the parties. The communication cost is finite for n Bell states, but it grows exponentially in n. Three simple protocols are presented that provide approximate simulations for low-dimensional entangled systems and require a linearly growing amount of communication. We have tested them by performing some simulations for a family of measurements. The maximal error is less than 1 in three dimensions and grows sublinearly with the number of entangled bits in the range numerically tested. One protocol is the multidimensional generalization of the exact Toner-Bacon [Phys. Rev. Lett. 91, 187904 (2003)] model for a single Bell state. The other two protocols are generalizations of an alternative exact model, which we derive from the Kochen-Specker [J. Math. Mech. 17, 59 (1967)] scheme for simulating single-qubit measurements. These protocols can give some indication for finding optimal one-way communication protocols that classically simulate entanglement and quantum channels. Furthermore they can be useful for deciding if a quantum communication protocol provides an advantage on classical protocols.
A long-standing open question is to characterize the classical communication cost of simulating the correlations arising from measurements on finite-dimensional quantum systems. We consider this question in the prepare-and-measure scenario. First we construct a classical simulation model involving a finite average number of bits of one-way communication that simulates exactly the correlations arising from arbitrary d-dimensional quantum states and arbitrary measurements. Second, we show that no classical simulation protocol involving a finite average message dimension can exist for d≥4, hence strengthening a recent result of de Gois, Santos and Vieira. Our first result relies on a more general simulation theorem which can be applied to certain continuous variable (i.e. infinite-dimensional) quantum systems, and even beyond quantum theory, e.g. to generalized probabilistic theories. In particular, we show that multimode Gaussian states of bounded average energy and general Gaussian measurements admit an exact classical simulation with a finite expected number of bits. Overall, our results show that the classical simulation cost of quantum communication is essentially as high as it could be.