Jaki jest związek między bramą Toffoli a skrzynią Popescu-Rohrlich?

tło

Brama Toffoli jest klasyczną bramką logiczną z 3 wejściami i 3 wyjściami. Wysyła do ( x , y , a ⊕ ( x ⋅ y ) ) . Jest to znaczące, ponieważ jest uniwersalne dla obliczeń odwracalnych (klasycznych).$(x, y, a)$$(x, y, a \oplus (x \cdot y))$

Ramka Popescu-Rohrlicha jest najprostszym przykładem korelacji niesygnalizacyjnej. Wymaga pary danych wejściowych i danych wyjściowych ( a , b ) spełniających x ⋅ y = a ⊕ b, tak że a i b są równymi zmiennymi losowymi. Jest uniwersalny dla pewnej klasy ( ale nie wszystkich ) korelacji niesygnalizacyjnych.$(x, y)$$(a, b)$$x \cdot y = a \oplus b$$a$$b$

Moim zdaniem te dwa obiekty wyglądają niezwykle podobnie, szczególnie jeśli powiększamy pole PR, uzyskując dane wyjściowe . Ta skrzynka PR z 2 wejściami i 4 wyjściami „jest” bramką Toffoli z 3 wejściami i 3 wyjściami, ale z trzecim wejściem zastąpiono wyjście losowe. Ale nie udało mi się znaleźć żadnych odnośników, które ich dotyczą.$(x, y, a, b) = (x, y, a, a \oplus (x \cdot y))$

Pytanie

Jaki jest związek między bramą Toffoli a skrzynią Popescu-Rohrlich? Czy istnieje coś w rodzaju korelacji między odwracalnymi obwodami klasycznymi a (pewną klasą?) Korelacjami niesygnalizacyjnymi, które odwzorowują jeden na drugi?

Spostrzeżenia

1. $x$$x$

2. $x$$(a, x \cdot a)$$a$$x \cdot a$$0$$x = 0$$x$$x \cdot a$. Ale tę procedurę można już klasycznie odtworzyć ze wspólnym źródłem losowości. Oczekiwałbym więc, że włączenie nieodwracalnych bram nie rozszerzy klasy korelacji niesygnalizacyjnych, jakie można zbudować.

Naturalnym sposobem na powiązanie bramek Toffoli i skrzynek PR jest postrzeganie ich jako reprezentacji funkcji AND dwóch wejść binarnych, ale na różne sposoby. Związek z funkcją AND jest oczywisty i wyraźnie potwierdzony przez pytanie, ale wyraziłbym to nieco inaczej:

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\}$jest równomiernie wygenerowanym bitem losowym. Wyjście pola PR jest zatem albo idealnie skorelowaną, albo idealnie skorelowaną parą losowych bitów, w zależności od tego, czy AND na wejściach wynosi odpowiednio 0 czy 1. Jest to interesujące, ponieważ Alice i Bob wspólnie znają dane wyjściowe funkcji AND (którą mogą uzyskać obliczając XOR swoich bitów wyjściowych), podczas gdy indywidualnie nie mają żadnych informacji o tej wartości.

Pomysł, że skrzynka PR skutecznie oblicza funkcję AND w ten rozproszony sposób, jest kluczową ideą w dowodzie Wima van Dam, że złożoność komunikacji staje się trywialna w obecności skrzynek PR:

Wim van Dam. Nieprawdopodobne konsekwencje super mocnej nielokalności. Natural Computing 12 (1): 9-12, 2013.