Fredkin gate

Fredkin gate (även CSWAP gate och konservativ logisk gate ) är en beräkningskrets som är lämplig för reversibel beräkning, uppfunnen av Edward Fredkin . Det är universellt , vilket innebär att alla logiska eller aritmetiska operationer kan konstrueras helt av Fredkin-portar. Fredkin-grinden är en krets eller enhet med tre ingångar och tre utgångar som sänder den första biten oförändrad och byter de två sista bitarna om, och endast om, den första biten är 1.

Definition

Den grundläggande Fredkin-grinden är en kontrollerad växlingsgrind som mappar tre ingångar ( C , I 1 , I 2 ) till tre utgångar ( C , O 1 , O 2 ) . C - ingången mappas direkt till C- utgången. Om C = 0 utförs inget byte; I 1 kartor till O 1 , och I 2 kartor till O 2 . I2 I annat fall byts de två utgångarna så O1 att I1 mappar till O2 . och mappar till Det är lätt att se att denna krets är reversibel, dvs "ångrar" sig själv när den körs baklänges. En generaliserad n × n Fredkin-grind skickar sina första n −2 ingångar oförändrade till motsvarande utgångar och byter ut sina sista två utgångar om och bara om de första n −2 ingångarna är alla 1.

Fredkin-grinden är den reversibla trebitarsgrinden som byter ut de två sista bitarna om, och endast om, den första biten är 1.

Sanningstabell Permutationsmatrisform _
INMATNING PRODUKTION
C jag 1 jag 2 C O 1 O 2
 0   0   0   0   0   0 
0 0 1 0 0 1
0 1 0 0 1 0
0 1 1 0 1 1
1 0 0 1 0 0
1 0 1 1 1 0
1 1 0 1 0 1
1 1 1 1 1 1

Den har den användbara egenskapen att siffrorna 0:or och 1:or bevaras genomgående, vilket i biljardbollsmodellen innebär att samma antal bollar matas ut som indata. Detta motsvarar väl bevarandet av massa i fysiken, och hjälper till att visa att modellen inte är slösaktig.

Sanningen fungerar med AND, OR, XOR och NOT

Fredkin-porten kan definieras med hjälp av sanningsfunktioner med AND , OR , XOR och NOT , enligt följande:

O 1 = I 1 XOR S
O 2 = I 2 XOR S
C ut = C in

där S = ( I 1 XOR I 2 ) OCH C

Alternativt:

O 1 = ( INTE C OCH I 1 ) ELLER ( C OCH I 2 )
O 2 = ( C OCH I 1 ) ELLER ( INTE C OCH I 2 )
C ut = C in

Fullständighet

Ett sätt att se att Fredkin-porten är universell är att observera att den kan användas för att implementera AND, NOT och OR:

Om I 2 = 0 , så är O 2 = C OCH I 1 .
Om I 2 = 1 så är O 1 = C OR I 1 .
Om I 1 = 0 och I 2 = 1 , så är O 2 = INTE C .

Exempel

Trebitars fulladdare (lägg till med bär) med fem Fredkin-portar

Trebitars fulladdare (lägg till med bär) med fem Fredkin-portar. "g"-skräputgångsbiten är (p NAND ( )q p NORq ) om r = =0, and if r=1.

Ingångarna till vänster, inklusive två konstanter, går genom tre grindar för att snabbt bestämma pariteten. 0- och 1-bitarna byter plats för varje ingångsbit som är inställd, vilket resulterar i paritetsbit på 4:e raden och invers av paritet på 5:e raden.

Sedan byter bärraden och den omvända paritetsraden om paritetsbiten är inställd och byter igen om en av p- eller q -ingångsbitarna är inställda (det spelar ingen roll vilken som används) och den resulterande bärutgången visas på den tredje raden .

P- och q -ingångarna används endast som grindkontroller så de visas oförändrade i utgången .

Quantum Fredkin gate

Den 25 mars 2016 meddelade forskare från Griffith University och University of Queensland att de hade byggt en kvant-Fredkin-port som använder kvantintrasslingen av ljuspartiklar för att byta qubits . Tillgången på kvant-Fredkin-portar kan underlätta konstruktionen av kvantdatorer .

Se även

  1. ^ Brown, Julian, Quest for the Quantum Computer , New York: Touchstone, 2000.
  2. ^ "Quantum computing är nu ett stort steg närmare tack vare ett nytt genombrott: The Fredkin gate" .
  3. ^ A quantum Fredkin gate Raj B. Patel, Joseph Ho, Franck Ferreyrol, Timothy C. Ralph och Geoff J. Pryde, Science Advances, 25 mars 2016, Vol. 2, nr. 3, e1501531, DOI: 10.1126/sciadv.1501531

Vidare läsning

Hämtad från " https://en.wikipedia.org/w/index.php?title=Fredkin_gate&oldid=1105446281 "