Fredkin-Gate

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen
Eingänge Ausgänge
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

Das Fredkin-Gate ist eine von Edward Fredkin erfundene Schaltung, die für reversibles Computing verwendet wird. Input und Output bestehen aus drei Bits. Ist das erste Bit = 1, werden die anderen beiden Bits miteinander vertauscht; ist es = 0, findet kein Tausch statt.

Eine wichtige Eigenschaft ist, dass das Fredkin-Gate „konservativ“ ist, das heißt, die Ausgabe hat gleich viele Einsen wie die Eingabe. Da es keinen Informationsverlust gibt, ist die Operation vollständig umkehrbar.

O1 = I1 XOR S

O2 = I2 XOR S

mit S = (I1 XOR I2) AND C

  • Joachim Stolze, Dieter Suter: Quantum computing. A short course from theory to experiment. Wiley-VCH, Weinheim 2008, S. 33, ISBN 978-3-527-40787-3.