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

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)

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.

• thank you, that was the part I not understand. But, refer to this link we see the transformation between computational basis and Fourier basis. Are the qubits before QPE already in superposition in Fourier basis? Or why we get different values after the QPE? Oct 12 '20 at 8:43
• If you supplied an eigenvector, the qubits before the fourier transform would be in the fourier basis. So, when we don't supply an eigenvector, they're in a superposition of states in the fourier basis. Oct 12 '20 at 8:55

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

• Yes, I have studied the documents. My problem which I not understand is: How are the qubits "designed" after $H$ and $U^{2^j}$ and measurement of the second register? If i plot the Bloch, there still in $|+\rangle$. Is this because of the superposition over all possible $\theta$ and they sum up to $|+\rangle$ before QFT? Nov 10 '20 at 12:25