¿Cuál es la relación entre la puerta Toffoli y la caja Popescu-Rohrlich?

Antecedentes

La puerta Toffoli es una puerta lógica clásica de 3 entradas y 3 salidas. Envía a ( x , y , a ⊕ ( x ⋅ y ) ) . Es significativo porque es universal para el cálculo reversible (clásico).$(x, y, a)$$(x, y, a \oplus (x \cdot y))$

El cuadro de Popescu-Rohrlich es el ejemplo más simple de una correlación sin señalización. Se necesita un par de entradas y salidas ( a , b ) que satisfagan x ⋅ y = a ⊕ b de manera que a y b sean variables aleatorias uniformes. Es universal para una cierta clase de ( pero no todas ) correlaciones sin señalización.$(x, y)$$(a, b)$$x \cdot y = a \oplus b$$a$$b$

En mi opinión, estos dos objetos se ven extremadamente similares, especialmente si aumentamos el cuadro PR al hacer que salga . Esta caja PR de 2 entradas y 4 salidas "es" la puerta Toffoli de 3 entradas y 3 salidas, pero con la tercera entrada reemplazada por una salida aleatoria. Pero no he podido localizar ninguna referencia que los relacione.$(x, y, a, b) = (x, y, a, a \oplus (x \cdot y))$

Pregunta

¿Cuál es la relación entre la puerta Toffoli y la caja Popescu-Rohrlich? ¿Hay algo así como una correspondencia entre los circuitos clásicos reversibles y (una cierta clase de) correlaciones sin señalización que se correlacionan entre sí?

Observaciones

1. $x$$x$

2. $x$$(a, x \cdot a)$$a$$x \cdot a$$0$$x = 0$$x$$x \cdot a$. Pero este procedimiento ya puede reproducirse clásicamente con una fuente compartida de aleatoriedad. Por lo tanto, esperaría que incluir puertas irreversibles no expanda la clase de correlaciones sin señalización que uno puede construir.

Una forma natural de relacionar las compuertas Toffoli y los cuadros PR es verlos a ambos como representaciones de la función AND de dos entradas binarias, pero de diferentes maneras. La conexión con la función AND es evidente y claramente reconocida por la pregunta, pero lo expresaría de una manera ligeramente diferente:

1. $f:\{0,1\}^n\rightarrow\{0,1\}$$|x,a\rangle \mapsto |x,a\oplus f(x)\rangle$

2. $(x,y)$$(\text{AND}(x,y)\oplus a, a)$$(a,\text{AND}(x,y)\oplus a)$$a\in\{0,1\}$es un bit aleatorio generado uniformemente. La salida de la caja PR es, por lo tanto, un par de bits aleatorios perfectamente correlacionados o perfectamente correlacionados, dependiendo de si el AND de las entradas es 0 o 1 respectivamente. Esto es interesante porque Alice y Bob conocen colectivamente la salida de la función AND (que pueden obtener calculando el XOR de sus bits de salida), mientras que individualmente no tienen ninguna información sobre este valor.

La idea de que el cuadro PR calcule efectivamente la función AND de esta manera distribuida es una idea clave en la prueba de Wim van Dam de que la complejidad de la comunicación se vuelve trivial en presencia de cuadros PR:

Wim van Dam. Implausibles consecuencias de la no localidad superfuerte. Computación natural 12 (1): 9-12, 2013.