We show that some tripartite quantum correlations are inexplicable by any causal theory involving bipartite nonclassical common causes and unlimited shared randomness. This constitutes a device-independent proof that nature’s nonlocality is fundamentally at least tripartite in every conceivable physical theory—no matter how exotic. To formalize this claim, we are compelled to substitute Svetlichny’s historical definition of genuine tripartite nonlocality with a novel theory-agnostic definition tied to the framework of local operations and shared randomness. A companion article by Coiteux-Roy et al. generalizes these concepts to any $N\ge 3$ number of parties, providing experimentally amenable device-independent inequality constraints along with quantum correlations violating them, thereby certifying that nature’s nonlocality must be boundlessly multipartite.

We introduce the class of genuinely local operations and shared randomness multipartite nonlocal correlations, that is, correlations between $N$ parties that cannot be obtained from unlimited shared randomness supplemented by any composition of $(N-1)$-shared causal generalized probabilistic theory (GPT) resources. We then show that noisy $N$-partite Greenberger-Horne-Zeilinger (GHZ) quantum states as well as the three-partite $W$ quantum state can produce such correlations. This proves, if the operational predictions of quantum theory are correct, that nature's nonlocality must be boundlessly multipartite in any causal GPT. We develop a computational method which certifies that a noisy $N=3$ GHZ quantum state with fidelity $85\%$ satisfies this property, making an experimental demonstration of our results within reach. We provide our definition and contrast it with preexisting notions of genuine multipartite nonlocality. This work extends a more compact parallel Letter [X. Coiteux-Roy et al., No Bipartite-Nonlocal Causal Theory Can Explain Nature's Correlations, Phys. Rev. Lett. 127, 200401 (2021)] on the same subject and provides all the required technical proofs.

Quantum theory predicts the existence of genuinely tripartite-entangled states, which cannot be obtained from local operations over any bipartite-entangled states and unlimited shared randomness. Some of us recently proved that this feature is a fundamental signature of quantum theory. The state $|{\mathrm{GHZ}}_3⟩=(|000⟩+|111⟩)/\sqrt{2}$ gives rise to tripartite quantum correlations that cannot be explained by any causal theory limited to bipartite nonclassical common causes of any kind (generalizing entanglement) assisted with unlimited shared randomness. Hence, any conceivable physical theory that would reproduce quantum predictions will necessarily include genuinely tripartite resources. In this Letter, we verify that such tripartite correlations are experimentally achievable. We derive a new device-independent witness capable of falsifying causal theories wherein nonclassical resources are merely bipartite. Using a high-performance photonic $|{\mathrm{GHZ}}_3⟩$ state with fidelities of $0.9741\pm 0.002$, we provide a clear experimental violation of that witness by more than 26.3 standard deviations, under the locality and fair sampling assumption. We generalize our Letter to the $|{\mathrm{GHZ}}_4⟩$ state, obtaining correlations that cannot be explained by any causal theory limited to tripartite nonclassical common causes assisted with unlimited shared randomness.

We give an almost complete characterization of the hardness of c-coloring χ-chromatic graphs with distributed algorithms, for a wide range of models of distributed computing. In particular, we show that these problems do not admit any distributed quantum advantage. To do that: We give a new distributed algorithm that finds a c-coloring in χ-chromatic graphs in Õ(n^1/α) rounds, with α = ⌊c−1/χ − 1⌋. We prove that any distributed algorithm for this problem requires Ω(n^1/α) rounds. Our upper bound holds in the classical, deterministic LOCAL model, while the near-matching lower bound holds in the non-signaling model. This model, introduced by Arfaoui and Fraigniaud in 2014, captures all models of distributed graph algorithms that obey physical causality; this includes not only classical deterministic LOCAL and randomized LOCAL but also quantum-LOCAL, even with a pre-shared quantum state. We also show that similar arguments can be used to prove that, e.g., 3-coloring 2-dimensional grids or c-coloring trees remain hard problems even for the non-signaling model, and in particular do not admit any quantum advantage. Our lower-bound arguments are purely graph-theoretic at heart; no background on quantum information theory is needed to establish the proofs.

A common starting point of traditional quantum algorithm design is the notion of a universal quantum computer with a scalable number of qubits. This convenient abstraction mirrors classical computations manipulating bits. It allows for a device-independent development of algorithmic primitives. Here we argue that an alternative approach centered on the physical setup can yield great benefits. As an example, we consider hybrid qubit-oscillator systems with linear optics operations augmented by certain qubit-controlled Gaussian unitaries. The continuous variable Fourier transform and certain arithmetic operations have native realizations in such systems. We put this to algorithmic use and give a polynomial-time quantum factoring algorithm which uses only one qubit and three oscillators, independent of the number being factored.