Puerta de Fredkin (CSWAP del inglés. Controlled SWAP - intercambio controlado) - una puerta lógica universal de tres entradas de la clase CU (operaciones controladas U), suficiente para construir circuitos de cualquier grado de complejidad. Tiene reversibilidad: al conocer el estado de las salidas, puede establecer con precisión los estados de las entradas del elemento, por lo que, sobre esta base, puede construir cálculos reversibles y circuitos lógicos reversibles. En particular, se puede utilizar como puerta cuántica en la implementación de computadoras cuánticas . El nombre de Edward Fredkinquien propuso esta puerta [1] .
La válvula tiene tres entradas y tres salidas - (C, A, B). Cuando hay una señal de línea de control (primera entrada, c ), las señales de las dos líneas controladas ( segunda y tercera entradas, ayb ) se invierten. En ausencia de una señal de control, las señales de las líneas controladas pasan directamente, sin una acción de intercambio. La primera salida es la señal de la línea de control no modificada [2] .
En general, es similar en funcionamiento a la puerta "no controlada" (CNOT), sin embargo, la equivalencia de lógica positiva y negativa en combinación con dos entradas conmutadas la hace universal y autosuficiente, a diferencia de la "no controlada".
La razón de la simetría de la válvula también la da Richard Feynman en su libro:
Fredkin agregó una restricción adicional sobre las entradas y salidas de las puertas que consideró. Requería no solo que la puerta fuera reversible, sino que el número de unos y ceros nunca cambiara. No había una buena razón para ello, pero lo hizo de todos modos.
Texto original (inglés)[ mostrarocultar] Fredkin agregó una restricción adicional en las salidas y entradas de las puertas que consideró. Exigió que no solo una puerta debe ser reversible, sino que el número de 1 y 0 nunca debe cambiar. No hay una buena razón para esto, pero lo hizo de todos modos. Introdujo una puerta que realizaba una operación de intercambio controlado. — Feynman Readings in Computing, 2.3 "Más sobre puertas: Puertas reversibles"Debido al equilibrio del número de ceros y unos (conservadurismo), esta puerta se puede implementar en una computadora de billar , también propuesta por Fredkin [3] .
Tabla de verdad [4] :
| C | A | B | C' | A' | B' |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | una | 0 | 0 | una |
| 0 | una | 0 | 0 | una | 0 |
| 0 | una | una | 0 | una | una |
| una | 0 | 0 | una | 0 | 0 |
| una | 0 | una | una | una | 0 |
| una | una | 0 | una | 0 | una |
| una | una | una | una | una | una |
La puerta de Fredkin, junto con la puerta de Toffoli , son puertas universales reversibles de tres entradas bien conocidas, con la ayuda de cualquiera de ellas es posible implementar cualquier función lógica reversible [5] .