Measuring ancillas in Shor's algorithm

Question

When considering Shor's algorithm, we use ancilla qubits to effectively obtain the state $$\sum_x \left|x,f(x)\right>$$ for the function $f(x) = a^x \mod N$.

As I have learned it, we then measure the ancilla qubits, to obtain, say $f(x) = b$ and get the state $$\sum_{x\mid f(x) = b} \left|x,f(x)\right>.$$

Then applying a QFT will give the period. However, I think that the measurement of the ancilla qubits is not necessary, in order to be able to apply the QFT (or its inverse for that matter) and do a measurement to obtain the period.

Is that correct? Is it necessary to measure the ancilla qubits in Shor's algorithm?

Answer 1

Is that correct? Is it [not] necessary to measure the ancilla qubits in Shor's algorithm?

Correct, it is not necessary to measure the ancillae.

This is easily seen by appealing to the no-communication theorem. If measuring the ancillae could affect the success of the algorithm, you could communicate faster-than-light by starting the algorithm many times, giving the ancillae to Alice, sending her far away, have her encode a bit by measuring or not measuring the ancillae, then having Bob measure how often the factoring was succeeding to read out the bit.

Another way to see that this works is by simulating it. From the results you can see that, as soon as the modular-exponentiation into the ancillae has happened, the density matrix of the input has been decohered in a very particular periodic way. And that the inverse QFT of this decohered density matrix has magnitude spikes at the correct places:

Notice that this is all in place even though the ancillae were not measured. Measuring them changes none of the density matrices.