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

13

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(xy))

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)xy=abab

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(xy))

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. xx

  2. x(a,xa)axa0x=0xxa. 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ć.

Evan Jenkins
źródło

Odpowiedzi:

7

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{0,1}|x,a|x,af(x)

  2. (x,y)(AND(x,y)a,a)(a,AND(x,y)a)a{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.

John Watrous
źródło