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

13

Фон

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

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

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

Вопрос

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

наблюдения

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

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

Эван Дженкинс
источник

Ответы:

7

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

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

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

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

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

Джон Уотроус
источник