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

Phase kickback

We come back to the technique we’ve been exploiting all this time. If we cannot get information about $\theta$ from the global phase, why not turn it into a relative phase of another qubit(s) using phase kickback? We know that relative phases do have an impact that we can see upon measurement. Recall the effect of a CNOT gate on $|+\rangle$ and $|-\rangle$. This gives us a hint that we need a controlled operation, so let’s create a controlled version of the $U$ operator, called $C-U$ gate.

Basic solution

Let’s try to understand what’s going on by following the circuit step by step.

$$|\phi_0\rangle = |\psi\rangle|0\rangle$$

We apply the Hadamard gate on our ancilla. This will help us encode the phase information in a relative phase in the superposition of the ancilla qubit.

$$|\phi_1\rangle = |\psi\rangle H|0\rangle$$

$$|\phi_1\rangle = \frac{|\psi\rangle|0\rangle + |\psi\rangle|1\rangle}{\sqrt2}$$ ...