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?

  • $\begingroup$ This is a good question, although versions of it have been asked before. Is your question distinguished over this one in particular? I like to ponder Alice giving those qubits to her friend Bob, who assures her that he will measure them but then goes off to his corner and secretly throws the qubits away. $\endgroup$ Commented Jan 12, 2022 at 0:06
  • $\begingroup$ @MarkS Thank you. My question came in my mind after reading that question actually. I thought that the measurement was fundamental for the algorithm, and there it is said that is not fundamental and why. But I do not undersand how the algorithm works if I remove it, since all the math I've seen about Shor's algorithm uses that measurement. Thank you again. $\endgroup$
    – stopper
    Commented Jan 12, 2022 at 10:15

1 Answer 1


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:

  1. You can measure the output qubits.
  2. The janitor can fish the output qubits out of the trash and measure them for you.
  3. You can secretly not measure the output qubits and say you did.
  4. 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.

  • 3
    $\begingroup$ The quote made my day! Thanks! The core of the confusion here seems to be the difference between measuring a system and discarding it. I recently encountered a nice take on the latter in "Picturing Quantum Processes" by @Bob Coecke and Aleks Kissinger: If the output of a process is discarded, it may as well have never happened. I suppose this encompasses "or something else could have happened in its place" which includes the fishing, the janitor and the lies. $\endgroup$ Commented Jan 12, 2022 at 18:35
  • $\begingroup$ "Picturing Quantum Processes" looks beautiful, thanks! $\endgroup$ Commented Jan 12, 2022 at 19:34

Not the answer you're looking for? Browse other questions tagged or ask your own question.