In Shor's algorithm, how can we guarantee that each controlled-U will kickback to the same eigenvalue?

Question

I'm studying the Shor algorithm as part of my thesis and have a question about the "measured" phases after the QPE.

So, I take the controlled-U operations on the second register and in cause of phase kickback the relative phase of the controll qubit in register one will change with a multiple of the eigenvalue of $U$. I understand, that $cU$ has multiple eigenvalues with a factor $s$. How can be guaranteed that each of the controlled-Us will kickback the same eigenvalue? Or, why it is not important?

Second, if I run the controlled-U operations and make the QPE, why it is possible to get different results? I thought that the transformation between the bases is unique. So, if my controlled-U makes a specific "change" on the quibit, how it is possible that the QPE generates a superposition with specific probabilities? (e.g. in Nielsen/Chuang Box 5.4 the final measurement will give 0, 512, 1024, 1536)

Thank you for your help.

Answer 1

I understand, that cU has multiple eigenvalues with a factor s. How can be guaranteed that each of the controlled-Us will kickback the same eigenvalue? Or, why it is not important?

All the $U$s in the various controlled-$U$ are the same $U$, with the same eigenvectors and the same eigenvalues. This is part of the construction of the circuit, and provides the guarantee that you are seeking.

Second, if I run the controlled-U operations and make the QPE, why it is possible to get different results?

Remember that, for QPE, if you input an eigenvector of $U$ (and if that eigenvalue has an exact $t$-bit representation) then a $t$-bit QPE will give exactly the eigenvalue, no probabilities.

However, for Shor's algorithm, we cannot create an eigenvector - it requires knowledge of the value $s/r$, which is exactly what we're trying to find out! So, instead of inputting an eigenvector, we input $|1\rangle$, which is a superposition of several different eigenvectors. By linearity, the end result is a superposition of several different possible eigenvalues, and when we measure, the measurement just finds one of those values at random.

Answer 2

Have you seen this document? https://qiskit.org/textbook/ch-algorithms/shor.html

Note that in Shor's algorithm, we use the quantum computer as a subroutine to essentially find the period of the function

$$ f(x) = a^x mod N$$

where $a$ is a guessed value between $1$ and $N-1$. So you have to create different circuit to implement each of the guessed $a$.

---

As for the QPE step, this is essentially as follow:

Let's suppose that

$$ U|\psi\rangle = e^{2\pi i \phi} |\psi\rangle$$

then

$$U^{2^j}|\psi \rangle = U^{2^j -1}\bigg(U|\psi\rangle\bigg) = U^{2^j -1}\bigg( e^{2\pi i \phi} |\psi\rangle\bigg) = \cdots = e^{2\pi i 2^j \phi} |\psi \rangle$$

The phase-kickback turn each of the ancilla qubit (after going through Hadamard gate) from the state $\dfrac{|0\rangle + |1 \rangle}{\sqrt{2}}$ to the state $\dfrac{ |0\rangle + e^{2\pi i 2^j \phi}|1 \rangle}{\sqrt{2}}$ under $CU^{2^j}$ operator. To be mathematical precise,

$$CU^{2^j}: \bigg( \dfrac{1}{\sqrt{2}} \big( |0\rangle + |1\rangle \big) \bigg)|\psi\rangle \to \dfrac{1}{\sqrt{2}} \bigg( |0\rangle |\psi \rangle + |1\rangle e^{2\pi i 2^j \phi} |\psi\rangle \bigg) = \dfrac{1}{\sqrt{2}} \bigg( |0\rangle + e^{2\pi i 2^j \phi} |1\rangle \bigg)|\psi\rangle $$

Now if you apply the inverse QFT to all the ancilla qubit then you will get the binary expression of $\phi$.

---