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?
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).