Co jest wadliwe w metodzie odwracalnego obliczania „zapisz dane”?

9

Jestem studentem, który dopiero zaczyna czytać o komputerach zwrotnych. Wiem, że z powodu zasady Landauera nieodwracalne obliczenia rozpraszają ciepło (a odwracalne tego nie robią). Porozmawiałem o tym z moim profesorem, który nigdy wcześniej nie słyszał o komputerach zwrotnych, a on miał trudności ze zrozumieniem, dlaczego teoria komputerów zwrotnych nie była trywialna.

Chodziło tylko o to, że zawsze można zapisać dane wejściowe, tj. Dla dowolnej funkcji f:{0,1}n{0,1}n że chcesz uczynić odwracalną, zdefiniuj nową funkcję freversible:{0,1}n{0,1}2n (lub {0,1}2n{0,1}2n i po prostu umieściłeś 0s na ostatni n bitów wejścia), który zwraca wynik w pierwszym n bity i dane wejściowe w drugim nbitów Następnie w celu odwróceniafreversible po prostu odrzucasz dane wyjściowe i zwracasz zapisane dane.

Moje bezpośrednie zastrzeżenie było takie, że zajmuje to więcej pamięci niż pierwotna funkcja - choć tylko ze względu na stały czynnik. Ograniczenie wyjścia donbity wydają się jednak przywracać ciekawość problemu. Czy to zwykle oznacza przetwarzanie odwracalne?

Kolejnym zastrzeżeniem było to, że kiedy odrzucamy moc wyjściową, robimy coś nieodwracalnego, co rozproszy ciepło. Ale prawidłowo odzyskaliśmy stan początkowy, więc jak może być nieodwracalny? Nie znam wystarczającej fizyki, aby zrozumieć, czy ważną rzeczą w / r / t ciepła jest tylko odwrócenie całego obliczenia, czy też każdy krok musi być odwracalny, czy też ten pomysł jest po prostu niewłaściwy .

Eli Rose - REINSTATE MONICA
źródło

Odpowiedzi:

12

Istnieją dwie ważne cechy obliczeń odwracalnych, których brakuje w dyskusji na temat obliczeń odwracalnych:

  1. Odwracalną funkcją musi być bijection, i
  2. Odwracalność jest definiowana na poziomie bram lokalnych, a nie tylko na poziomie globalnym.

W szczególności w przypadku rozszerzenia {0,1}n{0,1}n w {0,1}2n{0,1}2n kopiując, nie zapewnisz wstrzyknięcia, ponieważ nie wyjaśnisz, co się stanie, gdy nastąpi ostatni n bity wejściowe dla twojej funkcji nie są 0n.

Jeśli chodzi o drugi punkt, jest to naprawdę istotna część obliczeń odwracalnych z perspektywy fizyki. Proces fizyczny nie może po prostu „cofnąć” ogrzewania na poziomie globalnym, dlatego każda bramka musi być odwracalna, aby obwód był odwracalny w sensie istotnym dla fizyki.

Wreszcie teoria obliczeń odwracalnych nie jest nadmiernie skomplikowana, ale zdecydowanie nie jest trywialna. W szczególności istnieją pewne obwody, które można zaimplementować za pomocą mniejszej liczby rejestrów / przewodów nieodwracalnych niż mogą być odwracalne. Jednak przyspieszenie przejścia od nieodwracalnego do odwracalnego nie jest takie złe.

Ogólnie rzecz biorąc, rzadko słyszę, że obliczenia odwracalne pojawiają się na klasycznych kursach CS, ponieważ rzadko dotyczą one obliczeń klasycznych. Jest to jednak ważny temat w obliczeniach kwantowych, ponieważ wszystkie obwody kwantowe są odwracalne i ponieważ należy ostrożnie obchodzić się z przewodami „śmieciowymi”, aby uniknąć niepotrzebnego splątania.

Artem Kaznatcheev
źródło
Aha. Więc jakie jest formalne stwierdzenie „każda brama musi być odwracalna” - czy wymaga wstrzykiwania funkcji przejścia maszyny Turinga?
Eli Rose - REINSTATE MONICA
2
Odwracalne przetwarzanie @EliRose jest zdefiniowane w modelu bramy, a nie w modelu TM. Nie jestem pewien, czy w modelu TM istnieje rozsądna definicja, ale prawdopodobnie wymagałoby to przynajmniej kontroli skończonej, aby była odwracalna. Odwracalne bramy oznaczają coś w rodzaju bramy Toffoli .
Artem Kaznatcheev
1
@ArtemKaznatcheev: co z odwracalnymi maszynami Turinga (łącze PDF) wprowadzonymi przez Bennetta?
Niel de Beaudrap
Obwody kombinatoryczne można łatwo obsługiwać za pomocą odwracalnej logiki, ale wszystkie przydatne urządzenia komputerowe wymagają sprzężenia zwrotnego. Można by użyć bramki Toffoli, aby obliczyć „A, a nie B”, a dwie takie bramki mogłyby zostać użyte do zbudowania zatrzasku, ale po umieszczeniu sprzężenia zwrotnego okno odwraca się.
supercat
co z kwantowymi TM, których dopuszczalne amplitudy mogą wynosić tylko 0 lub 1. To wydaje się rozsądnym sposobem na zdefiniowanie odwracalnej TM.
Marcos Villagra