Apa hubungan antara gerbang Toffoli dan kotak Popescu-Rohrlich?

Latar Belakang

Gerbang Toffoli adalah gerbang logika klasik 3-input, 3-output. Ia mengirim ke ( x , y , a ⊕ ( x ⋅ y ) ) . Ini penting karena itu bersifat universal untuk perhitungan (reversibel) klasik.$(x, y, a)$$(x, y, a \oplus (x \cdot y))$

Kotak Popescu-Rohrlich adalah contoh paling sederhana dari korelasi non-pensinyalan. Dibutuhkan sepasang input dan output ( a , b ) memuaskan x ⋅ y = a ⊕ b sehingga a dan b keduanya merupakan variabel acak yang seragam. Ini universal untuk kelas tertentu ( tetapi tidak semua ) korelasi non-pensinyalan.$(x, y)$$(a, b)$$x \cdot y = a \oplus b$$a$$b$

Untuk mata saya, dua benda ini terlihat sangat mirip, terutama jika kita menambah kotak PR oleh karena itu keluaran . Kotak PR 2-input, 4-output "adalah" gerbang Toffoli 3-input, 3-output tetapi dengan input ketiga diganti dengan output acak. Tetapi saya tidak dapat menemukan referensi yang menghubungkannya.$(x, y, a, b) = (x, y, a, a \oplus (x \cdot y))$

Pertanyaan

Apa hubungan antara gerbang Toffoli dan kotak Popescu-Rohrlich? Apakah ada sesuatu seperti korespondensi antara sirkuit klasik reversibel dan (kelas tertentu?) Korelasi non-pensinyalan yang memetakan satu ke yang lain?

Pengamatan

1. $x$$x$

2. $x$$(a, x \cdot a)$$a$$x \cdot a$$0$$x = 0$$x$$x \cdot a$. Tetapi prosedur ini sudah dapat direproduksi secara klasik dengan sumber keacakan yang dibagi. Jadi saya berharap bahwa termasuk gerbang yang tidak dapat dikembalikan tidak memperluas kelas korelasi non-sinyal yang dapat dibangun.

Cara alami untuk menghubungkan gerbang Toffoli dan kotak PR adalah dengan melihatnya sebagai representasi fungsi AND dari dua input biner, tetapi dengan cara yang berbeda. Koneksi dengan fungsi AND jelas dan diakui dengan jelas oleh pertanyaan, tapi saya akan mengungkapkannya dengan cara yang sedikit berbeda:

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\}$adalah bit acak yang dihasilkan secara seragam. Output dari kotak PR karenanya adalah pasangan bit acak yang berkorelasi sempurna atau sangat tidak berkorelasi, tergantung pada apakah AND dari input masing-masing adalah 0 atau 1. Ini menarik karena Alice dan Bob secara kolektif mengetahui output dari fungsi AND (yang dapat mereka peroleh dengan menghitung XOR dari bit output mereka), sementara secara individual mereka tidak memiliki informasi sama sekali tentang nilai ini.

Gagasan bahwa kotak PR secara efektif menghitung fungsi AND dengan cara yang didistribusikan ini adalah gagasan kunci dalam bukti Wim van Dam bahwa kompleksitas komunikasi menjadi sepele di hadapan kotak-kotak PR:

Wim van Dam. Konsekuensi yang tidak masuk akal dari nonlocality superstrong. Komputasi Alam 12 (1): 9-12, 2013.