可逆計算のメモ

ref:どこが面白いの？可逆計算 -- コンピューティングと北極グマ - 檜山正幸のキマイラ飼育記
上記記事を読んで適当な話をメモしておく.

そういえば量子だと観測しない限り可逆だなぁと思いました (又聞き).
あと素子自体をビリヤードみたいにするタイプの可逆計算もあった筈. これが多分フレドキン（Fredkin）ゲートみたいなものだと思う. (Billiard-ball computer - Wikipedia:enによると, Fredkin and Toffoli (1982) だそうな.)

我々は非可逆計算（例えば足し算や論理AND）に慣らされているので、のところですが, 足し算をちょっとだけ弄ると可逆にできる. Add'(x,y) = (x+y,y) みたいにインプットの片方を残しておけばよいと.

Regev05の量子帰着のところで可逆性に関して面白い話が出てくる. LWEオラクルからCVP_αオラクルを構成する. 次にこのオラクルを使って量子サンプリングを行い, 短いベクトルを得ていく. 量子サンプリングの途中, 計算結果を忘れるためにCVP_αオラクルを使うというアイデア. (短いベクトルを得るとまたそれでLWEオラクルを作ってCVP_α'オラクルを作ってと繰り返されていく.)