Quantum Phase Estimation

Introduction

Given oracular access to a unitary operator \(U\) and an eigenvector \(\psi\) of \(U\), quantum phase estimation (QPE) is about estimating the eigenvalue \(\lambda\) associated with \(U\) and \(\psi\). Since \(U\) is unitary, \(|\lambda | = 1\) and therefore \(\lambda = e^{i\theta }\) for some \(\theta\). QPE boils down to estimating \(\theta \), the phase of the eigenvalue.

QPE is used within more complex algorithms like Shor's algorithm.

Notation

We assume that \(U\) acts on \(m\)-qubit states, and denote the dimension \(2^m\) as \(M\). We'll use the (orthonormal) basis \(\{|k\rangle\}_{k=0}^{M-1}\), where \(k\) is the integer with the binary encoding of the \(n\) qubits. So \(|0 \rangle = |00...0\rangle\), \(|2\rangle = |00...10\rangle \) and \(|2^m-1\rangle = |11...1\rangle\).

Most of our focus will be on a seperate register of \(n\) qubits with dimension \(N=2^n\). We'll use the basis \(\{|k\rangle\}_{k=0}^{N-1}\) analogous to above.

The gist of it

The QPE algorithm is normally explained in the context of a quantum circuit. As we'll show below, a quantum circuit can efficiently create the \(n\)-qubit state \(\phi = \Sigma_{j=0}^{N -1}e^{j \theta i} |j\rangle \), where \(e^{\theta i}\) is the eigenvalue of \(U\).

If you are familiar with the quantum Fourier transform (QFT), you may know that it converts a \(n\)-qubit to the amplitudes of the harmonics of the frequency \(1/N\). Likewise, measuring the inverse QFT of \(\phi\) helps reveal information about \(\theta \). If this sounds like a foreign language, don't worry about it. The details will be filled in below.

Quantum circuit

The first and main portion of the circuit will create the state \(\phi \) mentioned above. The input to this circuit will be the \(n\)-qubit \(|0\rangle\) and the \(m\)-qubit \(\psi\), i.e. \(|0\otimes \psi\rangle \).

All bits of the \(n\)-qubit \(|0\rangle\) are passed through Hadamard gates, which effectively converts the \(|0\rangle\) input to \(\frac{1}{\sqrt{N}}\Sigma_{k=0}^{N-1} |k\rangle \). These \(n\)-qubits are now used as control bits for applying \(U\) repeatedly to the other \(m\) qubits, which started in state \(\psi\). The circuit diagram is provided below.

After all \(U\) operations are done, but before the inverse QFT, you may check that the state of the top \(n\) qubits is \(\phi\), while the bottom is still \(\psi\). Applying the inverse QFT to \(\phi\), the \(k\)th output bit effectively measures how much \(\theta\) has in common with the phase \(k2\pi /N\). In other words, a measurement of \(|0\rangle\) from the \(n\) qubits indicates indicates that \(\theta\) is likely close to \(0\), while a measurement of \(|4\rangle\) indicates \(\theta\) is likely closer to \(8\pi /N\). If this doesn't make sense yet, don't worry. The next section explains this.

The inverse QFT

Measuring the inverse QFT of \(\phi\) will reveal information about \(\theta\). First, let's take a simple case and assume \(\theta = 0\). In this case \(\phi = \frac{1}{\sqrt{N}}\Sigma_{k=0}^{N-1} |k\rangle \). You can check that the inverse QFT of this state is simply \(|0\rangle\).

Being slightly more general now, let's assume \(\theta\) is an integral multiple of \(2\pi / N\), i.e. \(\theta = l2\pi /N\) for some integer \(l\). In this case \(\phi = \frac{1}{\sqrt{N}}\Sigma_{k=0}^{N-1} e^{kl2\pi i/N} |k\rangle \). You can easily verify that the inverse QFT here is simply \(|l\rangle\), i.e. that the QFT of \(|l\rangle\) is \(\phi\). So if \(\theta\) is an integral multiple of \(2\pi / N\), the measurement results from the top of the ciruit will reveal the value of that multiple with perfect probability of 1.

As you might imagine by continuity, the closer \(\theta\) is to such a multiple, the larger the probability of measuring that multiple's value. For example, if \(N=8\) and \(\theta \approx 2*2\pi/8\), we'll see that the probability \(P(|2\rangle )\) is high. We'll examine this in more detail, but it will require some tedious arithmatic.

Starting with \(\phi = \Sigma_{j=0}^{N-1}e^{j \theta i} |j\rangle \) the \(k\)th component of the inverse QFT of \(\phi\) will be \(\chi_k = \frac{1}{\sqrt{N}}\Sigma_{j=0}^{N-1}e^{j \theta i}e^{-2\pi jki/N}\). Factoring out the \(j\) in the exponent, this is equivalent to

$$\chi_k = \frac{1}{\sqrt{N}}\Sigma_{j=0}^{N-1}{e^{(\theta -2\pi k/N)i}}^{j}$$

Using the formula \( \Sigma_{j=0}^N x^j = \frac{x^{N+1} -1}{x-1} \) we can simplify \(\chi_k\) as

$$\chi_k = \frac{1}{\sqrt{N}}\frac{e^{N\gamma i} -1}{e^{\gamma i} -1}$$

where \(\gamma \equiv \theta - 2\pi k/N\).

The probability \(P(k)\) of measuring \(|k\rangle\) is \(\chi_k\chi_k^*\) which is as follows.

$$P(k)=\chi_k \chi_k^* = \frac{1}{N}\frac{(e^{N\gamma i} -1)(e^{-N\gamma i} -1)}{(e^{\gamma i} -1)(e^{-\gamma i} -1)} = \frac{1-\cos N\gamma}{N(1-\cos\gamma )}$$

If you inspect this function P(k) you will find that most of the probability is focused around \(\gamma=0\) which indeed corresponds to \(\theta = 2\pi k/N \). This is what we guessed from the examples above, a measurement of \(|k\rangle\) indicates that \(\theta\) is likely close to \(2\pi k/N\).