# Shor's algorithm: initialization of second register

I am trying to understand Shor's algorithm. I am not quite sure why the initialization, indicated as $$|1\rangle$$ in the below image at the bottom left is chosen as it is? I understand the modular exponentiation method in principle, but I am not sure which initialization should be chosen.

For preference, in a phase estimation algorithm, you would set the state of the second register equal to an eigenstate of the unitary operator $$U$$, the plan being to find its eigenvalue, which depends on the period $$r$$. In fact, any of the eigenvectors $$|u_s\rangle$$ would do for values $$s=0,1,\ldots r-1$$ as these have eigenvalues related to $$s/r$$.

However, the eigenstates themselves depend on $$r$$, so without knowing $$r$$, you cannot make the eigenstate, and so you cannot find $$r$$. That's a problem.

The way to circumvent the problem is that you can prepare the state $$|1\rangle$$, and it turns out that this state is an equal superposition of all the vectors $$|u_s\rangle$$. Using linearity, you now know the outcome - an equal superposition of the estimates of the different eigenvalues (entangled with the second register). Thus, in effect, what the phase estimation does is it measures one of the $$s/r$$ eigenvalues at random (with equal probability). (You then use the continued fractions algorithm to figure out which $$s$$ it was.)

• I understand now in principle, but why is that in the second (lower) register, the lowermost qubit is denoted $|1\rangle$ and not the uppermost qubit in the lower register? – Tintin Nov 19 '20 at 17:09
• It is that the entire register, when converted from binary to decimal, represents the number 1. It's not the state of a single qubit. – DaftWullie Nov 20 '20 at 7:36
• Why do some sources like Wikipedia en.wikipedia.org/wiki/Shor's_algorithm, or more profoundly Lomonaco, S., arxiv.org/pdf/quant-ph/0010034.pdf, not mention this eigenvector preparation of the second register? – Tintin Nov 20 '20 at 22:00
• Typically, there are two approaches to demonstrating Shor's algorithm: (i) build up from phase estimation, using eigenvector inputs, then make the jump to an input that is a superposition of eigenvectors. I believe this method gives the most understanding , or (ii) just happen to pick some particular input state, work though the calculation by brute force, and see that it magically works. It's a valid pedagogical option that comes down to author's choice. – DaftWullie Nov 22 '20 at 14:08
• how can Shor's algorithm in the case of (ii) work if we do not start with |1> as an input to the second register? – Tintin Dec 14 '20 at 21:32

The initial state of Shor's algorithm is $$\frac{1}{\sqrt N}\displaystyle\sum_{a=0}^{N-1}|a\rangle$$, and it is OK to move this state to $$\frac{1}{\sqrt N}\displaystyle\sum_{a=0}^{N-1}|a,x\rangle$$ as our initial state since the modular exponentiation takes $$x$$ as one of its input.

Here shows the model of a $$\text{controlled}-U$$ gate, and a circuit for factoring (figure comes from this paper).

So I think the $$|x\rangle$$ denoted here directs to $$|x\rangle$$, although I do not know why they are doing so.

• How do you explain why the ancilla register was put into state $|1\rangle$? – Tintin Nov 18 '20 at 4:48
• Which part do you refer to as the ancilla? The $|1>$ state in the figure should be the second input quantum register and the ancilla is kept hidden. – Yitian Wang Nov 18 '20 at 6:55

Look at this part https://qiskit.org/textbook/ch-algorithms/shor.html#2.-The-Solution . The last box you can expand is the answer to your question. All eigenstates sum up to $$|1\rangle$$.

Maybe somebody can explain how these calculus works?