Puerta Fredkin - Fredkin gate
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 de 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.
Definición
La puerta Fredkin básica es una puerta de intercambio controlada que asigna tres entradas ( C , I 1 , I 2 ) a 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 y 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 verdad funciona con AND, OR, XOR y NOT
La puerta Fredkin se puede definir usando funciones de verdad con AND , OR , XOR y NOT , de la siguiente manera:
- O 1 = I 1 XOR S
- O 2 = I 2 XOR S
- C fuera = C en
donde S = ( I 1 XOR I 2 ) Y C
Alternativamente:
- O 1 = (NO C Y I 1 ) O ( C Y I 2 )
- O 2 = ( C Y I 1 ) O (NO C Y I 2 )
- C fuera = C en
Lo completo
Una forma de ver que la puerta Fredkin es universal es observar que se puede usar para implementar AND, NOT y OR:
- Si I 2 = 0 , entonces O 2 = C Y I 1 .
- Si I 2 = 1 , entonces O 1 = C O I 1 .
- Si I 1 = 0 y I 2 = 1 , entonces O 2 = NO C .
Ejemplo
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.
Puerta de Fredkin cuántica
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 .
Ver también
- Computación cuántica
- Puerta cuántica
- Programación cuántica
- Puerta Toffoli , que es una puerta NO controlada-controlada .
Referencias
- ^ Brown, Julian, The Quest for the Quantum Computer , Nueva York: Touchstone, 2000.
- ^ "La computación cuántica está ahora un gran paso más cerca gracias a un nuevo avance: la puerta Fredkin" .
- ^ Una puerta cuántica de Fredkin Raj B. Patel, Joseph Ho, Franck Ferreyrol, Timothy C. Ralph y Geoff J. Pryde, Science Advances, 25 de marzo de 2016, Vol. 2, no. 3, e1501531, DOI: 10.1126 / sciadv.1501531
Otras lecturas
- Fredkin, Edward ; Toffoli, Tommaso (1982). "Lógica conservadora" (PDF) . Revista Internacional de Física Teórica . 21 (3-4): 219-253. Código Bibliográfico : 1982IJTP ... 21..219F . doi : 10.1007 / BF01857727 . S2CID 37305161 . Archivado desde el original (PDF) el 17 de octubre de 2006.