= One-bit computation using Popescu–Rohrlich boxes
{title2=$f(x,y)=A\oplus B$}
Take a <separated Boolean decomposition> $f(x,y)=\bigoplus_{\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=\bigoplus_\ell a_\ell$, Bob forms $B=\bigoplus_\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.
Back to article page
