Before discussing application to such hard problems as simulating brains, I would like to see an example of a short irreversible program, it reversible equivalent, and a trace through running each one that demonstrates the advantage of the reversible program.
I want to calculate f^128(X) (mod N), where f is a polynomial and f^128 is f composed with itself 128 times.
First I calculate f(X) (mod N). Now my workspace is:
X, f(X), garbage.
I copy out the f(X) to some scratch space. Now my workspace is:
X, f(X), garbage, f(X).
Now I reverse my original computation to clear the garbage.
X, 0, 0, f(X).
Now I repeat this process to compute f(f(X)).
X, f(f(X)), garbage, f(X).
Now copy out f(f(X)) and uncompute.
X, 0, 0, f(X), f(f(X)).
Now I repeat my calculation of f(X), but backwards.
X, 0, 0, 0, f(f(X)).
Now I repeat my computation of f(f(X)), but starting from f(f(X)) instead of from X.
X, 0, 0, 0, f(f(X)), f(f(f(f(X))))
Now I reverse my computation of f(f(X)):
X, 0, 0, 0, 0, f(f(f(f(X))))
And so on.
I end up with
X, 0, 0, 0, 0, 0, 0, 0, 0, 0, f^128(X).
after about 2100 steps.
I’ve used 11 times more memory than required to compute f. But on the flipside, I’ve generated no waste heat, while just applying f over and over again would have generated 128 times the waste heat required to compute f.
1. First I calculate f(X) (mod N). Now my workspace is:
X, f(X), garbage-1.
2. I copy out the f(X) to some scratch space. Now my workspace is:
X, f(X), garbage-2, f(X).
3. Now I reverse my original computation to clear the garbage.
X, 0, 0, f(X).
Is garbage-1 the same as garbage-2? If so, how do you copy f(X) in step 2 without introducing more garbage? If not, how do you reverse the computation in step 3?
Before discussing application to such hard problems as simulating brains, I would like to see an example of a short irreversible program, it reversible equivalent, and a trace through running each one that demonstrates the advantage of the reversible program.
I want to calculate f^128(X) (mod N), where f is a polynomial and f^128 is f composed with itself 128 times.
First I calculate f(X) (mod N). Now my workspace is:
X, f(X), garbage.
I copy out the f(X) to some scratch space. Now my workspace is:
X, f(X), garbage, f(X).
Now I reverse my original computation to clear the garbage.
X, 0, 0, f(X).
Now I repeat this process to compute f(f(X)).
X, f(f(X)), garbage, f(X).
Now copy out f(f(X)) and uncompute.
X, 0, 0, f(X), f(f(X)).
Now I repeat my calculation of f(X), but backwards.
X, 0, 0, 0, f(f(X)).
Now I repeat my computation of f(f(X)), but starting from f(f(X)) instead of from X.
X, 0, 0, 0, f(f(X)), f(f(f(f(X))))
Now I reverse my computation of f(f(X)):
X, 0, 0, 0, 0, f(f(f(f(X))))
And so on.
I end up with
X, 0, 0, 0, 0, 0, 0, 0, 0, 0, f^128(X).
after about 2100 steps.
I’ve used 11 times more memory than required to compute f. But on the flipside, I’ve generated no waste heat, while just applying f over and over again would have generated 128 times the waste heat required to compute f.
Is garbage-1 the same as garbage-2? If so, how do you copy f(X) in step 2 without introducing more garbage? If not, how do you reverse the computation in step 3?
You can copy something reversibly (into fresh memory) without creating garbage by a using a CNOT (controlled not).