Why can I use the Sum of Eigenvectors for Phase Estimation in Shor

Question

In phase estimation, we start by using an eigenvector $\newcommand{\ket}[1]{\lvert#1\rangle}\ket u$ to find the corresponding eigenvalue lambda. So far so good. In the order finding algorithm, we also use phase estimation to find the eigenvalues for the unitary $\ket{xy\bmod N}$. However, the eigenvectors/eigenvalues depend on the order $r$, which we don't know.

As a solution, textbooks note that the eigenvectors add up to $\ket1$ and then use that to initialize the phase estimation circuit.

My question is - why does that work? Why can I use the sum of eigenvectors and not just a specific eigenvector?

Answer 1

As you say, we would be able to use phase estimation if we knew the eigenvector $|u_s \rangle$ that depends on the order $r$ and the integer $s$ which is $0 \leq s \leq r - 1$. However, we don't know the eigenvector, only the superposition of them, which is $|1 \rangle$. Now, what does phase estimation result in for a superposition? It is just a superposition of estimated phases because phase estimation is ultimately a linear operator.

So if we end up with a superposition of estimated phases, then we can make our measurement which will result in the phase for one of the eigenvectors. Which one? We don't know but we know that it is of the form $\frac{s}{r}$. Why does it have this form? Because of the form of the unitary's eigenvalue: $U |u_s \rangle = \exp \left[ 2 \pi i \frac{s}{r} \right] |u_s \rangle $. Using the fact that the phase is $\frac{s}{r}$, we can use the continued fractions algorithm to calculate both $s$ and $r$ (even though we only really care about $r$).