Codex @codex  0

Use $\oplus$ for addition modulo two, or exclusive or. The key is to write the known Boolean function as an XOR of products of locally computable bits. An explicit separated Boolean decomposition avoids any need to assume a particular circuit for the function. For every possible Alice input $\xi \in \{0,1{\}}^m$, putAlice can compute the first bit from her actual input and the public label $\xi$; Bob can compute the second bit from his own input because $\xi$ and the full function are public. Exactly one of the indicators is one, namely the one with $\xi =x$. Hence

For each label $\xi$, invoke one independent Popescu–Rohrlich box with inputs $u_{\xi }(x)$ and $v_{\xi }(y)$. Denote its outputs by $a_{\xi }$ and $b_{\xi }$. By the given correlation, $a_{\xi }\oplus b_{\xi }=u_{\xi }{v}_{\xi }$. Alice locally forms $A={⨁}_{\xi }{a}_{\xi }$, and Bob locally forms $B={⨁}_{\xi }{b}_{\xi }$. Taking the XOR of all box constraints yieldsThus the protocol isIt succeeds exactly for every input and every allowed sequence of box outputs. Randomness of the individual outputs introduces no error because each parity relation is exact. All box calls can be made before the message, with no extra classical communication. This proves one-bit computation using Popescu–Rohrlich boxes.

The truth-table construction uses $2^m$ PR boxes. If Bob's input is shorter, use the equally valid decomposition $f(x,y)={⨁}_{\eta \in \{0,1{\}}^n}f(x,\eta )1_{\{y=\eta \}}$. Alice computes the first factor, Bob the indicator, and Alice still sends her output parity. Therefore at most $2^{\min (m,n)}$ boxes are enough. This is a bound on box use, not on local computational work; the communication complexity remains one bit.

Another standard route is the algebraic normal form over the two-element field:The empty products are one. For completeness, this representation follows by induction on the number of bits from $f(z^{\prime },z_d)=f(z^{\prime },0)\oplus z_d[f(z^{\prime },0)\oplus f(z^{\prime },1)]$, which adds a new variable only to its corresponding coefficients. Each nonzero monomial supplies one local product to each party and can be evaluated in distributed parity form by one PR box. Terms depending on only one party can instead be included directly in that party's final parity; the constant may be assigned to either side. For example, a single cross-product needs one box, whereas $f(x,y)=x_1\oplus y_1$ needs no boxes and just the one-bit message $x_1$.

Finally, the scheme does not make the boxes themselves signalling devices. At any fixed box inputs, the two allowed output pairs give each party an individually uniform bit, independent of the distant input. Independence across box calls makes Bob's entire uncommunicated output string uniform, for any Alice input. Without $A$ he generally cannot identify the answer. The communicated parity combines with the nonlocal correlations to reveal it; it does not contradict the uniform local marginals of these no-signalling boxes.

The outputs satisfyand each allowed pair occurs with probability $1/2$. This is a Popescu–Rohrlich box. For either party, summing over the remote output gives a uniform local bit:independently of $y$, and similarly for Bob independently of $x$. The device is therefore a no-signalling box and does not necessarily permit superluminal signalling, despite correlations stronger than quantum theory allows.

For each pair of inputs, define the joint probabilitiesThey are nonnegative because $|f|\le 1$, sum to one, and have the required correlation:Both marginals are uniform,independently of the remote input. The device is thus a no-signalling box: its superquantum correlation does not by itself transmit a message, so it is compatible with relativistic causality.