Какова связь между воротами Тоффоли и коробкой Попеску-Рорлиха?

Фон

Вентиль Toffoli - это классический логический вентиль с 3 входами и 3 выходами. Он отправляет в . Показательно, что он универсален для обратимых (классических) вычислений.$(x, y, a)$$(x, y, a \oplus (x \cdot y))$

Поле Popescu-Rohrlich является самым простым примером несигнальной корреляции. Требуется пара входов и выходов удовлетворяющих , так что и являются одинаковыми случайными переменными. Он универсален для определенного класса ( но не всех ) несигнальных корреляций.$(x, y)$$(a, b)$$x \cdot y = a \oplus b$$a$$b$

На мой взгляд, эти два объекта выглядят очень похожими, особенно если мы увеличиваем окно PR, выводя его . Этот PR-блок с 2-мя входами и 4-мя выходами «является» 3-входным вентилем Toffoli с 3-мя выходами, но третий вход заменен случайным выходом. Но я не смог найти какие-либо ссылки, которые их касаются.$(x, y, a, b) = (x, y, a, a \oplus (x \cdot y))$

Вопрос

Какова связь между воротами Тоффоли и коробкой Попеску-Рорлиха? Есть ли что-то вроде соответствия между обратимыми классическими схемами и (определенным классом?) Несигнальных корреляций, которые отображают одну на другую?

наблюдения

1. Определение не сигнальной корреляции требует не только функции, но и назначения каждого входа и выхода стороне, которая ее контролирует. Блок PR больше не будет сигнализировать, если мы позволим Алисе ввести оба входа, а Бобу прочитать оба выхода. Или в нашем «расширенном» PR-боксе, если Алиса вводит , она также должна быть той, кто читает копию . Таким образом, кажется нетривиальным определить для общей схемы (с некоторыми входами, возможно, замененными случайными выходами) все способы, которыми входы и выходы могут быть назначены сторонам так, что связь не возможна.$x$$x$

2. Мы можем применить описанную выше процедуру к любым логическим элементам, в том числе и необратимым. Например, мы можем взять AND и заменить один из входов случайным выходом, и получить функцию one input и пару где - это равномерная случайная величина. Тем не менее, равен условии , поэтому единственным способом, которым это может быть не сигналом, является то, что Алиса, которая вводит , получает . Но эта процедура уже может быть воспроизведена классически с общим источником случайности. Таким образом, я ожидаю, что включение необратимых гейтов не расширяет класс не сигнальных корреляций, которые можно построить.$x$$(a, x \cdot a)$$a$$x \cdot a$$0$$x = 0$$x$$x \cdot a$

Естественный способ связать логические блоки Toffoli и PR состоит в том, чтобы рассматривать их как представление функции AND двух двоичных входов, но по-разному. Связь с функцией AND очевидна и четко подтверждена этим вопросом, но я бы выразил это немного иначе:

1. Ворота Тофоли, конечно, являются естественным способом представления И как обратимой функции. Он следует обычной схеме представления произвольной функции обратимо в виде .$f:\{0,1\}^n\rightarrow\{0,1\}$$|x,a\rangle \mapsto |x,a\oplus f(x)\rangle$

2. Окно PR можно рассматривать как распределенную форму функции AND. Выходные данные PR-поля на входе могут быть выражены как или эквивалентно как , где - это случайно сгенерированный случайный бит. Таким образом, выходной сигнал блока PR представляет собой либо идеально коррелированную, либо идеально коррелированную пару случайных битов, в зависимости от того, равно ли И входов 0 или 1 соответственно. Это интересно, потому что Алиса и Боб вместе знают выходные данные функции AND (которую они могут получить, вычисляя XOR своих выходных битов), в то время как по отдельности они вообще не имеют никакой информации об этом значении.$(x,y)$$(\text{AND}(x,y)\oplus a, a)$$(a,\text{AND}(x,y)\oplus a)$$a\in\{0,1\}$

Идея о том, что блок PR эффективно вычисляет функцию И таким распределенным способом, является ключевой идеей в доказательстве Вим ван Дама, что сложность коммуникации становится тривиальной при наличии блоков PR:

Вим ван Дам. Невероятные последствия сверхсильной нелокальности. Natural Computing 12 (1): 9-12, 2013.