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 UU and a quantum state ψ|\psi\rangle. The state ψ|\psi\rangle is the eigenstate of the operator UU, 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 UU.

Uψ=eiθψ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 UU and ψ|\psi\rangle. When we try to measure the final state, we cannot see the effect of the global phase eiθe^{i\theta} because the probabilities to measure 0s|0\rangle's or 1s|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.

Get hands-on with 1200+ tech skills courses.