In this module, we will work towards understanding and implementing the Quantum Phase Estimation subroutine. The QPE subroutine and the QFT are the elementary building blocks for larger quantum algorithms such as Shor's algorithm for factoring numbers, the Harrow-Hassidim-Lloyd (HHL) algorithm for solving linear systems of equations, and algorithms for finding the ground state energy of a molecule. In earlier nodes, we encountered both *relative* and *global* phases. *Global* phases do not affect measurement outcome probabilities at all and, as such, are *unobservable*; whereas *relative* phases can affect measurement outcomes if measured in a different basis.

But what if we had a situation where we *did* want to figure out the global phase. Could we do so? This problem corresponds to figuring out the eigenvalue of a unitary operator corresponding to a given eigenvector. The action of a unitary operator $U$ on its eigenvector $\vert \psi \rangle$ is $$ U \vert \psi \rangle = e^{2\pi i \theta} \vert \psi \rangle, \tag{1} \label{eq:unitary} $$ where $e^{2\pi i \theta}$ is an eigenvalue with a unit norm, which appears as a *global* phase in the output. Let us prove that introducing a global phase to the output does not change the measurement outcomes. --- ***Exercise P.1.1.*** Prove that the expectation value of any observable $\mathcal{O}$ given any $\vert \psi \rangle$ is the same as the expectation of $\mathcal{O}$ given $\vert \widetilde{\psi} \rangle = e^{2 \pi i \theta} \vert \psi \rangle$.

Hint.

The expectation value of an observable is defined as follows: $$ \langle \mathcal{O} \rangle_{\psi} = \langle \psi \vert \mathcal{O} \vert \psi \rangle. $$

Solution.

We are given $$ \langle \mathcal{O} \rangle_{\psi} = \langle \psi \vert \mathcal{O} \vert \psi \rangle, $$ and $$ \vert \widetilde{\psi} \rangle = e^{2 \pi i \theta} \vert \psi \rangle. $$ The expectation of $\mathcal{O}$ is $$ \begin{align} \langle \mathcal{O} \rangle_{\widetilde{\psi}} &= \langle \widetilde{\psi} \vert \mathcal{O} \vert \widetilde{\psi} \rangle \\ &= \langle \psi \vert e^{-2 \pi i \theta} \mathcal{O} e^{2 \pi i \theta} \vert \psi \rangle \\ &= \langle \psi \vert e^{-2 \pi i \theta} e^{2 \pi i \theta} \mathcal{O} \vert \psi \rangle \\ & = \langle \psi \vert \mathcal{O} \vert \psi \rangle \\ & = \langle \mathcal{O} \rangle_{\psi}. \end{align} $$

▢

--- The QPE subroutine estimates the global phase introduced when a unitary is applied to one of its eigenvectors. For the QPE subroutine, we assume that we have the ability to prepare $\vert \psi \rangle$ and apply $U$. We will now prove a few properties of unitary matrices that are fundamental to understanding the QPE algorithm. --- ***Exercise P.1.2.*** (a) Show that all eigenvalues of a unitary matrix, $U$, are complex numbers with a norm of 1.

Solution.

By definition, for a unitary matrix $U$, $$ U U^{\dagger} = U^{\dagger} U = I. $$ Suppose that $\lambda$ is an eigenvalue of $U$ such that $$ U\vert \psi \rangle = \lambda \vert \psi \rangle. \tag{2} \label{eq:eigenstate} $$ Taking the conjugate transpose, we have $$ \begin{align} (U\vert \psi \rangle)^{\dagger} &= \langle \psi \vert U^{\dagger} \\ &= \langle \psi \vert \lambda^{*} \tag{3} \label{eq:conjugate} \end{align} $$ Multiplying Eq.($\ref{eq:conjugate}$) with Eq.($\ref{eq:eigenstate}$) we get $$ \begin{align} \langle \psi \vert U^{\dagger} U \vert \psi \rangle &= \langle \psi \vert \lambda^{*} \lambda \vert \psi \rangle \\ & = \vert \lambda \vert^2 \langle \psi \vert \psi \rangle. \end{align} $$ Since $U^{\dagger} U = I$, $$ \begin{align} \langle \psi \vert \psi \rangle & = \vert \lambda \vert^2 \langle \psi \vert \psi \rangle. \end{align} $$ As $\langle \psi \vert \psi \rangle = 1$ for normalized quantum states, it follows that $$ \vert \lambda \vert^2 = 1. $$ Thus, all eigenvalues of a unitary matrix have a magnitude of $1$, and are in general complex. ▢

(b) Show that the eigenvectors of a unitary matrix are orthogonal to each other.

Solution.

Suppose we have two distinct eigenvalues, $\lambda_1$ and $\lambda_2$, corresponding to two eigenvectors of a unitary matrix $U$, $\vert \psi_1\rangle$ and $\vert \psi_2\rangle$ respectively: $$ \begin{aligned} U\vert \psi_1 \rangle &= \lambda_1 \vert \psi_1 \rangle, \\ U\vert \psi_2 \rangle &= \lambda_2 \vert \psi_2 \rangle. \\ \end{aligned} $$ Since $U$ is a unitary matrix, we also have $UU^{\dagger} = U^{\dagger}U = I $. Then, $$ \begin{align} \langle \psi_1 \vert \psi_2 \rangle &= \langle \psi_1 \vert U^{\dagger} U\vert \psi_2 \rangle \\ &= \left( \langle \psi_1 \vert U^{\dagger} \right) \left( U\vert \psi_2 \rangle \right) \\ &= \left( U\vert\psi_1 \rangle \right)^{\dagger} \left( U\vert \psi_2 \rangle \right) \\ &= \left( \lambda_1\vert\psi_1 \rangle \right)^{\dagger} \left( \lambda_2\vert \psi_2 \rangle \right) \\ &= \langle \psi_1 \vert \lambda_1^{*} \lambda_2\vert \psi_2 \rangle \\ &= \lambda_1^{*} \lambda_2 \langle \psi_1 \vert \psi_2 \rangle \end{align} $$ Therefore, $$ \begin{align} \langle \psi_1 \vert \psi_2 \rangle - \lambda_1^{*} \lambda_2 \langle \psi_1 \vert \psi_2 \rangle & = 0 \\ (1 - \lambda_1^{*} \lambda_2) \langle \psi_1 \vert \psi_2 \rangle &= 0. \end{align} $$ If we assume $(1 - \lambda_1^{*} \lambda_2) = 0$, then, $$ \lambda_1^{*} \lambda_2 = 1. $$ Multiplying the equation by $\lambda_1$, we get $$ \begin{align} \lambda_1\lambda_1^{*} \lambda_2 &= \lambda_1 \\ \lvert\lambda_1\rvert^2 \lambda_2 &= \lambda_1 \\ \lambda_2 &= \lambda_1, \end{align} $$ since the magnitude of an eigenvalue of a unitary matrix is $1$. Therefore, for the condition $(1 - \lambda_1^{*} \lambda_2) = 0$ to be satisfied, $\lambda_2$ has to be the same as $\lambda_1$. Therefore, if $\lambda_1 \neq \lambda_2$, $(1 - \lambda_1^{*} \lambda_2) \neq 0$, we must have that $\langle \psi_1 \vert \psi_2 \rangle = 0$, i.e., the eigenvectors are orthogonal to each other. ▢

--- Since the eigenvectors form an orthonormal set, all unitary matrices can be written in a *diagonal representation* or an *orthonormal decomposition* (or equivalently, a *spectral decomposition*) $$ U = \sum_\lambda e^{2 \pi i\theta_\lambda} \vert \psi_\lambda \rangle \langle \psi_\lambda \vert, \label{eq:spectral} \tag{4} $$ where $e^{2 \pi i\theta_\lambda}$ is an eigenvalue of the eigenvector $\vert \psi_\lambda \rangle$. --- ***Exercise P.1.3.*** Write the $T$ gate and the $X$ gate in terms of their eigenbases in the form of Eq.($\ref{eq:spectral}$).

Solution.

The eigenvalues of the $T$ gate are ${1, e^{\frac{i\pi}{4}}}$. Its corresponding eigenvectors are $\left( \vert 0 \rangle = \begin{bmatrix} 1 \\ 0\end{bmatrix}, \vert 1 \rangle = \begin{bmatrix} 0 \\ 1\end{bmatrix}\right)$. Therefore, we can write, $$ \begin{align} T &= 1 \vert 0 \rangle \langle 0 \vert + e^{\frac{i\pi}{4}} \vert 1 \rangle \langle 1 \vert, \\ &= 1\begin{pmatrix} 1 & 0 \\ 0 & 0 \end{pmatrix} + e^{\frac{i\pi}{4}}\begin{pmatrix} 0 & 0 \\ 0 & 1 \end{pmatrix}, \\ & = \begin{pmatrix} 1 & 0 \\ 0 & e^{\frac{i\pi}{4}} \end{pmatrix}. \end{align} $$ The eigenvalues of the $X$ gate are $1$ and $-1$ with eigenvectors $ \vert + \rangle = \frac{1}{\sqrt 2}\begin{bmatrix} 1 \\ 1 \end{bmatrix}$ and $ \vert - \rangle = \frac{1}{\sqrt 2}\begin{bmatrix} 1 \\ -1 \end{bmatrix}$, therefore the $X$ gate can be written as $$ \begin{align} X &= 1 \vert + \rangle \langle + \vert - 1 \vert - \rangle \langle - \vert, \\ & = \frac{1}{2} (\vert 0 \rangle + \vert 1 \rangle)(\langle 0 \vert + \langle 1 \vert) -\frac{1}{2} (\vert 0 \rangle - \vert 1 \rangle)(\langle 0 \vert - \langle 1 \vert), \\ & = \vert 0 \rangle\langle 1 \vert + \vert 1 \rangle\langle 0 \vert, \\ &= \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}. \end{align} $$

▢

--- Now, we will start developing the intuition behind phase estimation using the concept of *phase kickback*.

Codercise P.1.1 - Detecting a negative phase

Codercise P.1.2 - Finding the eigenvalues of Pauli X

Relative and global phases

Phase kickback