Genuine Global Kochen-Specker Contextuality as Classical Coordination Cost
2026-06-22 • Computational Complexity
Computational Complexity
AI summaryⓘ
The authors study a unique type of quantum behavior called genuine global Kochen-Specker (KS) contextuality, where individual parts seem normal on their own but together they can't be explained classically. They create a new way to measure how much coordination (like communication or memory) is needed to simulate these quantum effects on a classical system. By introducing concepts like coordination bits and global contextual covering numbers, they show how to relate simpler quantum tasks to more complex global ones. They also apply their framework to specific quantum scenarios to illustrate their approach.
Kochen-Specker contextualitylocal hidden-variable modelsBell localityquantum correlationsclassical simulationcoordination costHardy paradoxKCBS inequalitypostselectionscaling laws
Authors
Ming Yang
Abstract
Classical simulations of quantum correlations can fail because no low-communication local hidden-variable model exists, or because no single noncontextual hidden state can explain all compatible measurement contexts. This manuscript studies a third regime: genuine global Kochen-Specker contextuality, where local subsystems are noncontextual and the tested multipartite blocks are generalized-Bell-local, but the whole empirical model admits no global noncontextual hidden-variable explanation. We propose a coordination-cost framework in which communication, memory, and local computation are treated as different ways for a classical simulator to maintain a global classical explanation from locally available information. We introduce coordination bits, global contextual covering numbers, scaling laws for task families, and an abstract lifting theorem showing how classical simulation lower bounds for KS-contextual seed families can be transferred to genuinely global-KS models. As worked examples, we analyze a polarization-path Hardy obstruction and postselected KCBS-type tasks.