Fredkin gate
Encyclopedia
The Fredkin gate is a computational circuit suitable for reversible computing
, invented by Ed Fredkin. It is universal, which means that any logical or arithmetic operation can be constructed entirely of Fredkin gates. The Fredkin gate is the three-bit gate that swaps the last two bits if the first bit is 1.
The basic Fredkin gate is a controlled swap gate that maps
three inputs (C, I1, I2) onto three outputs (C, O1, O2). The C input is mapped directly to the C output. If C = 0, no swap is performed; I1 maps to O1, and I2 maps to O2. Otherwise, the two outputs are swapped so that I1 maps to O2, and I2 maps to O1. It is easy to see that this circuit is reversible, i.e., "undoes itself" when run backwards. A generalized n×n Fredkin gate passes its first n-2 inputs unchanged to the corresponding outputs, and swaps its last two outputs if and only if the first n-2 inputs are all 1.
The Fredkin gate is the reversible three-bit gate that swaps the last two bits if the first bit is 1. Its truth table
is shown to the right.
It has the useful property that the numbers of 0s and 1s are conserved throughout, which in the billiard ball model
means the same number of balls are output as input. This corresponds nicely to the conservation of mass
in physics, and helps to show that the model is not wasteful.
O2 = I2 XOR S
with S = (I1 XOR I2) AND C
Reversible computing
Reversible computing is a model of computing where the computational process to some extent is reversible, i.e., time-invertible. A necessary condition for reversibility of a computational model is that the transition function mapping states to their successors at a given later time should be...
, invented by Ed Fredkin. It is universal, which means that any logical or arithmetic operation can be constructed entirely of Fredkin gates. The Fredkin gate is the three-bit gate that swaps the last two bits if the first bit is 1.
Definition
| INPUT | OUTPUT | ||||
|---|---|---|---|---|---|
| C | I1 | I2 | C | O1 | O2 |
| 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 |
The basic Fredkin gate is a controlled swap gate that maps
Function (mathematics)
In mathematics, a function associates one quantity, the argument of the function, also known as the input, with another quantity, the value of the function, also known as the output. A function assigns exactly one output to each input. The argument and the value may be real numbers, but they can...
three inputs (C, I1, I2) onto three outputs (C, O1, O2). The C input is mapped directly to the C output. If C = 0, no swap is performed; I1 maps to O1, and I2 maps to O2. Otherwise, the two outputs are swapped so that I1 maps to O2, and I2 maps to O1. It is easy to see that this circuit is reversible, i.e., "undoes itself" when run backwards. A generalized n×n Fredkin gate passes its first n-2 inputs unchanged to the corresponding outputs, and swaps its last two outputs if and only if the first n-2 inputs are all 1.
The Fredkin gate is the reversible three-bit gate that swaps the last two bits if the first bit is 1. Its truth table
Truth table
A truth table is a mathematical table used in logic—specifically in connection with Boolean algebra, boolean functions, and propositional calculus—to compute the functional values of logical expressions on each of their functional arguments, that is, on each combination of values taken by their...
is shown to the right.
It has the useful property that the numbers of 0s and 1s are conserved throughout, which in the billiard ball model
Billiard-Ball Computer
A billiard ball computer, also known as a conservative logic circuit, is an idealized model of a reversible mechanical computer based on newtonian dynamics, proposed in 1982 by Edward Fredkin and Tommaso Toffoli...
means the same number of balls are output as input. This corresponds nicely to the conservation of mass
Conservation of mass
The law of conservation of mass, also known as the principle of mass/matter conservation, states that the mass of an isolated system will remain constant over time...
in physics, and helps to show that the model is not wasteful.
Logic function with XOR and AND gates
O1 = I1 XOR SO2 = I2 XOR S
with S = (I1 XOR I2) AND C
Example
Here is a diagram of a three-bit adder implemented using Fredkin gates. The three inputs are A, B and C, supplemented by the constant T and F. In the diagram, the leftmost input (before the colon) swaps the two rightmost inputs if it is true.See also
- Quantum computing
- Quantum gateQuantum gateIn quantum computing and specifically the quantum circuit model of computation, a quantum gate is a basic quantum circuit operating on a small number of qubits. They are the building blocks of quantum circuits, like classical logic gates are for conventional digital circuits.Unlike many classical...
- Quantum programmingQuantum programmingQuantum programming is a set of computer programming languages that allow the expression of quantum algorithms using high-level constructs. The point of quantum languages is not so much to provide a tool for programmers, but to provide tools for researchers to understand better how quantum...
- Toffoli gateToffoli gateIn computer science, the Toffoli gate , invented by Tommaso Toffoli, is a universal reversible logic gate, which means that any reversible circuit can be constructed from Toffoli gates...
, which is a controlled-controlled-NOT gate.
Further reading
- E. Fredkin and T. ToffoliTommaso ToffoliTommaso Toffoli is a professor of electrical and computer engineering at Boston University. He joined the faculty in 1995. He was born in June, 1943 in Montereale Valcellina, in northeastern Italy, and was raised in Rome. He received his doctorate in physics from the University of Rome La...
. Conservative logic. International Journal of Theoretical Physics, 21:219–253, 1982.