quantum mechanics - Shor's algorithm - why doesn't the final collapse of the auxiliary qubits cripple the computation?

Let's look at quantum subroutine of Shor's algorithm (image source):

1. Hadamard gates create superposition of all (exponential number) values for input qubits.


2. Then we perform a classical function on them, which is here: $f(a) = y^a \textrm{ mod } N$, where $N$ is the number we would like to factorize, $y$ is some chosen (usually random) number smaller than $N$.


3. Then we perform measurement of value of this function $f(a)=m$ (random). This measurement restricts the original ensemble to only input values $a$, such that $f(a)=m$.


4. Mathematics says that this restricted ensemble has to be periodic, this period can be concluded from value of (quantum) Fourier transform, and allows to conclude the factors.

However, quantum computers require reversible/unitary operations, e.g. we cannot just use OR gate: $(x,y) \to x\ \mathrm{or}\ y$, and instead we need to use e.g. $(x, y, z) \to (x, y, z\ \mathrm{xor}\ (x\ \mathrm{or}\ y))$, which is own inverse $-$ but which requires one additional auxiliary qubit initialized as $z=0$. So their required number is comparable with the number of gates of the classical function - can be quite large.

But what's happening with all these auxiliary qubits at the end of computation, and after the computation is over?

Measuring the classical function has led to the crucial restriction of the original ensemble - can we ensure that auxiliary qubits aren't finally also measured/collapsed, also restricting the ensemble?

Is there some time interval when such measurement restricts the ensemble? (Analogously: required time order between QFT and measurement of classical function?)

If not, can we ensure that restriction from (inevitable?) collapse of auxiliary qubits does not cripple our computation?

---

Peter Shor has confirmed (below) the problem with auxiliary qubits, requiring to "uncompute" them to fixed values for proper computation process.

Answer

In the factoring algorithm, there are three kinds of qubits. In the OP's notation, there are "input qubits", which start in a superposition of all possible values, and which you eventually take the Fourier transform of. There are "value qubits", in which you compute the function $y^a \pmod{N}$, where $a$ is the value in the input qubits. And there are "auxiliary qubits", which you use as workspace to help do this computation.

In order to make the factoring algorithm work properly, you need to reset all the auxiliary qubits, which started as $|0\rangle$ at the beginning of the computation, to $|0\rangle$ at the end of the computation. This is called "uncomputing" these qubits. (Actually, you can set them to anything you please as long as it is a constant independent of the workings of the algorithm.) Theorems about reversible classical computation ensure that it is possible to do this.

If you reset the auxiliary qubits to $|0\rangle$, then if the environment, or somebody, measures them, nothing is revealed about the computation, and the computation is not "crippled". If you forget to reset them to $|0\rangle$, you probably won't get the right answer, whether or not anybody measures them.