Reversible Computing ist ein Rechenmodell, das nur thermodynamisch reversible Operationen zulässt. Nach dem Landauer-Prinzip, das besagt, dass das Löschen einer Information Joule Wärme freigesetzt werden, werden Übergangsfunktionen ausgeschlossen, die nicht eins zu eins sind (z. B. die Booleschen UND- und ODER-Operatoren). Es ist bekannt, dass die Quantenberechnung von Natur aus reversibel ist, da die zulässigen Operationen bei der Quantenberechnung durch einheitliche Matrizen dargestellt werden.
Bei dieser Frage geht es um Kryptographie. Inoffiziell scheint der Begriff der "Reversibilität" den grundlegenden Zielen der Kryptographie zu widersprechen, was die Frage aufwirft: "Hat die Kryptographie inhärente thermodynamische Kosten?"
Ich glaube, das ist eine andere Frage als "Kann alles in Quanten gemacht werden?"
In seinem Skript , so Dr. Preskill : „Es gibt eine allgemeine Strategie für eine irreversible Berechnung auf einem reversiblen Computer simuliert. Jedes irreversible Tor kann durch Fixieren Ein- und Ausgänge ignoriert durch ein Toffoli - Gatter simuliert werden. Wir akkumulieren und speichern alle‚Müll 'Ausgangsbits, die benötigt werden, um die Rechenschritte umzukehren. "
Dies legt nahe, dass diese reversiblen Quantensimulationen von irreversiblen Operationen eine Eingabe sowie etwas "Scratch" -Raum benötigen. Dann erzeugt die Operation eine Ausgabe zusammen mit einigen "schmutzigen" Scratch-Bits. Die Operationen sind alle in Bezug auf die Ausgabe plus Müllbits umkehrbar, aber irgendwann werden die Müllbits "weggeworfen" und nicht weiter betrachtet.
Da die Kryptographie von der Existenz von Einwegfunktionen für Traps abhängt, könnte eine alternative Aussage lauten: "Gibt es Einwegfunktionen für Traps, die mit nur umkehrbaren logischen Operationen ohne zusätzlichen Arbeitsspeicher implementiert werden können?" Wenn ja, ist es auch möglich, eine beliebige Einwegfunktion für die Falltür mit nur umkehrbaren Operationen (und ohne Leerzeichen) zu berechnen?
Antworten:
Wie ich oben in meinem Kommentar erwähnt habe und wie Sie in der Frage anspielen, kann jede Berechnung umkehrbar gemacht werden, und indem einfach die zusätzlichen Bits beibehalten werden, entstehen keine inhärenten thermodynamischen Kosten.
Jede Schaltung, die durch die Verwendung von Toffoli-Gattern und -Ancillas zum Ersetzen von irreversiblen Gattern erzeugt wird, ist genauso effizient umzukehren wie zu berechnen, vorausgesetzt, Sie haben Zugriff auf alle Ausgangsbits. Dies ist bei den in der Kryptographie betrachteten Funktionen eindeutig nicht der Fall, da viele Ancillae verwendet und verworfen werden. Durch Geheimhalten dieser zusätzlichen Bits ist es schwierig, die Berechnung rückgängig zu machen.
Indem jedoch die Funktion reversibel berechnet wird, eine Kopie der dem Ausgang entsprechenden Teilmenge von Bits erstellt wird und dann die Funktion invertiert wird, betragen die Gesamtenergiekosten für die Berechnung und Invertierung der Funktion Null, während die einzigen Kosten für die Erstellung der Funktion anfallen Kopie der Ausgabebits, die nur von der Anzahl der Ausgabebits und nicht von der berechneten Funktion abhängt. Dies ist eindeutig das Beste, was Sie tun können, da es die gleiche Energie kostet, wie das einfache Schreiben des Ausgangsstrings in ein leeres Register.
Wenden wir uns Ihrer erneuten Frage zu:
Die Antwort ist trivial nein. Wenn Sie die Inverse jedes Gatters in umgekehrter Reihenfolge anwenden, berechnen Sie die Inverse der Funktion. Unter der Annahme eines Modells, bei dem Gatter auf eine feste Anzahl von Qubits gleichzeitig einwirken, kann die Inverse jedes reversiblen Elementartors in konstanter Zeit angewendet werden. Daher ist eine solche Funktion genauso einfach zu invertieren wie zu berechnen (bis zu einer multiplikativen Konstante) und daher keine Falltürfunktion.
quelle