7
$\begingroup$

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.

enter image description here

$\endgroup$
1
4
$\begingroup$

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.)

$\endgroup$
6
  • $\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$
    – Tintin
    Nov 19 '20 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$
    – DaftWullie
    Nov 20 '20 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$
    – Tintin
    Nov 20 '20 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$
    – DaftWullie
    Nov 22 '20 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$
    – Tintin
    Dec 14 '20 at 21:32
3
$\begingroup$

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).

C-U shor

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

$\endgroup$
2
  • $\begingroup$ How do you explain why the ancilla register was put into state $|1\rangle$? $\endgroup$
    – Tintin
    Nov 18 '20 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$ Nov 18 '20 at 6:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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