No-signalling box

A no-signalling box is a conditional probability distribution $P(x,y|a,b)$ whose marginal distribution for either party is independent of the other party's input. It can therefore exhibit correlations stronger than quantum correlations without transmitting information superluminally.

A Popescu–Rohrlich box is a bipartite no-signalling box attaining the algebraic maximum of the CHSH inequality.

Take a separated Boolean decomposition $f(x,y)={⨁}_{\ell }{u}_{\ell }(x)v_{\ell }(y)$. Feed $(u_{\ell },v_{\ell })$ to one independent PR box, obtaining outputs with $a_{\ell }\oplus b_{\ell }=u_{\ell }{v}_{\ell }$. Alice forms $A={⨁}_{\ell }{a}_{\ell }$, Bob forms $B={⨁}_{\ell }{b}_{\ell }$, and their parities satisfy $A\oplus B=f$. Sending the single bit $A$ lets Bob compute the answer with certainty. The truth-table decomposition needs at most $2^{\min (m,n)}$ boxes for input lengths $m,n$. Each box's local output is uniform, so Bob's uncommunicated output string carries no information about Alice's input; the final parity bit is essential for a general function depending on that input.