Obliczenia odwracalne to model obliczeniowy, który pozwala jedynie na operacje odwracalne termodynamicznie. Zgodnie z zasadą Landauera, która stwierdza, że usunięcie części informacji uwalnia ciepło dżuli, wyklucza to funkcje przejścia, które nie są jeden do jednego (np. Operatory logiczne AND i OR). Powszechnie wiadomo, że obliczenia kwantowe są z natury odwracalne, ponieważ dozwolone operacje w obliczeniach kwantowych są reprezentowane przez macierze jednostkowe.
To pytanie dotyczy kryptografii. Nieformalnie pojęcie „odwracalności” wydaje się przekleństwem dla podstawowych celów kryptografii, sugerując w ten sposób pytanie: „Czy kryptografia ma nieodłączny koszt termodynamiczny?”
Uważam, że jest to inne pytanie niż: „Czy wszystko można zrobić w kwantach?”
W notatkach z wykładu dr Preskill stwierdza: „Istnieje ogólna strategia symulowania nieodwracalnego obliczenia na odwracalnym komputerze. Każda nieodwracalna brama może być symulowana przez bramę Toffoli poprzez ustalanie danych wejściowych i ignorowanie wyników. Gromadzimy i zapisujemy wszystkie śmieci „bity wyjściowe potrzebne do odwrócenia kroków obliczeń.”
Sugeruje to, że te odwracalne symulacje kwantowe nieodwracalnych operacji przyjmują dane wejściowe, a także pewną przestrzeń „zadrapania”. Następnie operacja generuje dane wyjściowe wraz z „brudnymi” zadrapaniami. Wszystkie operacje są odwracalne w odniesieniu do danych wyjściowych plus bity śmieci, ale w pewnym momencie bity śmieci są „wyrzucane” i nie są rozważane dalej.
Ponieważ kryptografia zależy od istnienia jednokierunkowych funkcji zapadni, alternatywne pytanie może brzmieć: „Czy są jakieś jednokierunkowe funkcje zapadni, które można zaimplementować przy użyciu tylko odwracalnych operacji logicznych, bez dodatkowego miejsca na zarysowania?” Jeśli tak, to czy jest również możliwe WYLICZENIE dowolnej jednokierunkowej funkcji zapadni przy użyciu tylko operacji odwracalnych (bez miejsca na zarysowania)?
Odpowiedzi:
Jak wspomniałem w moim komentarzu powyżej i jak wspominasz w pytaniu, każde obliczenie można uczynić odwracalnym, a po prostu zachowując dodatkowe bity, nie ma nieodłącznego kosztu termodynamicznego.
Każdy obwód generowany przy użyciu bramek i pomocników Toffoli w celu zastąpienia nieodwracalnych bramek staje się równie skuteczny do cofania, jak do obliczeń przy założeniu, że masz dostęp do wszystkich bitów wyjściowych. Oczywiście nie jest tak w przypadku funkcji rozważanych w kryptografii, ponieważ wiele pomocników jest używanych i odrzucanych. To trzymanie w tajemnicy tych dodatkowych bitów sprawia, że obliczenia trudno jest odwrócić.
Jednak obliczając funkcję w sposób odwracalny, wykonując kopię podzbioru bitów odpowiadającą wyjściu, a następnie odwracając funkcję całkowity koszt energii obliczenia i odwrócenia funkcji wyniesie zero, a jedynym poniesionym kosztem będzie wykonanie kopia bitów wyjściowych, która zależy tylko od liczby bitów wyjściowych, a nie od obliczanej funkcji. Jest to oczywiście najlepsze, co możesz zrobić, ponieważ kosztuje tyle samo energii, co zwykłe zapisanie ciągu wyjściowego do pustego rejestru.
Przechodząc do twojego przekształconego pytania:
Odpowiedź jest trywialnie przecząca. Jeśli zastosujesz odwrotność każdej bramki w odwrotnej kolejności, obliczymy odwrotność funkcji. Zakładając model, w którym bramki działają na określoną liczbę kubitów jednocześnie, odwrotność każdej elementarnej odwracalnej bramki może być zastosowana w stałym czasie. Tak więc taka funkcja jest tak łatwa do odwrócenia, jak do obliczenia (aż do stałej multiplikatywnej), a zatem nie jest funkcją zapadni.
źródło