Fredkinova brána - Fredkin gate

Obvodové znázornění brány Fredkin

The Fredkinova brána (taky Brána CSWAP) je výpočetní obvod vhodný pro reverzibilní výpočet, vynalezl Edward Fredkin. to je univerzální, což znamená, že jakoukoli logickou nebo aritmetickou operaci lze sestavit výhradně z bran Fredkin. Brána Fredkin je obvod nebo zařízení se třemi vstupy a třemi výstupy, které přenášejí první bit beze změny a zaměňují poslední dva bity tehdy a jen tehdy, když je první bit 1.

Definice

Základní Fredkinova brána[1] je kontrolované vyměnit bránu že mapy tři vstupy (C, Já1, Já2) na tři výstupy (C, Ó1, Ó2). The C vstup je mapován přímo na C výstup. Li C = 0, neprovádí se žádný swap; Já1 mapy do Ó1, a Já2 mapy do Ó2. Jinak jsou dva výstupy zaměněny tak, aby Já1 mapy do Ó2, a Já2 mapy do Ó1. Je snadno vidět, že tento obvod je reverzibilní, tj. „Se rozepne“ sám, když běží zpět. Zobecněný n×n Fredkinova brána prochází jako první n-2 vstupy nezměněny na odpovídající výstupy a zamění své poslední dva výstupy, pokud a pouze pokud je první n-2 vstupy jsou všechny 1.

Brána Fredkin je reverzibilní tříbitová brána, která zamění poslední dva bity, a to pouze v případě, že první bit je 1.

Pravdivá tabulkaPermutační matice formulář
VSTUPVÝSTUP
CJá1Já2CÓ1Ó2
 0  0  0  0  0  0 
001001
010010
011011
100100
101110
110101
111111

Má užitečnou vlastnost, že čísla 0 a 1 jsou zachována po celou dobu, což v model kulečníkové koule znamená stejný počet koulí na výstupu jako vstup. To pěkně odpovídá zachování hmoty ve fyzice a pomáhá ukázat, že model není nehospodárný.

Pravda funguje s AND, OR, XOR a NOT

Bránu Fredkin lze definovat pomocí funkce pravdy s A, NEBO, XOR, a NE, jak následuje:

Ó1 = Já1 XOR S
Ó2 = Já2 XOR S
Cven= Cv

kde S = (Já1 XOR Já2) A C

Alternativně:

Ó1 = (NE C A Já1) NEBO (C A Já2)
Ó2 = (C A Já1) NEBO NE C A Já2)
Cven= Cv

Úplnost

Jedním ze způsobů, jak zjistit, že brána Fredkin je univerzální, je pozorovat, že ji lze použít k implementaci AND, NOT a OR:

Li Já2 = 0, tedy Ó2 = C A Já1.
Li Já2 = 1, tedy Ó1 = C NEBO Já1.
Li Já1 = 0 a Já2 = 1, tedy Ó2 = NE C.

Příklad

Tříbitové plný zmije (přidat s carry) pomocí pěti bran Fredkin

Tříbitové plný zmije (přidat s carry) pomocí pěti bran Fredkin. Odpadní výstupní bit „g“ je (p NOR q), pokud r = 0, a (p NAND q), pokud r = 1.

Vstupy vlevo, včetně dvou konstant, procházejí třemi branami a rychle určují paritu. 0 a 1 bity zaměňují místa pro každý vstupní bit, který je nastaven, což má za následek paritní bit ve 4. řádku a inverzi parity v 5. řádku.

Poté se vymění řádek přenosu a řádek inverzní parity, pokud je nastaven paritní bit, a vymění se znovu, pokud je nastaven jeden ze vstupních bitů p nebo q (nezáleží na tom, který je použit) a výsledný výstup přenosu se objeví na 3. řádku .

Vstupy p a q se používají pouze jako ovládací prvky brány, takže se na výstupu zobrazují beze změny.

Kvantová Fredkinova brána

25. března 2016 vědci z Griffith University a University of Queensland oznámili, že postavili kvantovou Fredkinovu bránu, která využívá Kvantové zapletení částic světla vyměnit qubits. Stavbu může usnadnit dostupnost kvantových bran Fredkin kvantové počítače.[2][3]

Viz také

Reference

  1. ^ Brown, Julian, Pátrání po kvantovém počítači, New York: Touchstone, 2000.
  2. ^ http://www.pcworld.com/article/3048763/hardware/quantum-computing-is-now-a-big-step-closer-thanks-to-this-new-breakthrough.html
  3. ^ Kvantová Fredkinova brána Raj B. Patel, Joseph Ho, Franck Ferreyrol, Timothy C. Ralph a Geoff J. Pryde, Science Advances, 25. března 2016, sv. 2, č. 3, e1501531, DOI: 10.1126 / sciadv.1501531

Další čtení

  • Fredkin, Edward; Toffoli, Tommaso (1982). „Konzervativní logika“ (PDF). International Journal of Theoretical Physics. 21 (3–4): 219–253. doi:10.1007 / BF01857727. Archivovány od originál (PDF) dne 17. října 2006.