La puerta Fredkin (también puerta CSWAP y puerta lógica conservadora ) es un circuito computacional adecuado para computación reversible , inventado por Edward Fredkin . Es universal , lo que significa que cualquier operación lógica o aritmética puede construirse completamente a partir de puertas Fredkin. La puerta Fredkin es un circuito o dispositivo con tres entradas y tres salidas que transmite el primer bit sin cambios e intercambia los dos últimos bits si, y solo si, el primer bit es 1.
La puerta Fredkin básica [1] es una puerta de intercambio controlada que mapea tres entradas ( C , I 1 , I 2 ) en tres salidas ( C , O 1 , O 2 ) . La entrada C se asigna directamente a la salida C. Si C = 0, no se realiza ningún intercambio; I 1 se asigna a O 1 e I 2 se asigna a O 2. De lo contrario, las dos salidas se intercambian para que I 1 se asigne a O 2 e I 2 se asigne a O 1 . Es fácil ver que este circuito es reversible, es decir, se "deshace" cuando se ejecuta al revés. Una compuerta Fredkin generalizada n × n pasa sus primeras n −2 entradas sin cambios a las salidas correspondientes, e intercambia sus dos últimas salidas si y solo si las primeras n −2 entradas son todas 1.
La puerta Fredkin es la puerta reversible de tres bits que intercambia los dos últimos bits si, y solo si, el primer bit es 1.
Mesa de la verdad | Forma de matriz de permutación | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
Tiene la propiedad útil de que los números de 0 y 1 se conservan en todo momento, lo que en el modelo de bola de billar significa que se produce la misma cantidad de bolas como entrada. Esto se corresponde muy bien con la conservación de la masa en física y ayuda a demostrar que el modelo no es un desperdicio.
La puerta Fredkin se puede definir usando funciones de verdad con AND , OR , XOR y NOT , de la siguiente manera:
donde S = ( I 1 XOR I 2 ) Y C
Alternativamente:
Una forma de ver que la puerta Fredkin es universal es observar que se puede usar para implementar AND, NOT y OR:
Sumador completo de tres bits (agregar con acarreo) usando cinco puertas Fredkin. El bit de salida de basura "g" es ( p NOR q ) si r = 0 , y ( p NAND q ) si r = 1 .
Las entradas de la izquierda, incluidas dos constantes, pasan por tres puertas para determinar rápidamente la paridad. Los bits 0 y 1 intercambian lugares para cada bit de entrada que se establece, lo que da como resultado un bit de paridad en la cuarta fila e inverso de paridad en la quinta fila.
Luego, la fila de acarreo y la fila de paridad inversa se intercambian si el bit de paridad está establecido y se intercambian nuevamente si se establece uno de los bits de entrada p o q (no importa cuál se use) y la salida de acarreo resultante aparece en la tercera fila .
Los p y q entradas sólo se utilizan como controles de la puerta por lo que aparecen sin cambios en la salida.
El 25 de marzo de 2016, investigadores de la Universidad Griffith y la Universidad de Queensland anunciaron que habían construido una puerta Fredkin cuántica que utiliza el entrelazamiento cuántico de partículas de luz para intercambiar qubits . La disponibilidad de puertas cuánticas Fredkin puede facilitar la construcción de computadoras cuánticas . [2] [3]