How would you draw the phase-estimation circuit for the eigenvalues of $U = \mathrm{diag}(1,1,\exp(\pi i/4),\exp(\pi i/8)) $?

Question

How would you draw the phase-estimation circuit for the eigenvalues of:

$U = \mathrm{diag}(1,1,e^{(\pi i)/ 4}, e^{(\pi i)/8}) $

corresponding to the eigenstates $|10\rangle$ and $|11\rangle$?

What is the state prior to the measurement?

Also how many additional qubits would be needed to get a good estimation?

Answer 1

TL;DR

What does the circuit look like? See the diagram below. This one uses 3 measurement qubits and the eigenstate is $|11\rangle$. Here I prepare the $|11\rangle$ with two Pauli $X$ gates. You could also prepare a linear combination of eigenstates instead if you like.

What is the state prior to measurement? For $m=4$ measurement qubits the state will be $|0001\rangle$. If we use $m=3$ instead we end up with an equal superpositon of $|000\rangle$ and $|001\rangle$.

How many qubits to get a good estimate? In this case we can exactly estimate the phase with $m=4$ measurement qubits. In general more qubits means more precision at the expense of a larger circuit.

EDIT:

Code to accompany this example is available at

https://tket.quantinuum.com/examples/phase_estimation.html

Background

Phase estimation allows you to approximate the eigenvalues of some unitary operator $U$ to some precision. The precision will depend on the number of qubits in your measurement register which will also determine the size of your circuit.

Given that $U$ is unitary its eigenvalues must lie on the unit circle.

\begin{equation} U |\psi \rangle = e^{2 \pi i \theta}|\psi\rangle \end{equation}

Where \begin{equation} U = \mathrm{diag}(1,1,e^{(\pi i)/ 4}, e^{(\pi i)/8}) \end{equation}

and $|\psi\rangle$ is an eigenstate of $U$. In phase estimation we try to approximate $\theta$ by extracting an estimate from the measurement results. If our algorithm works we expect a single bitstring to be measured with high probability. This bitstring encodes a binary approximation to our phase $\theta$.

To be a little more precise QPE allows you to estimate $\theta$ to a precision $\varepsilon$ using $O(\log(1/\varepsilon))$ qubits. You can make phase estimation more and more precise provided you are willing to have a circuit with many controlled unitaries.

The Circuit

In your case the circuit will look something like the diagram below. There are several variants of phase estimation but I've gone with the "textbook" one.

1. Here I have used $m = 3$ measurement qubits to estimate the phase of $U$. The number of controlled $U$ operations increases exponentially with $m$.

2. Note that here I am using the two Pauli X gates to prepare the $|11\rangle$ eigenstate of $U$.

3. At the end of the circuit we apply the inverse quantum Fourier transform (QFT†) before measuring our qubits.

Please note: The circuit here uses 3 measurement qubits to estimate the phase. This is actually not quite enough for an exact measurement of the phase as $\theta = 1/16 = 1/(2)^4$. We need four qubits here (see the calculation below). If we run this circuit we will get the results $|000\rangle$ and $|001\rangle$ with roughly equal probability. This is because our true result ($\theta=1/16$) is halfway between $1/8$ and $0$.

The State Prior to Measurement

The unitary you gave actually is a pretty decent test case for phase estimation. Given that its a diagonal matrix you can just read off the eigenvalues and compare with the results of the algorithm.

\begin{equation} U|11 \rangle = e^{i(\pi/8)}|11 \rangle = e^{2\pi i \theta}|11 \rangle \implies \theta = \frac {1}{16} \end{equation}

You asked about what the state would be prior to measurement. Lets go through the circuit step by step and work it out.

After the first layer of single qubit gates in the diagram above we have the state. Note: Here I'll use four measurement qubits, this is one more than the above.

\begin{equation} |\psi_1\rangle = |11\rangle |+\rangle^{\otimes 4} = \frac{1}{4}|11\rangle \big(|0\rangle + |1\rangle)^{\otimes 4} \end{equation}

Now comes the sequence of controlled unitaries. These kick back a phase of $e^{i \pi/8}$ onto our measurement qubits each time we apply $U$. So if we apply $U^2$ we get $\big(e^{i \pi/8}\big)^2$ and so on.

\begin{equation} |\psi_2\rangle = \frac{1}{4}|11\rangle \big(|0\rangle + e^{i \pi/8}|1\rangle \big)\big(|0\rangle + (e^{i \pi/8})^2|1\rangle \big)\big(|0\rangle + (e^{i \pi/8})^4|1\rangle \big)\big(|0\rangle + (e^{i \pi/8})^8|1\rangle \big) \end{equation}

Okay now we are ready to apply the inverse quantum fourier transform which has the following action \begin{equation} \text{QFT}^† : \frac{1}{\sqrt{N}} \sum_{k=0}^{N - 1} e^{2 \pi ijk/N}|k\rangle \longmapsto |j\rangle\,, \quad N= 2^m \end{equation}

To apply the definition above, it's useful to rewrite $|\psi_2\rangle$ as the following sum. Here $N=16$. We pull out a factor of 2 to so we can identify $j$.

\begin{equation} |\psi_2\rangle = \frac{1}{4}\sum_{k=0}^{15}(e^{i \pi/8})^k |k\rangle =\frac{1}{4}\sum_{k=0}^{15}e^{2 \pi i k(\frac{1}{16})} |k\rangle \end{equation}

We can safely disregard the state $|11\rangle$ now as nothing else happens to these qubits.

Now if we stare at the equation above for a moment we see that $j=1$ (the numerator of our fraction) with the denominator (N=16).

We are now ready to apply the inverse QFT

\begin{equation} |\psi_3\rangle = \text{QFT}^†|\psi_2\rangle = |0001\rangle \end{equation}

Please note that the string $0001$ is a representation of $j=1$ using 4 bits. (See note above)

This state $|\psi_3\rangle$ is the state which we will measure with high probability. We see that the inverse QFT has essentially performed destructive interfernce, transforming the superposition into a state $|0001\rangle$.

\begin{equation} \theta_{estimate} = \frac{j}{N} = \frac{1}{16} \end{equation}

Here our value of $\theta$ is exactly expressible as $\frac{1}{2^l}$ for some integer $l$ ($\theta$ is a dyadic fraction) so our estimate is bang on. In general the answer will be a binary approximation of the phase.

Finally the eigenvalue corresponding to the state $|11\rangle$ \begin{equation} \lambda_{|11\rangle} = e^{2 \pi i \theta} = e^{i \pi/8} \end{equation}

Which is exactly what we would expect from looking at our matrix.