Due to required reversibility, classical function [itex](f(a)=y^a \mod N)[/itex] in Shor's algorithm needs a lot of auxiliary qubits. I was afraid that their later treatment might influence the computation - and just got confirmation from Peter Shor himself: that we need to "uncompute" these auxiliary qubits. Let's look at quantum subroutine of Shor's algorithm: Hadamard gates create superposition of all (exponential number) values for input qubits. Then we perform a classical function on them, which is here: [itex]f(a)=y^a \mod N[/itex], where [itex]N[/itex] is the number we would like to factorize, [itex]y[/itex] is some chosen (usually random) number smaller than [itex]N[/itex] Then we perform measurement of value of this function [itex]f(a)=m[/itex] (random). This measurement restricts the original ensemble to only input values [itex]a[/itex], such that [itex]f(a)=m[/itex]. 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, calculation of classical function requires huge number of auxiliary qubits (~square of number of other qubits) - they are usually ignored in considerations, but there is a crucial question what finally happens with them? As measurement of value qubits has restricted the ensemble, measuring/collapse of auxiliary qubits should also affect the ensemble - this time in unwanted way. I thought maybe we could "erase them" by measuring in orthogonal basis, but Peter Shor has replied: "In order to make the factoring algorithm work properly, you need to reset all the auxiliary qubits, which started as |0⟩ at the beginning of the computation, to |0⟩ 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." Asking for literature, he replied: "Measuring the qubits in the "orthogonal basis" isn't going to work. You need to "uncompute" them. This is discussed briefly on page 9 of my paper, and in much more detail in C. H. Bennett (1973), Logical reversibility of computation." However, reversible computation of bits is just a permutation - I don't see how to "uncompute" most of them (auxiliary) to a fixed value such that the total process is still a permutation? Can it be done? How? Have you seen addressed/solved this problem in a literature?