Apa yang salah tentang metode “save-the-input” dari komputasi reversibel?

Saya seorang sarjana baru mulai membaca tentang komputasi reversibel. Saya tahu bahwa, karena prinsip Landauer, perhitungan yang ireversibel menghilangkan panas (dan yang reversibel tidak). Saya membahasnya dengan profesor saya, yang belum pernah mendengar tentang komputasi reversibel sebelumnya, dan dia mengalami kesulitan memahami mengapa teori komputasi reversibel tidak sepele.

Maksudnya adalah Anda selalu dapat menyimpan input, yaitu untuk fungsi apa saja yang ingin Anda balikan, tentukan fungsi baru (atau dan Anda hanya memasukkan s untuk bit terakhir dari input) yang mengembalikan output dalam bit pertama dan input dalam bit lainnya. Kemudian untuk membalikkan Anda hanya membuang output dan mengembalikan input yang Anda simpan.f r e v e r s i b l e : { { 0 , 1 } 2 n → { 0 , 1 } 2 n 0 n n n f r e v e r s i b l $f: \{ 0, 1 \}^n \rightarrow \{ 0, 1 \}^n$$f_{reversible}: \{ 0, 1 \}^n \rightarrow \{0, 1 \}^{2n}$$\{ 0, 1 \}^{2n} \rightarrow \{0, 1 \}^{2n}$$0$$n$$n$$n$$f_{reversible}$

Keberatan saya adalah bahwa ini membutuhkan lebih banyak memori daripada fungsi aslinya - meskipun hanya dengan faktor konstan. Membatasi output ke bit akan mengembalikan keunikan masalahnya. Apakah ini yang biasanya dimaksud dengan komputasi reversibel?$n$

Keberatan lain tampaknya ketika kita membuang output, kita melakukan sesuatu yang tidak dapat diubah yang akan menghilangkan panas. Tapi kami benar memulihkan keadaan awal, jadi bagaimana bisa itu tidak dapat dikembalikan? Saya tidak tahu cukup fisika untuk memahami apakah yang penting w / r / t panas hanya untuk seluruh perhitungan menjadi reversibel, atau apakah setiap langkah perlu reversibel juga, atau jika ide ini hanyalah pohon yang salah .

Ada dua fitur penting dari komputasi reversibel yang hilang dari diskusi Anda tentang komputasi reversibel:

1. Fungsi yang dapat dibalik harus merupakan suatu penambangan, dan
2. Reversibilitas didefinisikan pada tingkat gerbang lokal, bukan hanya tingkat global.

Khususnya, untuk ekstensi Anda dari menjadi dengan menyalin, Anda tidak memastikan bijih karena Anda tidak menjelaskan apa yang terjadi ketika bit input terakhir untuk fungsi Anda bukan . { 0 , 1 } 2 n → { 0 , 1 } 2 n n 0 $\{0,1\}^n \rightarrow \{0,1\}^n$$\{0,1\}^{2n} \rightarrow \{0,1\}^{2n}$$n$$0^n$

Adapun poin kedua, itu benar-benar bagian penting dari komputasi reversibel dari perspektif fisika. Proses fisik tidak bisa sekadar "membatalkan" pemanasan pada tingkat global, sehingga setiap gerbang harus dapat dibalik agar sirkuit dapat dibalikkan dalam pengertian yang relevan dengan fisika.

Akhirnya, teori komputasi reversibel tidak terlalu rumit, tetapi jelas tidak sepele. Secara khusus, ada beberapa sirkuit yang dapat diimplementasikan dengan register / kabel yang lebih sedikit secara non-reversibel daripada yang dapat dibalik. Namun, ledakan dari non-reversibel ke reversibel tidak terlalu buruk.

Secara umum, saya jarang mendengar komputasi reversibel muncul dalam kursus CS klasik, karena jarang relevan dengan perhitungan klasik. Namun, ini adalah topik penting dalam komputasi kuantum karena semua sirkuit kuantum dapat dibalik dan karena seseorang harus menangani apa yang ada di kabel 'sampah' Anda dengan hati-hati untuk menghindari keterikatan yang tidak perlu.