I've read that the measurement of the ancilla qubits is not fundamental for Shor's algorithm, but I don't understand how the algorithm works if I remove it.
Without those measurements, do I have $r$ possible different outputs (all with the same probability) as I have for the Shor's algorithm with the measurement in the second quantum register?
Without loss of generality your question could also be phrased as "what would I measure in the bottom, second register if I waited to measure the second register until after performing the QFT on the upper first register?" In that case it might be seen that measuring the second register only affects the (unmeasurable) global phase of the system.
To answer directly your question, you get the same probabilities for measuring $r$ in the first register after performing the QFT of the first register, whether you measure the second register before the QFT, after the QFT, or never.
To quote from Kuperberg on Shtetl-Optimized:
- You can measure the output qubits.
- The janitor can fish the output qubits out of the trash and measure them for you.
- You can secretly not measure the output qubits and say you did.
- You can keep the output qubits and say you threw them away.
Measuring the output qubits wins you the purely mathematical convenience that the posterior state on the input qubits is pure (a vector state) rather than mixed (a density matrix). However, since no use is made of the measured value, it truly makes no difference for the algorithm.
