Welche Beziehung besteht zwischen dem Toffoli-Tor und der Popescu-Rohrlich-Box?

Hintergrund

Das Toffoli-Gatter ist ein klassisches Logikgatter mit 3 Eingängen und 3 Ausgängen. Es sendet an . Dies ist insofern von Bedeutung, als es für die reversible (klassische) Berechnung universell ist.$(x, y, a)$$(x, y, a \oplus (x \cdot y))$

Die Popescu-Rohrlich-Box ist das einfachste Beispiel für eine nicht signalisierende Korrelation. Es nimmt ein Paar von Eingängen und Ausgängen ( a , b ) erfüllen x ⋅ y = ein ⊕ b , so daß eine und sind beide gleichförmigen Zufallsvariablen. Es ist universell für eine bestimmte Klasse von ( aber nicht alle ) nicht signalisierenden Korrelationen.$(x, y)$$(a, b)$$x \cdot y = a \oplus b$$a$$b$

Für mich sehen diese beiden Objekte sehr ähnlich aus, besonders wenn wir die PR-Box erweitern, indem wir sie ausgeben lassen . Diese PR-Box mit 2 Eingängen und 4 Ausgängen ist das Toffoli-Gatter mit 3 Eingängen und 3 Ausgängen, wobei jedoch der dritte Eingang durch einen Zufallsausgang ersetzt wird. Ich konnte jedoch keine Referenzen finden, die sie in Beziehung setzen.$(x, y, a, b) = (x, y, a, a \oplus (x \cdot y))$

Frage

Welche Beziehung besteht zwischen dem Toffoli-Tor und der Popescu-Rohrlich-Box? Gibt es so etwas wie eine Entsprechung zwischen reversiblen klassischen Schaltkreisen und (einer bestimmten Klasse von?) Nicht signalisierenden Korrelationen, die sich gegenseitig zuordnen lassen?

Beobachtungen

1. Das Festlegen einer nicht signalisierenden Korrelation erfordert nicht nur eine Funktion, sondern auch die Zuweisung der einzelnen Ein- und Ausgänge zu einer Partei, die diese steuert. Eine PR-Box signalisiert nichts mehr, wenn wir Alice erlauben, beide Eingänge und Bob beide Ausgänge zu lesen. Oder in unserer "erweiterten" PR-Box, wenn Alice eingibt , muss sie auch diejenige sein, die die Kopie von liest . Es erscheint daher nicht trivial, für eine allgemeine Schaltung (wobei einige Eingänge möglicherweise durch zufällige Ausgänge ersetzt werden) alle Möglichkeiten zu bestimmen, wie Ein- und Ausgänge Parteien zugewiesen werden können, so dass keine Kommunikation möglich ist.$x$$x$

2. Wir können das obige Verfahren auf jedes Logikgatter anwenden, auch auf irreversible. Zum Beispiel können wir UND nehmen und eine der Eingaben durch eine zufällige Ausgabe ersetzen und eine Funktion mit einer Eingabe und einem Paar wobei eine einheitliche Zufallsvariable ist. Allerdings ist konditioniert auf , so dass der einzige Weg , so kann dieser nicht-Signalisierung ist , wenn Alice, die Eingänge , erhält . Dieses Verfahren kann jedoch bereits klassisch mit einer gemeinsamen Zufallsquelle reproduziert werden. Daher würde ich erwarten, dass die Einbeziehung irreversibler Gatter die Klasse der nicht signalisierenden Korrelationen, die man konstruieren kann, nicht erweitert.$x$$(a, x \cdot a)$$a$$x \cdot a$$0$$x = 0$$x$$x \cdot a$

Eine natürliche Art, Toffoli-Gates und PR-Boxen in Beziehung zu setzen, besteht darin, beide als Repräsentationen der UND-Funktion zweier Binäreingänge zu betrachten, jedoch auf unterschiedliche Weise. Der Zusammenhang mit der UND-Funktion ist durch die Frage offensichtlich und klar erkennbar, aber ich würde es etwas anders ausdrücken:

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\}$ist ein gleichmäßig erzeugtes Zufallsbit. Der Ausgang der PR-Box ist daher entweder ein perfekt korreliertes oder ein perfekt antikorreliertes Paar von Zufallsbits, abhängig davon, ob das UND der Eingänge 0 oder 1 ist. Dies ist interessant, da Alice und Bob gemeinsam die Ausgabe der UND-Funktion kennen (die sie durch Berechnen des XOR ihrer Ausgabebits erhalten können), während sie einzeln überhaupt keine Informationen über diesen Wert haben.

Die Idee, dass die PR-Box die UND-Funktion auf diese verteilte Weise effektiv berechnet, ist eine Schlüsselidee im Beweis von Wim van Dam, dass die Komplexität der Kommunikation bei Vorhandensein von PR-Boxen trivial wird:

Wim van Dam. Unplausible Folgen einer übermächtigen Nichtlokalität. Natural Computing 12 (1): 9-12, 2013.