Porta Fredkin

Sumador complet de tres bits (afegiu amb transport) mitjançant cinc portes Fredkin.

La porta Fredkin (també porta CSWAP i porta lògica conservadora) és un circuit computacional adequat per a la computació reversible, inventat per Edward Fredkin. És universal, el que significa que qualsevol operació lògica o aritmètica es pot construir completament amb portes de Fredkin. La porta Fredkin és un circuit o dispositiu amb tres entrades i tres sortides que transmet el primer bit sense canvis i intercanvia els dos últims bits si, i només si, el primer bit és 1.

La porta Fredkin bàsica és una porta d'intercanvi controlada que mapeja tres entrades (C, I₁, I₂) a tres sortides (C, O₁, O₂). L'entrada C s'assigna directament a la sortida C. Si C = 0, no es realitza cap intercanvi; I₁ mapa a O₁, i I₂ mapa a O₂. En cas contrari, les dues sortides s'intercanvien de manera que I₁ s'assigni a O₂ i I₂ s'assigni a O₁. És fàcil veure que aquest circuit és reversible, és a dir, es "desfà" quan es corre cap enrere. Una porta de Fredkin generalitzada n × n passa les seves primeres n−2 entrades sense canvis a les sortides corresponents, i intercanvia les seves dues últimes sortides si i només si les primeres n−2 entrades són totes 1.

La porta Fredkin és la porta reversible de tres bits que intercanvia els dos últims bits si, i només si, el primer bit és 1.

Taula de la veritat i Forma de matriu de permutació ENTRADA SORTIDA C I1 I₂ C O1 O₂  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

${\begin{bmatrix}1&0&0&0&0&0&0&0\\0&1&0&0&0&0&0&0\\0&0&1&0&0&0&0&0\\0&0&0&1&0&0&0&0\\0&0&0&0&1&0&0&0\\0&0&0&0&0&0&1&0\\0&0&0&0&0&1&0&0\\0&0&0&0&0&0&0&1\\\end{bmatrix}}$

Té la propietat útil que els nombres de 0 i 1 es conserven a tot arreu, la qual cosa en el model de boles de billar significa que es surt el mateix nombre de boles que l'entrada. Això es correspon molt bé amb la conservació de la massa en física i ajuda a demostrar que el model no és un malbaratament.

El 25 de març de 2016, investigadors de la Universitat Griffith i la Universitat de Queensland van anunciar que havien construït una porta Fredkin quàntica que utilitza l'entrellat quàntic de partícules de llum per intercanviar qubits. La disponibilitat de portes quàntiques de Fredkin pot facilitar la construcció d'ordinadors quàntics.