Fredkin ventil

Fredkin gate (CSWAP från engelskan.  Controlled SWAP  - controlled exchange) - en universell logikgrind med tre ingångar av CU-klassen (kontrollerade operationer U), tillräcklig för att bygga kretsar av vilken grad av komplexitet som helst. Den har reversibilitet - genom att känna till utgångarnas tillstånd kan du exakt ställa in tillstånden för elementets ingångar, så på grundval av det kan du bygga reversibla beräkningar och reversibla logiska kretsar. I synnerhet kan den användas som en kvantport vid implementering av kvantdatorer . Uppkallad efter Edward Fredkinsom föreslog denna port [1] .

Ventilen har tre ingångar och tre utgångar - (C, A, B). När det finns en styrlinjesignal (första ingången, c ), vänds signalerna från de två styrda linjerna (andra och tredje ingångarna, a och b ) om. I avsaknad av en styrsignal passerar de styrda ledningarnas signaler direkt, utan en utbytesåtgärd. Den första utgången är den omodifierade styrledningssignalen [2] .

Specifikationer

I allmänhet liknar den i drift den "kontrollerade ej" -grinden (CNOT), men ekvivalensen av positiv och negativ logik i kombination med två switchade ingångar gör den universell och självförsörjande, till skillnad från "kontrollerad ej".

Orsaken till ventilens symmetri ges också av Richard Feynman i sin bok:

Fredkin lade till en ytterligare begränsning på ingångarna och utgångarna från grindarna som han ansåg. Han krävde inte bara att porten skulle vara reversibel, utan att antalet ettor och nollor aldrig ändras. Det fanns ingen bra anledning till det, men han gjorde det ändå.

Originaltext  (engelska)[ visaDölj] Fredkin lade till en extra begränsning på utgångarna och ingångarna från grindarna som han ansåg. Han krävde att inte bara en gate måste vara reversibel, utan att antalet 1:or och 0:or aldrig skulle ändras. Det finns ingen bra anledning till detta, men han gjorde det ändå. Han introducerade en grind som utförde en kontrollerad växlingsoperation. — Feynman Readings in Computing, 2.3 "Mer om gates: Reversible Gates"

På grund av balansen mellan antalet nollor och ettor (konservativitet), kan denna gate implementeras på en biljarddator , också föreslagen av Fredkin [3] .

Sanningstabell [4] :

C A B C' A' B'
0 0 0 0 0 0
0 0 ett 0 0 ett
0 ett 0 0 ett 0
0 ett ett 0 ett ett
ett 0 0 ett 0 0
ett 0 ett ett ett 0
ett ett 0 ett 0 ett
ett ett ett ett ett ett

Fredkin-porten, tillsammans med Toffoli-porten , är välkända universella reversibla tre-ingångsportar, med hjälp av någon av dem är det möjligt att implementera vilken reversibel logikfunktion som helst [5] .

Anteckningar

  1. ↑ "Feynman Readings on Computing": "...Till hans ära kommer vi att kalla det en Fredkin-port..."
  2. ↑ Michael A. Nielsen, Isaac L. Chuang, Quantum Computation and Quantum Information: 10th Anniversary Edition Arkiverad 5 mars 2016 på Wayback Machine // Cambridge, 2010, ISBN 9781139495486 , sida 156 "reversible gate känd som Fredkins universalport, den vändbara gate . ... Fredkin-grinden har tre ingångsbitar och tre utgångsbitar, ... Biten c är en kontrollbit, vars balue inte ändras av Fredkin-grinden. .. Om c är satt till 0 så lämnas a och b ensamma... Om c är satt till 1 byts a och b om."
  3. ↑ Del 7. Fundamental Limits in Computation Arkiverad 14 maj 2015 på Wayback Machine // MIT EECS 6-701 Introduktion till nanoelektronik, våren 2010  : "Den kanske mest kända reversibla datorn är biljardbollsdatorn som Fredkin banat väg för. … Fig. 7.11. Symbolen för Fredkinporten. … Fig. 7.12. En Fredkin-grind konstruerad av fyra biljardbollsväxlar. Efter Feynman, föreläsningar om beräkning. Redaktörer AJG Hey och RW Allen, Addison-Wesley 1996.
  4. ↑ Michael A. Nielsen, Isaac L. Chuang, Quantum Computation and Quantum Information: 10th Anniversary Edition Arkiverad 4 mars 2016 på Wayback Machine // Cambridge, 2010, ISBN 9781139495486 , sida 157 "Figure 5 tabell Fredkin 3. "
  5. ↑ Teknisk rapport MIT/LCS/TM-151 Arkiverad 4 januari 2015 på Wayback Machine (1980), även Toffoli, Tommaso (1980). JW de Bakker och J. van Leeuwen , red. Reversibel datoranvändning . Automater, språk och programmering , sjunde kollokviet ]. Noordwijkerhout, Nederländerna: Springer Verlag. pp. 632–644. DOI : 10.1007/3-540-10003-2_104 . ISBN  3-540-10003-2 . Parametrar |author=och |last=duplicera varandra ( hjälp )

Litteratur