Fredkinův ventil

Fredkinovo hradlo (CSWAP z angl.  Controlled SWAP  - řízená ústředna) - univerzální třívstupové logické hradlo třídy CU (řízené operace U), dostatečné pro sestavení obvodů libovolného stupně složitosti. Má reverzibilitu - se znalostí stavu výstupů můžete přesně nastavit stavy vstupů prvku, takže na jeho základě lze stavět vratné výpočty a reverzibilní logické obvody. Zejména může být použit jako kvantová brána při implementaci kvantových počítačů . Pojmenováno po Edwardu Fredkinovikterý tuto bránu navrhl [1] .

Ventil má tři vstupy a tři výstupy - (C, A, B). Pokud existuje signál řídicího vedení (první vstup, c ), jsou signály dvou řízených vedení (druhý a třetí vstup aab ) obráceny . Při absenci řídícího signálu procházejí signály řízených vedení přímo, bez výměnné akce. Prvním výstupem je neupravený signál řídicího vedení [2] .

Specifikace

Obecně je ovládání podobné jako u hradla „kontrolovaného ne“ (CNOT), avšak ekvivalence kladné a záporné logiky v kombinaci se dvěma spínanými vstupy jej činí univerzálním a soběstačným, na rozdíl od „kontrolovaného ne“.

Důvod symetrie ventilu uvádí také Richard Feynman ve své knize:

Fredkin přidal další omezení na vstupy a výstupy bran, které zvažoval. Požadoval nejen to, aby brána byla vratná, ale aby se počet jedniček a nul nikdy neměnil. Nebyl pro to žádný dobrý důvod, ale přesto to udělal.

Původní text  (anglicky)[ zobrazitskrýt] Fredkin přidal další omezení na výstupy a vstupy bran, které zvažoval. Požadoval, že brána musí být nejen reverzibilní, ale počet 1s a 0s by se nikdy neměl měnit. Není pro to žádný dobrý důvod, ale přesto to udělal. Zavedl bránu provádějící řízenou výměnu. — Feynman Readings in Computing, 2.3 „Více o branách: Reverzibilní brány“

Vzhledem k vyváženosti počtu nul a jedniček (konzervativnost) lze tuto bránu implementovat na kulečníkovém počítači , který rovněž navrhl Fredkin [3] .

Pravdivostní tabulka [4] :

C A B C' A' B'
0 0 0 0 0 0
0 0 jeden 0 0 jeden
0 jeden 0 0 jeden 0
0 jeden jeden 0 jeden jeden
jeden 0 0 jeden 0 0
jeden 0 jeden jeden jeden 0
jeden jeden 0 jeden 0 jeden
jeden jeden jeden jeden jeden jeden

Hradlo Fredkin spolu s hradlem Toffoli , jsou známá univerzální vratná třívstupová hradla, pomocí kteréhokoli z nich je možné implementovat libovolnou reverzibilní logickou funkci [5] .

Poznámky

  1. ↑ "Feynman Readings on Computing": "...Na jeho počest tomu budeme říkat Fredkinova brána..."
  2. ↑ Michael A. Nielsen, Isaac L. Chuang, Quantum Computation and Quantum Information: 10th Anniversary Edition Archived 5. March 2016 at the Wayback Machine // Cambridge, 2010, ISBN 9781139495486 , page 156 „reversible the Fredkin logic gate“ . … Fredkinovo hradlo má tři vstupní bity a tři výstupní bity, … Bit c je řídicí bit, jehož balue se působením Fredkinova hradla nemění. .. Pokud je c nastaveno na 0, pak aab zůstanou samotné… Pokud je c nastaveno na 1, aab jsou prohozeny.“
  3. ↑ Část 7. Základní limity ve výpočtech Archivováno 14. května 2015 na Wayback Machine // MIT EECS 6-701 Úvod do nanoelektroniky, jaro 2010  : „Snad nejznámějším reverzibilním počítačem je počítač s kulečníkovými koulemi, jehož průkopníkem je Fredkin. … Obr. 7.11. Symbol pro Fredkinovu bránu. … Obr. 7.12. Fredkinova brána vyrobená ze čtyř spínačů kulečníkových koulí. Po Feynmanovi přednášky o počítání. Editoři AJG Hey a RW Allen, Addison-Wesley 1996.
  4. ↑ Michael A. Nielsen, Isaac L. Chuang, Quantum Computation and Quantum Information: 10th Anniversary Edition Archived 4. March 2016 at the Wayback Machine // Cambridge, 2010, ISBN 9781139495486 , page 157 "Figure 3.1 "
  5. ↑ Technická zpráva MIT/LCS/TM-151 Archivováno 4. ledna 2015 ve Wayback Machine (1980), také Toffoli, Tommaso (1980). JW de Bakker a J. van Leeuwen , ed. Reverzibilní počítání . Automaty, jazyky a programování , 7. kolokvium ]. Noordwijkerhout, Nizozemsko: Springer Verlag. str. 632–644. DOI : 10.1007/3-540-10003-2_104 . ISBN  3-540-10003-2 . Parametry |author=a |last=vzájemně se duplikují ( nápověda )

Literatura