Output register in Shor's algorithm

106 Views Asked by At

In Shor's original paper he creates two registers, sets the first to uniform superposition for each possible number $a \text{(mod $q$)}$, and then computes $x^a \text{(mod $n$)}$ into the second register. He then goes on to apply the Fourier Transform to the first register and subsequently measures it. It seems to me that the value of the second register is used at no point. In fact he writes that "it would be sufficient to observe solely the value [...] in the first register, [...]."

Thus my question, what is the second, "output" register used for at all? I've read that in later versions, one first reads the second register to collapse the first into a non-uniform superposition corresponding to the measurement, and then applies QFT. But in Shor's paper he does not do this. What is the point of the second register in the original paper?

Thank you!

1

There are 1 best solutions below

7
On BEST ANSWER

In the original paper, Shor uses the second register to compute $x^a (\mod n)$ while $a$ is kept in the first register. He mentions this allows reversibility of the modular exponentiation operation done on the second register. In the paper you provided in the link it is there in the paragraph preceding Eqn $(5.2)$.

Snippet from Shor's paper