On random classical marginal problems with applications to quantum information theory

This paper investigates random instances of the classical marginal problem by encoding them into graphs with fixed vertex and random edge distributions, providing probability estimates for the existence of joint distributions and analyzing the volume ratios between local and non-signaling polytopes in CHSH and Bell-Wigner scenarios to inform quantum information theory.

The Gist

Imagine you are a detective trying to solve a mystery involving a group of friends who are all telling you about their relationships with each other.

The Setup: The "Friendship" Graph

Let's say you have a group of people (vertices) and you know how each pair of friends gets along (edges).

• The Local Rules (Classical): In a normal, "local" world, if Alice and Bob are friends, and Bob and Charlie are friends, there must be a consistent story about how Alice, Bob, and Charlie all interact together. Their stories must fit into one single, coherent reality.
• The "Spooky" Rules (Non-Signaling): In the quantum world (or a "spooky" world), Alice and Bob might have a relationship, and Bob and Charlie might have a relationship, but there might be no single story that explains all three at once. They are compatible in pairs, but impossible as a trio. This is like "quantum entanglement" or "non-locality."

The paper asks a simple but deep question: If we randomly pick how these pairs get along, how often is it possible to find a single, consistent story for the whole group?

The Analogy: The Puzzle Box

Think of the "Local Rules" as a perfectly fitting puzzle. Every piece (the relationship between two people) must snap together to form a complete picture.
Think of the "Non-Signaling Rules" as a box of loose puzzle pieces. You know that Piece A fits with Piece B, and Piece B fits with Piece C. But you haven't checked if A, B, and C can all exist in the same box without breaking the rules of physics.

The authors are studying the volume (the size) of these two boxes:

1. The Local Box: Only contains puzzles that actually fit together perfectly.
2. The Non-Signaling Box: Contains all possible pairs that look like they could fit, even if they don't actually form a whole picture.

The paper calculates the ratio: If you grab a random puzzle from the big "Non-Signaling" box, what are the odds it actually belongs in the smaller "Local" box?

The "Tightness" of the Rules (The Fall-Off Value)

The authors discovered something fascinating about how these rules change based on the "marginals."

• Marginals: Imagine you fix the "personality" of each person. For example, "Alice is 50% happy, 50% sad."
• The Discovery: If the personalities are very extreme (e.g., Alice is 100% happy), it's very easy to find a consistent story. The Local and Non-Signaling boxes are almost the same size.
• The "Fall-Off": But as the personalities become more "balanced" (e.g., 50/50), the rules get tighter. Suddenly, many of those loose puzzle pieces that looked okay in pairs turn out to be impossible to fit together. The "Local" box shrinks rapidly compared to the "Non-Signaling" box.

The authors define a "Fall-Off Value": This is the tipping point. It's the specific level of "balance" where the probability of finding a consistent story stops being constant and starts dropping.

The Secret Code: Tree Width

Here is the most beautiful part of the paper. The authors found a hidden code that predicts exactly when this "Fall-Off" happens.

They looked at the shape of the group's connections (the graph):

• Trees (No loops): If your friends are connected in a line or a branching tree (no one is part of a closed circle), the rules are loose. You can almost always find a consistent story. The "Fall-Off" happens at the very end.
• Loops (Triangles, Squares): If your friends form a circle (Alice-Bob-Charlie-Alice), the rules get tighter.
• The Formula: The authors conjecture (and prove for many cases) that the "Fall-Off Value" is simply 1 divided by (The Complexity of the Shape + 1).

Think of "Tree Width" as the "Tangle Factor":

• A simple line has a Tangle Factor of 1.
• A triangle has a Tangle Factor of 2.
• A complex web has a higher Tangle Factor.

The Rule: The more "tangled" the group is, the sooner the consistent stories disappear as you move toward balanced personalities.

• For a Triangle (Tangle 2), the tipping point is 1/3.
• For a Square (Tangle 2), the tipping point is also 1/3.
• For a complete mess of 4 people (Tangle 3), the tipping point is 1/4.

Why Does This Matter? (The Quantum Connection)

This isn't just about math puzzles. It's about Quantum Mechanics.

• Classical World: Everything has a pre-existing story (Local).
• Quantum World: Sometimes, the story only exists when you look at it (Non-Local).

The paper helps us understand how "quantum" a system is. If you randomly generate a scenario where people (or particles) interact, how likely is it that they are behaving in a "spooky" quantum way rather than a normal classical way?

The authors found that the "spookiest" scenarios (where quantum behavior is most likely to appear) happen when the participants are perfectly balanced (50/50). If you fix their personalities to be extreme, they act more classically.

Summary in One Sentence

This paper uses geometry to show that the more "tangled" a group of relationships is, the harder it becomes to find a single consistent story for them, and it gives us a precise mathematical formula to predict exactly when that consistency breaks down.

Technical Summary

1. Problem Statement

The paper investigates the classical marginal problem within the context of quantum information theory. Specifically, it addresses the question of compatibility: given a graph $G=(V, E)$ where each vertex $v$ is assigned a fixed univariate probability distribution (marginal) $p_v$, and each edge $e=(u,v)$ is assigned a random bivariate distribution consistent with the vertex marginals, what is the probability that these edge distributions are compatible?

Compatibility means there exists a global joint probability distribution over all vertices such that the given edge distributions are its marginals.

In the language of quantum information, this problem maps to the relationship between:

• Local Polytope ($L$): The set of correlations explainable by local hidden variable models (classical strategies).
• Non-Signaling Polytope ($N$): The set of correlations satisfying the no-signaling principle (consistent with special relativity), which includes quantum and super-quantum correlations.

The authors study the volume ratio $\frac{\text{vol}(L)}{\text{vol}(N)}$ for specific "slices" of these polytopes where the single-site marginals are fixed. This ratio quantifies how "large" the set of classical correlations is relative to the set of all non-signaling correlations under specific constraints.

2. Methodology

The authors employ a multi-faceted approach combining convex geometry, combinatorial optimization, and probability theory:

• Graph Encoding: They encode the marginal problem using graphs. Vertices represent random variables (binary outcomes), and edges represent the bivariate distributions.
• Polytope Definitions:
  • Correlation Polytope ($L(G)$): Defined as the convex hull of deterministic strategies (extremal points). This corresponds to the set of compatible distributions.
  • Transportation Polytope ($N(G)$): Defined as the Cartesian product of local transportation polytopes for each edge. This corresponds to the set of non-signaling (compatible marginals) distributions.
• Slice Analysis: Instead of analyzing the full polytopes, they fix the vertex probabilities $p_v = t$ (symmetric case) or specific vectors (skewed case). This reduces the dimensionality, creating "slices" $L(t, G)$ and $N(t, G)$.
• Volume Computation:
  • They utilize the H-representation (inequalities) and V-representation (vertices) of these polytopes.
  • For small graphs, they explicitly calculate volumes by decomposing the polytopes into simpler geometric shapes (simplexes, pyramids).
  • They use Fourier-Motzkin elimination to derive inequalities for subgraphs from larger graphs (e.g., deriving $C_4$ from $K_4$).
  • They use the gluing technique to combine results from smaller graphs (like trees or cycles) to analyze larger structures.
• Random Sampling: The volume ratio is interpreted as the probability that a uniformly sampled point from the non-signaling slice $N(t, G)$ falls within the local slice $L(t, G)$.

3. Key Contributions

A. Exact Volume Ratios for Specific Graphs

The paper provides exact analytical formulas for the volume ratio $\rho(t) = \frac{\text{vol}(L(t, G))}{\text{vol}(N(t, G))}$ for several fundamental graphs:

1. Triangle Graph ($K_3$ / Bell-Wigner Scenario):
   • For symmetric marginals $p_i = t$, the ratio is constant at 1/2 for $t \in (0, 1/3]$.
   • It decreases for $t > 1/3$, reaching 1/3 at $t=1/2$.
2. Square Graph ($K_{2,2}$ / CHSH Scenario):
   • For symmetric marginals, the ratio is constant at 5/6 for $t \in (0, 1/3]$.
   • It decreases to 2/3 at $t=1/2$.
3. Cycle Graphs ($C_n$):
   • Generalized results for arbitrary cycles. The initial ratio is $1 - \frac{1}{(n-1)!}$.
   • As $n \to \infty$, the volume ratio approaches 1, indicating that for large cycles, the local and non-signaling sets become indistinguishable in terms of volume.
4. Complete Graph ($K_4$):
   • Calculated explicitly, showing a fall-off value of $1/4$ and an initial ratio of $5/36$.

B. The "Fall-off" Value ($\tau(G)$)

The authors define a critical parameter $\tau(G)$: the largest value of $t$ for which the volume ratio remains constant on the interval $(0, \tau)$.

• They observe that for trees, $\tau = 1/2$ (since $L=N$).
• For $K_3$ and $K_{2,2}$, $\tau = 1/3$.
• For $K_4$, $\tau = 1/4$.

C. The Treewidth Conjecture

Based on their calculations, the authors propose a fundamental conjecture linking the geometry of the problem to graph theory:
$$\tau(G) = \frac{1}{\text{tw}(G) + 1}$$
where $\text{tw}(G)$ is the treewidth of the graph.

• Proofs: They prove this conjecture for:
  • Forests (Treewidth 1): Trivial, as $\tau=1/2$.
  • Series-Parallel Graphs (Treewidth 2): They prove $\tau=1/3$ using odd-cycle inequalities.
• Support: The conjecture holds for $K_4$ (treewidth 3, $\tau=1/4$) and is supported by numerical data for $K_5$.

D. Operations on Graphs

The paper establishes how the volume ratio behaves under graph operations:

• Gluing: If two graphs are glued along a single vertex, the volume ratios multiply. If glued along an edge (forming a tree-like structure), the ratio remains that of the base graph.
• Edge Removal: Removing an edge from a graph increases (or keeps constant) the fall-off value $\tau$.

4. Key Results

• Non-Constant Ratios: The volume ratio is not uniform; it stays constant for small $t$ (near deterministic limits) and drops as $t$ approaches $1/2$ (maximal randomness).
• Maximal Contextuality: The probability of finding a contextual (non-local) correlation is highest when the marginals are fixed to $t=1/2$. For the CHSH game, fixing marginals to $t=1/2$ reduces the chance of a random non-signaling box being local to $2/3$ (meaning $1/3$ are non-local), whereas free marginals yield a much lower probability of non-locality ($1/17$).
• Inequalities: The paper details the specific Bell-type inequalities (facets) that cut into the non-signaling polytope to form the local polytope, showing exactly when they become "active" (restrictive) based on the parameter $t$.

5. Significance and Applications

• Quantum Foundations: The work provides a rigorous geometric understanding of the gap between classical, quantum, and non-signaling correlations. It quantifies "how classical" a scenario is under specific experimental constraints.
• Contextuality: It offers a probabilistic measure of contextuality. The results suggest that fixing marginals (a common experimental constraint) can significantly alter the likelihood of observing quantum advantages.
• Computational Complexity: The study highlights the difficulty of characterizing correlation polytopes for general graphs (NP-complete membership testing) but provides exact solutions for important subclasses (cycles, series-parallel).
• Future Directions: The paper suggests that the volume ratio could be used as a measure of non-contextuality, potentially linking to the "contextual fraction." It opens the door for analyzing larger contexts and higher-order correlations.

In summary, this paper bridges combinatorial optimization and quantum information theory by solving the random marginal problem for specific graph topologies, revealing a deep connection between the treewidth of a graph and the stability of classical correlations under random sampling.