Synthese reversibler Logikschaltungen

Reversible oder informationsverlustfreie Schaltungen finden Anwendungen in der digitalen Signalverarbeitung, Kommunikation, Computergrafik und Kryptographie. Sie sind auch eine grundlegende Anforderung im aufkommenden Bereich der Quantenberechnung. Wir untersuchen die Synthese reversibler Schaltungen, die eine minimale Anzahl von Gattern verwenden und keine redundanten Eingangs-Ausgangs-Leitungs-Paare (temporäre Speicherkanäle) enthalten. Wir beweisen konstruktiv, dass jede gerade Permutation ohne temporären Speicher unter Verwendung von NOT-, CNOT- und TOFFOLI-Gattern implementiert werden kann. Wir beschreiben einen Algorithmus zur Synthese optimaler Schaltungen und untersuchen die reversiblen Funktionen auf drei Drähten, wobei wir die Verteilung der Schaltungsgrößen berichten. Wir studieren auch kanonische Schaltungdekompositionen, bei denen Gatter der gleichen Art zusammengefasst werden. Schließlich synthetisieren wir in einer für die Quantenberechnung wichtigen Anwendung Orakel-Schaltungen für Grovers Suchalgorithmus und zeigen eine erhebliche Verbesserung gegenüber einem zuvor vorgeschlagenen Synthesealgorithmus.