What is Quantum Phase Estimation in Shor's Algorithm?

Question

While I'm studying Algorithm, I couldn't understand what Quantum Phase Estimation is. And I heard there is relation between Phase-Kickback and Quantum Phase Estimation. I wonder what it is. Also, I'm not sure what this is and how it works within the algorithm. I would like to learn from the mathematical point of view and the conceptual part.

Answer 1

Phase estimation is the process by which you are given a controlled-$U$ unitary, and a state that you are promised is an eigenvector of $U$ with eigenvalue $e^{2\pi ix/2^t}$, then you can use a $t$-qubit register to affect the change $$ |0\rangle^{\otimes t}|u\rangle\mapsto|y\rangle|u\rangle. $$ If $x$ is in integer, then the outcome is guaranteed to be $y=x$. If $x$ is not an integer, $y$ is, with high probability, the closest integer to $x$.

The phase-kickback is the way that we get something, apparently on the second register (i.e. the $|u\rangle$ being acted upon by $U$) to change the first register. In effect, this is making use of the difference between global phase (as it would be for $U$) and relative phase in a superposition (which is what you actually get when you use controlled-$U$).

Before I go into the detailed mathematics, what have you read so far (as this is standard in all texts)? What is it you don't understand?

Answer 2

If you want to learn more generally about phase estimation, the book I am helping write has a whole chapter on it, Learn Quantum Computing with Python and Q# (chapter 8). Ping me here or via email and I can get you a discount code!