Nonlocality for Generic Networks

Bell’s theorem shows that correlations created by a single entangled quantum state cannot be reproduced classically. Such correlations are called nonlocal. They are the elementary manifestation of a broader phenomenon called network nonlocality, where several entangled states shared in a network create network nonlocal correlations. In this Letter, we provide the first class of strategies producing nonlocal correlations in generic networks. In these strategies, called color matching (CM), any source takes a color at random or in superposition, where the colors are labels for a basis of the associated Hilbert space. A party (besides other things) checks if the color of neighboring sources match. We show that in a large class of networks without input, well-chosen quantum CM strategies result in nonlocal correlations that cannot be produced classically. For our construction, we introduce the graph theoretical concept of rigidity of classical strategies in networks, and using the Finner inequality, establish a deep connection between network nonlocality and graph theory. In particular, we establish a link between CM strategies and the graph coloring problem. This work is extended in a longer paper [M.-O. Renou, Phys. Rev. A 105, 022408 (2022)], where we introduce a second family of rigid strategies called token counting, leading to network nonlocality.

Figure 1

Four-party 1-2 network, source orientation, and illustration of some events of the decohered classical CM strategy leading to $P_{\text{color}}$. All outputs except the ambiguous $\chi$ give the color of the sources adjacent to a party. Hence, there exist only three patterns for the color of the sources for which all outputs are ambiguous, that are labeled by $t=1$, 2, and 3.

Figure 2

(a) Network nonlocality in bipartite source complete networks ${\mathcal{K}}_n$. The network is composed of $n$ parties and $m=(\genfrac{}{}{0ex}{}{n}{2})$ bipartite sources, such that each pair of parties share a source (here $n=5$, $m=10$). In Ref. [35], we introduce a quantum CM strategy with two colors in which $\mathcal{T}$ contains all tuples of colors which do not correspond to the cases $t=1$ and $t=2$ in the figure. Theorem 1 applied to the decohered classical strategy implies that any hypothetical classical simulation of the resulting distribution must assign colors to sources. Hence, assuming that all parties’ outputs are ambiguous, the unobserved classical hidden variable $t$ is well defined. This introduces new constraints, forming a linear program, which has no solution. (b) Network nonlocality in bipartite parties complete networks ${\mathcal{G}}_m$. The network is composed of $m$ sources and $n=(\genfrac{}{}{0ex}{}{m}{2})$ parties, such that every pair of sources has one common party (here $m=4$, $n=6$). In Ref. [35], we introduce a quantum CM strategy with $m$ colors. In this strategy, based on the graph coloring problem, each party checks if the color of adjacent sources match. Thus, when all parties find a noncolored output, the underlying graph (with parties being the edges) is properly colored (no adjacent sources have the same color). For example the left colored network is properly colored, while in the right colored network two parties with their red and yellow outputs can detect the nonproper coloring. As before, a well chosen set $\mathcal{T}$ allows us to prove nonlocality.