Finite Nonsignalling Resources Suffice to Simulate Entangled Qubits

The paper in detail

With \(c=\cos2\theta\), \(s=\sin2\theta\) and \(T=\operatorname{diag}(s,-s,1)\), the target statistics are \(P_\theta(\alpha,\beta|x,y)=\tfrac14[1+\alpha cx_z+\beta cy_z+\alpha\beta\,x^{\mathsf T}Ty]\) for Bloch directions \(x,y\). A known decomposition writes \(P_\theta=cP_L+(1-c)P_N\), where \(P_L\) is local and \(P_N\) has uniform marginals and correlator \(C_N(x,y)=\int a_x(\lambda)b_y(\lambda)\,\nu_x(d\lambda)\). Here \(a_x=\operatorname{sgn}(Tx\cdot\lambda)\), \(b_y=\operatorname{sgn}(y\cdot\lambda)\), and \(\nu_x\) has density \(f_x\propto[|Tx\cdot\lambda|-c|\lambda_z|]_+\) on the sphere. Earlier protocols had Alice send the sampled \(\lambda\) to Bob, which is communication.

The new step replaces that message with a finite list. Before inputs arrive, both parties draw one direction uniformly in each of \(m\) cells of a fixed partition and one more over the whole sphere. Alice splits \(f_x\) into a piecewise-constant lower envelope and a residual bounded by 1, and with local coins picks one index \(I\). The global candidate is taken with probability equal to the residual at that point, otherwise a cell is chosen with weight proportional to its envelope mass. Averaged over the shared list, the chosen direction has exactly the distribution \(\nu_x\), even though each run uses only one of finitely many candidates.

Bob does not know \(I\), so he computes his sign bit \(z_j\) for every candidate. An index box takes Alice’s \(I\) and Bob’s whole table and returns individually fair bits \(u,v\) with \(u\oplus v=z_I\). It is built from \(N-1\) parallel PR boxes and one shared bit. Alice outputs \((-1)^{u\oplus d}\), with \(d\) her own sign bit, and Bob outputs \((-1)^v\), so \(AB=a_x(\omega_I)b_y(\omega_I)\) and averaging reproduces \(C_N\). The partition must keep \(f_x\) within \(1/2\) of its reference value in every cell for every \(x\); an explicit grid of \(4n_\theta^2\) paired cells with \(n_\theta=\lceil\sqrt2\pi\cot^2\theta\rceil\) achieves this, which fixes the budget.

Mixed states follow by sampling a pure-state component with shared randomness, and binary POVMs by local post-processing of a projective outcome, at no extra PR cost. A single budget \(K(\theta_0)\) covers all \(\theta\in[\theta_0,\pi/4)\). At the endpoints, product states need no box and the maximally entangled state needs one. A stability bound covers sampling errors, assuming exact sign evaluation.

Transferable methods

1. Exact sampling from an input-dependent density using a fixed shared list

   When one party must draw from a distribution that depends on its private input, while the other must react to the draw, prepare a list of candidates in advance and let the first party choose an index with local coins. Averaging over the list, not over each run, then reproduces the target distribution exactly.

   Partition the sphere into cells \(C_j\) with masses \(\mu(C_j)\) and references \(v_j\), such that \(|f_x(\lambda)-f_x(v_j)|\le\tfrac12\) on \(C_j\) for all \(x\). Set \(\gamma_j(x)=[f_x(v_j)-\tfrac12]_+\), the envelope \(\underline f_x=\sum_j\gamma_j\mathbf 1_{C_j}\le f_x\), and the residual \(h_x=f_x-\underline f_x\in[0,1]\).

   Draw \(\Lambda_j\) uniform in \(C_j\) and \(\Lambda_N\) uniform on the sphere. Choose \(I=N\) with probability \(h_x(\omega_N)\), otherwise \(I=j\) with probability \(w_j/W_x\), where \(w_j=\mu(C_j)\gamma_j\). Because \(\int(1-h_x)\,d\mu=\int\underline f_x\,d\mu=W_x\), \(P(I=j)=w_j\). The cell candidates then contribute density \(\sum_jw_j\mathbf 1_{C_j}/\mu(C_j)=\underline f_x\) and the global one \(h_x\), for a total of \(f_x\).

   Editorial check: Monte Carlo over \(2\times10^6\) points at \(\theta=\pi/8\) gives \(\int f_x\,d\mu=1.000\pm0.001\) for random \(x\), with maxima up to about 4. The budget formula gives \(K=2704\) at \(\theta=\pi/8\) against the bound \(128\cot^4\theta\approx4348\), with mean usage \((1-\cos2\theta)K\approx792\).

   How to reuse it

   Whenever a protocol needs a sample whose distribution depends on one party’s input but whose value must stay hidden from the other (distributed sampling, communication-free simulation, private randomness extraction), try a fixed-length shared list plus local selection. It needs a density that is uniformly continuous in both arguments, so that a finite partition keeps the residual bounded.

2. A random-access index box from parallel PR boxes

   An index box lets Alice’s index pick an entry of Bob’s table as the parity of their outputs, without either learning the other’s data. Each PR box fires its correlation only on Alice’s chosen position, and differences against a reference entry make the parity come out right.

   For \(j<N\), feed PR box \(j\) with \(a_j=\mathbf 1\{I=j\}\) and \(b_j=z_j\oplus z_N\); it returns \(u_j\oplus v_j=a_jb_j\). With a shared fair bit \(H\), set \(u=H\oplus\bigoplus_ju_j\) and \(v=H\oplus z_N\oplus\bigoplus_jv_j\).

   Editorial derivation: \(u\oplus v=z_N\oplus\bigoplus_ja_jb_j\). If \(I<N\), only \(a_I=1\), giving \(z_N\oplus z_I\oplus z_N=z_I\); if \(I=N\), every \(a_j=0\) and the parity is \(z_N\). Each output alone is uniform because of \(H\) and the PR marginals. An exhaustive check over all inputs for \(N=5\) confirms \(u\oplus v=z_I\).

   How to reuse it

   Any task needing a nonlocal random-access correlation, such as oblivious-transfer-like primitives, distributed Boolean functions or communication-complexity reductions, can use this wiring at \(N-1\) PR boxes for an \(N\)-entry table. The authors prove this count is optimal for the full input domain of the index box.

Source: Local–nonlocal decomposition (Eqs. 6–9); Steps 1–4 of the nonlocal branch (Eqs. 10–17); PR implementation and budget (Eqs. 18–20); SM Secs. S2–S4. Based on the linked paper version. Derivations marked as editorial, and suggested uses in other problems, are editorial guidance rather than results of the paper.

Context & limitations

Why it matters. It separates the continuity of quantum correlations from the alphabet of the resources needed to simulate them: continuous data can live in shared randomness and local processing, while nonlocal coordination needs only finitely many binary boxes. The finite-selection lemma behind it applies to any correlation family with a continuous distributed-sampling representation.

Limitations. The budget is explicit but not optimal, and it diverges as \(\theta\to0\) (worst case \(O(\theta^{-4})\), mean \(O(\theta^{-2})\)); the authors stress that this reflects the construction, not a proven necessity. Whether one finite budget serves all states, and the optimal PR cost, remain open. Shared randomness is continuous and local processing is exact; finite-precision implementations are only partly analysed. Multi-outcome POVMs are not covered.

Description based on the full text of the linked arXiv version, read 2026-10-26; equations follow the paper’s notation.