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.
2 Answers
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.)
-
$\begingroup$ 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? $\endgroup$– user823Commented Nov 19, 2020 at 17:09
-
$\begingroup$ 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. $\endgroup$ Commented Nov 20, 2020 at 7:36
-
$\begingroup$ 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? $\endgroup$– user823Commented Nov 20, 2020 at 22:00
-
$\begingroup$ 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. $\endgroup$ Commented Nov 22, 2020 at 14:08
-
$\begingroup$ 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? $\endgroup$– user823Commented Dec 14, 2020 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.
-
$\begingroup$ How do you explain why the ancilla register was put into state $|1\rangle$? $\endgroup$– user823Commented Nov 18, 2020 at 4:48
-
$\begingroup$ 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. $\endgroup$ Commented Nov 18, 2020 at 6:55