⚛️ quantum physics

Playing Nonlocal Games with Little to No Shared Randomness

This paper investigates classical models of Bell nonlocality under restricted shared randomness, characterizing achievable correlations through multiple linear functionals and extending these findings to quantum networks to derive new nonlinear inequalities that distinguish correlated sources and yield entropic Bell inequalities.

Original authors: Mingze Xu, Eric Chitambar

Published 2026-08-11

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: Mingze Xu, Eric Chitambar

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine the universe as a giant, cosmic game of dice. For centuries, scientists believed that if two people rolled dice in different rooms, the results could only be correlated if they had secretly agreed on a plan beforehand or if someone had handed them matching dice. This is the world of "classical physics," where everything is local and predictable. But then, a famous physicist named John Bell came along and showed that quantum particles can do something spooky: they can roll perfectly matching dice even when they are light-years apart, with no secret plan and no matching dice. This phenomenon, called "Bell nonlocality," proves that nature is far stranger than our everyday intuition suggests. It's the foundation for super-secure communication and powerful quantum computers. However, most experiments assume the players have an unlimited supply of "shared randomness"—like an infinite bag of pre-agreed notes they can use to coordinate their moves. But what if they don't have that luxury? What if they have to play the game with zero notes, or just a few? That is the puzzle this paper tackles.

The authors of this study, Mingze Xu and Eric Chitambar, decided to investigate what happens when we take away the "shared randomness" of the game. In the standard game, if you have unlimited shared randomness, the rules of the game form a smooth, convex shape (like a perfect sphere), and simple straight-line rules (linear inequalities) can easily tell you if someone is using a strategy that deviates from classical expectations or using quantum magic. But the researchers discovered that when you limit or remove that shared randomness, the shape of the game changes drastically. It becomes "nonconvex," which is a fancy way of saying it turns into a jagged, weirdly shaped blob with holes and bumps. You can no longer use simple straight lines to detect deviations from classical expectations; you need a more complex, curved net.

To solve this, the team developed a new way to play the game. Instead of looking at just one score at a time, they proposed looking at multiple scores simultaneously. Imagine trying to guess a friend's secret number. If you only ask, "Is it bigger than 5?" you might get a yes or no that doesn't tell you much. But if you ask, "Is it bigger than 5?" AND "Is it even?" AND "Is it a multiple of 3?" all at once, the combination of answers reveals a much tighter, more specific picture. The paper shows that by checking several different "Bell functions" (which are just different ways of scoring the dice game) at the same time, you can detect if two parties are secretly sharing randomness, even if they are trying to hide it. They found that without any shared randomness, the players can only achieve certain combinations of scores, and these combinations form a specific, non-smooth boundary. If the players' scores fall outside this jagged boundary, it proves they must have some shared randomness or are using quantum entanglement.

The researchers didn't stop at just two players. They expanded their game to a "quantum network," which is like a party where many people are connected by different sources of information, like a star-shaped web. Usually, scientists assume every source in this web is independent, like different people rolling their own dice. But this paper asks: "What if the sources are actually talking to each other?" They relaxed this assumption and created new, curved rules (nonlinear inequalities) to test for this hidden connection. They showed that if the sources are correlated, the players can achieve scores that would be impossible if the sources were truly independent. This allows scientists to certify whether the "dice" in a network are truly independent or if there's a secret link between them.

As a final trick, the team applied these findings to create a new type of rule based on "entropy," which is a measure of how much information or randomness is in the system. They derived a specific inequality that limits how well two people can play the game if they only have a tiny, limited amount of shared randomness. This gives scientists a precise tool to measure exactly how much "secret coordination" is needed to mimic quantum behavior. In short, this paper maps out the jagged, complex landscape of classical games when the players are stripped of their unlimited shared randomness, providing new, curved tools to spot when nature is truly playing by quantum rules.

Technical Summary: Playing Nonlocal Games with Little to No Shared Randomness

Problem Statement
Bell nonlocality is a cornerstone of quantum information theory, distinguishing quantum correlations from those explainable by local-hidden-variable (LHV) models. In standard Bell scenarios, classical correlations are typically modeled assuming "free" shared randomness, which renders the set of achievable correlations convex and characterizable by linear Bell inequalities. However, in practical settings, agents may have limited or no access to shared randomness. The authors investigate how restricting the amount of shared randomness (or relaxing the assumption of source independence in networks) fundamentally alters the structure of the classical correlation set. Specifically, they address the fact that without shared randomness, the classical set becomes nonconvex, rendering standard linear Bell inequalities insufficient for a tight characterization.

Methodology
The paper employs a combination of analytical derivation, numerical optimization, and information-theoretic bounds to characterize classical correlations under resource constraints:

Bipartite Scenarios (No Shared Randomness): For the minimal 2-2-2 scenario (two parties, two inputs, two outputs), the authors analyze the set of correlations achievable when the shared random variable $\lambda$ has a cardinality $|\Lambda|=1$ . Instead of relying on single linear inequalities, they evaluate the simultaneous feasibility of multiple linear Bell functionals (specifically the four facets of the local polytope: $A, B, C, D$ , and an auxiliary function $E$ ). They utilize Karush-Kuhn-Tucker (KKT) conditions to derive analytical boundaries for these joint feasible regions.
Quantum Networks (Correlated Sources): The authors extend their analysis to multi-source quantum networks, relaxing the standard assumption that sources are mutually independent. They define a metric, $M_{n,k}$ , based on the variational distance between the joint distribution of source variables and the product of their marginal distributions. This metric quantifies the degree of correlation between sources.
Inequality Construction: Using the constraints derived for the bipartite case, they construct nonlinear inequalities for network scenarios. These inequalities are designed to be violated by quantum correlations even when classical models are allowed to have correlated sources, provided the correlation does not exceed a certain threshold.
Entropic Application: By relating the variational distance metric to the mutual information (and thus entropy) of the shared randomness via Pinsker's inequality, they derive an entropic Bell inequality for the bipartite scenario with limited shared randomness.

Key Contributions and Results

Characterization of Nonconvex Sets: The authors demonstrate that for $|\Lambda|=1$ $∣Λ∣ = 1$ (no shared randomness), the set of classical correlations is nonconvex. They show that while any single linear Bell expression can be maximized classically without shared randomness, the simultaneous evaluation of multiple Bell functions reveals non-trivial boundaries.
- For pairs of functions like $(A, E)$ , they derive explicit analytical boundaries (Eqs. 8 and 9) that differ from the unrestricted classical region.
- For triples $(A, B, C)$ , they provide numerical heatmaps of the feasible region and derive an analytical form for the maximal value of one function given the other two (Eq. 13).
- They identify a specific algebraic constraint (Eq. 15) that must be satisfied by any strategy without shared randomness involving all four Bell functions.
Witnessing Shared Randomness: The simultaneous evaluation of as few as three linear Bell functions is shown to be sufficient to witness the presence of shared randomness. Any observed behavior falling outside the derived nonconvex feasible region implies the existence of genuine shared randomness.
Network Inequalities with Correlated Sources: The paper introduces modified nonlinear network inequalities (Eq. 22) that account for source dependence characterized by $M_{n,k}$ $M_{n, k}$ . These inequalities generalize standard network inequalities (like those for star networks) and allow for the certification of source dependence.
- They prove that quantum violations of these inequalities can occur even if sources are correlated, provided the correlation strength (measured by $M_{n,k}$ ) is below a specific threshold determined by the quantum parameter $V$ (Eq. 24).
Entropic Bell Inequality: As a direct application, the authors derive a new entropic Bell inequality (Eq. 27) for the bipartite scenario. This inequality bounds the correlations achievable when the shared randomness is limited by an entropy $H(S)$ , incorporating the bound $M \le \sqrt{2 \ln 2 H(S)}$ .

Significance and Claims
The paper claims to provide a refined understanding of the structural limitations of classical models in Bell scenarios when shared randomness is restricted. By moving beyond single linear inequalities to the simultaneous analysis of multiple functionals, the authors offer a method to detect shared randomness that is more sensitive than traditional approaches.

In the context of quantum networks, the work relaxes the strict independence assumption, offering a framework to distinguish between quantum nonlocality and classical correlations arising from dependent sources. The derived entropic inequality is presented as a new tool for bounding classical correlations in scenarios where the entropy of the shared resource is a known constraint. The authors suggest that their methodology of simultaneously considering multiple linear Bell functions could be extended to broader contexts, including $n$ -party scenarios and different combinations of Bell functions, to further explore the relationship between the number of constraints and the classical dimension required to span the feasible region.

More like this