What is the relationship between the Toffoli gate and the Popescu-Rohrlich box?

Question

Background

The Toffoli gate is a 3-input, 3-output classical logic gate. It sends $(x, y, a)$ to $(x, y, a \oplus (x \cdot y))$. It is significant in that it is universal for reversible (classical) computation.

The Popescu-Rohrlich box is the simplest example of a non-signaling correlation. It takes a pair of inputs $(x, y)$ and outputs $(a, b)$ satisfying $x \cdot y = a \oplus b$ such that $a$ and $b$ are both uniform random variables. It is universal for a certain class of (but not all) non-signaling correlations.

To my eye, these two objects look extremely similar, especially if we augment the PR box by having it output $(x, y, a, b) = (x, y, a, a \oplus (x \cdot y))$. This 2-input, 4-output PR box "is" the 3-input, 3-output Toffoli gate but with the third input replaced by a random output. But I've been unable to locate any references that relate them.

Question

What is the relationship between the Toffoli gate and the Popescu-Rohrlich box? Is there something like a correspondence between reversible classical circuits and (a certain class of?) non-signaling correlations that maps one to the other?

Observations

1. Specifying a non-signaling correlation requires not just a function but also an assignment of each input and output to a party that controls it. A PR box is no longer non-signaling if we allow Alice to enter both inputs and Bob to read both outputs. Or in our "augmented" PR-box, if Alice inputs $x$, she must also be the one who reads the copy of $x$. So it seems nontrivial to determine, for a general circuit (with some inputs possibly replaced by random outputs), all the ways inputs and outputs can be assigned to parties such that communication is not possible.

2. We can apply the above procedure any logic gate, including irreversible ones. For instance, we can take AND and replace one of the inputs by a random output, and get a function one input $x$ and a pair $(a, x \cdot a)$ where $a$ is a uniform random variable. However, $x \cdot a$ is $0$ conditioned on $x = 0$, so the only way this can be non-signaling is if Alice, who inputs $x$, receives $x \cdot a$. But this procedure can already be reproduced classically with a shared source of randomness. So I would expect that including irreversible gates does not expand the class of non-signaling correlations one can construct.

Answer 1

A natural way to relate Toffoli gates and PR boxes is to see them both as representations of the AND function of two binary inputs, but in different ways. The connection with the AND function is evident and clearly acknowledged by the question, but I would express it in a slightly different way:

1. The Toffoli gate is of course the natural way of representing AND as a reversible function. It follows the usual pattern of representing an arbitrary function $f:\{0,1\}^n\rightarrow\{0,1\}$ reversibly as $|x,a\rangle \mapsto |x,a\oplus f(x)\rangle$.

2. The PR box can be seen as a distributed form of the AND function. The output of a PR box on input $(x,y)$ can be expressed as $(\text{AND}(x,y)\oplus a, a)$, or equivalently as $(a,\text{AND}(x,y)\oplus a)$, where $a\in\{0,1\}$ is a uniformly generated random bit. The output of the PR box is therefore either a perfectly correlated or perfectly anti-correlated pair of random bits, depending on whether the AND of the inputs is 0 or 1 respectively. This is interesting because Alice and Bob collectively know the output of the AND function (which they can obtain by computing the XOR of their output bits), while individually they have no information at all about this value.

The idea that the PR box effectively computes the AND function in this distributed way is a key idea in Wim van Dam's proof that communication complexity becomes trivial in the presence of PR boxes:

Wim van Dam. Implausible consequences of superstrong nonlocality. Natural Computing 12(1): 9-12, 2013.