Für reversible Logik ist es unabdingbar, dass zu jedem Ausgang eines Logikgatters ein eindeutiger Eingang gehört und durch Umkehrung der Operation der Eingang wiederhergestellt werden kann. Herkömmliche Logikgatter wie Und-Gatter und NOR-Gatter verarbeiten mehrere Eingangssignale und liefern typischerweise nur ein Ausgangssignal. Aus dem Ausgangssignal lässt sich also nicht mehr schließen, welche Eingangssignale das Ergebnis bewirkt haben.
Waren früher die Überlegungen des Reversiblen Computings getrieben von der Erkenntnis, dass Logik-Gatter, die mehr Eingänge als Ausgänge haben, Information „vernichten“ und nach dem Landauer-Prinzip dadurch Energie als Wärme abgeben, so muss in jüngerer Zeit in Quantencomputern, die riesige Datenmengen komplex verarbeiten, die Entwicklung von Wärme minimiert werden, da diese zu Fehlfunktionen führen würde.
CNOT-Gatter
Ein einfaches Gatter, das reversibel ist, ist das Kontrollierte-Nicht-Gatter (englisch: Controlled NOT Gate / CNOT-Gate). Dieses verknüpft ein Kontroll-Bit und ein Ziel-Bit als Eingänge und liefert als Ausgänge wieder das Kontroll-Bit und verarbeitetes Ziel-Bit.
Eingänge
Ausgänge
Kontroll-Bit
Ziel-Bit
Kontrol-Bit Out
Ziel Out
0
0
0
0
0
1
0
1
1
0
1
1
1
1
1
0
Diese Funktion kann wie folgt dargestellt werden: Gibt man die Ausgangssignale wieder als Eingangssignale in das CNOT-Gatter, erhält man als Ausgang wieder die ursprünglichen Eingangssignale – die Funktion ist also reversibel. Allerdings lassen sich mit diesem einfachen Gatter (und gegebenenfalls kombiniert mit einem Nicht-Gatters) nicht sämtliche Funktionen der Booleschen Logik verwirklichen.
Andere Darstellungsweisen für das CNOT-Gate:
Matrixdarstellung
Quantencomputing-Symbol
Toffoli-Gatter
Tommaso Toffoli entwarf 1980 ein universelles, reversibles Gatter, mit dem sämtliche Booleschen Funktionen verwirklicht werden können: das CCNOT gate (controlled, controlled NOT gate). Die zwei Eingangsgrößen werden direkt zwei Ausgangsgrößen zugeordnet. Das Ziel-Bit wird invertiert, wenn beide Kontroll-Bits gesetzt sind (entsprechend einer Und-Verknüpfung der beiden Kontroll-Bits).
Eingänge
Ausgänge
Kontroll-Bit 1
Kontroll-Bit 2
Ziel Bit
Kontroll-Bit 1 Out
Kontroll-Bit 2 Out
Ziel Out
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
0
1
1
1
0
1
1
0
1
1
1
1
1
1
0
Diese Funktion kann als dargestellt werden.
Da das Toffoli-Gatter universell ist, kann ein (Quanten-)Computer, der sämtliche logische Funktionen ausführen kann, allein mit Toffoli-Gattern aufgebaut werden. In Quantencomputern werden die logischen Bits durch Qubits ersetzt.
Andere Darstellungsweisen für das Toffoli-Gate:
Matrixdarstellung
Quantencomputing-Symbol
Einzelnachweise
↑Russell J. Hoppenstein:Fundamentals of Reversible Logic.A new type of logic supports high-performance computing and quantum computers.Electronic Design,5.Juni 2026,abgerufen am 10.Juni 2026(englisch).
↑R. Landauer:Irreversibility and Heat Generation in the Computing Process. In: IBM Journal of Research and Development. Band5, Nr.3, Juli 1961, S.183–191, doi:10.1147/rd.53.0183 (englisch).
↑T. Toffoli:Reversible computing. In: J. de Bakker, J. van Leeuwen (Hrsg.): International Colloquium on Automata, Languages and Programming. 1980. Band85. Springer, Heidelberg 1980, S.632–644 (englisch, springer.com[abgerufen am 10.Juni 2026]).
