Quantum Phase Estimation

The phase estimation problem

Before we directly address the factorization problem that we solve using Shor’s algorithm, we will take a slight detour and look at a different problem. Don’t worry if you are not sure how these things are related at this point.

Let’s understand the quantum phase estimation (QPE) problem with a simple example. Let’s say we have a unitary operator $U$ and a quantum state $|\psi\rangle$. The state $|\psi\rangle$ is the eigenstate of the operator $U$, so when the operator is applied to the state, instead of modifying the state and its components, only a phase is applied to it. The phase can be from -1 to +1 and anything in between. In terms of Linear Algebra, the vector $|\psi\rangle$ is the eigenvector of unitary matrix $U$.

$$U|\psi\rangle = e^{i\theta}|\psi\rangle$$

The question is to find the value of the phase $\theta$ that has been applied to the quantum state $|\psi\rangle$. We can assume we already have $U$ and $|\psi\rangle$. When we try to measure the final state, we cannot see the effect of the global phase $e^{i\theta}$ because the probabilities to measure $|0\rangle's$ or $|1\rangle's$ haven’t changed. This doesn’t help us much, so let’s try to figure out how else we could find this phase $\theta$.