Quantum Fourier Transform and Basic QPE — QPE algorithms

In the last post of our series, we explored some of the required mathematics to tackle phase estimation. We learned phase kickbacks and phase encodings. This post revolves around the last piece of our puzzle (QPE), i.e., the Quantum Fourier Transform followed by the combination of all the mathematics into the QPE algorithm and why do we even care about it in the first place. Let’s get started then.

Classical Fourier transform, similar to its quantum counterpart. Image by AAVOS International.

Quantum Fourier Transform

Sounds a bit scary.

Anyway, let’s remember where we left off in the previous post. This image would help you in recalling the final quantum states that we had in the qubits:

Final qubit states after phase encoding- (1)

We concluded with the remark that phase was being encoded up to different bits in our ancilla register but we still needed a ‘way’ to extract those bits out. Quantum Fourier Transform(QFT) is how we do it.

Although many people teach QFT in a conventional way, saying that it is a change of basis(which it is) and then write the resultant state for a given binary state. We are not going to do that. Here, we are going to first build up the inverse circuit (QFT⁻¹) from scratch, look at its use case in the QPE algorithm and when we are comfortable with it, we just take the complex conjugate of the circuit that we have built.

Let us start from the simplest of cases. By simple, what I mean to say is that let us take the qubit which only has 1 bit of information encoded in its phase. Which bit is that? If we see closely, Q(n-1) contains only a single bit, θₙ encoded in its phase:

One-bit phase encoding-(2)

This is the last bit in our ancilla register. How do we extract it? Let’s try out some mathematics. Expanding our state when θₙ = 0 and θₙ = 1 gives us:

Final control state depending on last bit — (3)

This is a very important representation of our state. This means that whenever the value of θₙ is 0 or 1, our final state is going to be|+⟩ and |-⟩ respectively. This is exciting because |+⟩ corresponds to |0⟩ and |-⟩ corresponds to |1⟩ if we measure in the X-basis! Thus, if we apply an H-gate on this ancilla qubit, we are going to measure the qubit either as 0 with probability 1 or 1 with probability 1.

Circuit for measuring the control — (4)

Now think of this — if we have some means to transform each of the states Qi to the states |+⟩ or |-⟩(the X basis), we could measure them in the X basis and extract the information stored inside their phases, one bit at a time. Let us look at the math to drive home this simple discovery —

State of the control qubit before and after measurement -(5)

This is the basic idea behind QFT⁻¹ that we are trying to build — somehow extract the bit information from our qubits by changing the basis. Note that we are still building upon intuition and thus, we don’t have any concrete formula for it, yet.

If you understood the workings till now, let’s move on to the next qubit.

Two-bit phase encoding-(6)

Well, there isn’t just 1 bit in our phase encoding — there are 2. What if there was just 1? Could it be somehow reduced to that simpler case? You should remember one thing though — we have the final state of θₙ with us. Since we proved in image 5 that θₙ either collapses deterministically to 0 or 1, this also means that the previous bit was either in the state |0⟩ or in the state |1⟩ just before the collapse.

Let us have a closer look at the phase of the second last qubit.

Phase structure in two-bit encoding — (7)

Well, you see that if θₙ is 0, there shouldn’t be any trouble — we just measure in the X basis again and get the answer for the next bit. But if θₙ is 1, the phase needs to be reduced to a simpler version through which we can extract the next bit. If you think about it, doesn’t this sound like a conditional gate? If we have θₙ as 0, don’t do anything, if θₙ is 1 do something to simplify the phase. What is this something?

As we saw in image 7, the phase consists of contributions from both the current and the last bit. The phase contributed by the last bit θₙ can be turned off using a controlled rotation gate conditioned on the state of θₙ bit. This means if θₙ = 0, no gate is applied to the target qubit. If θₙ was 1, apply a rotation to cancel out the θₙ/2² term from our phase. What should the rotation be? It is exactly equal to —

Inverse rotation needed — (8)

Let us see the simple circuit which is used to accomplish this and what is the final state —

Final state for the 2-bit encoded phase-(9)

This is the heart of this transformation — we want to cancel out all the bits other than the one we want to find and then collapse the qubit to determine the bit information. Given that we have understood intuition till now, let’s look at the general case.

Let us say we have a phase, encoded as —

Phase encoded up to the bit j-(10)

and we want to determine θⱼ. If we are able to cancel out the bits —

The bits to be canceled-(11)

with the inverse rotation —

Inverse Rotation needed-(12)

we would be left with phase 0.θⱼ which allows us to determine θⱼ with very high certainty. This brings us to our controlled inverse rotation gate — a gate that is conditioned on a single control qubit and applies the needed inverse rotations in our current qubit:

Controlled rotation gate-(13)

Since the trailing bits, i.e.,

The bits to be canceled-(14)

would be identified by us as either |0⟩ or |1⟩ in earlier trials, we have the ability to apply the correct C-ROTₖ gates to turn off the kᵗʰ bit of our representation. To be clear, k is the position of the bit, from the decimal point, that we want to cancel out. For example, if the phase encoding is 0.001 and we want to cancel out the last bit(3rd from the decimal point), the C-ROT₃ gate, conditioned on the last bit state, would be applied.

Taking another example, let us say we wanted to determine the second last bit in our phase. Let us assume the phase encoding is something like 0.01. Now, to cancel out the θₙ(last bit) we would apply the C-ROT₂ gate conditioned on θₙ (as θₙ is the second bit to the right from the decimal point). The circuit we would be getting would be is exactly the same as we saw in image 9 with the change that the controlled gate, now, has a name —

Final circuit for 2-bit encoded phase — (15)

We have come a long way but I am sure that you have now understood what actually happens in the QFT⁻¹ circuit and are able to make sense of and thus appreciate the final circuit. Again, we have built QFT⁻¹ without any kind of pre-defined formula and maybe you could even build the formula by yourself!

Basic QPE with qiskit

OKAY. With all the math under our belt now, let us see the complete Phase Estimation circuit with all our components. We’ll be doing some hands-on phase estimation using IBM’s qiskit package and constructing our circuit piece by piece. The phase we are trying to estimate is 1/8 and we have a 1-qubit unitary. Since phase 1/8 is represented as 0.001 in binary, we will be using 3 extra qubits for phase encoding, one for each bit.

Phase and the unitary matrix

• Preparation of Eigenvector

The |1⟩ state acts as an eigenvector with eigenvalue 1/8.

• Phase Encoding

Phase being encoded into the extra qubits using the controlled U gates

• QFT⁻¹ circuit

QFT⁻¹ for three qubits. Since q2 contains the least significant bit of the phase, hence a swap gate is applied at the end for a better visual interpretation.

• Final Circuit in Qiskit

The complete phase estimation circuit

• Results for estimation using a single qubit phase gate with θ = 1/8

The final phase estimation result

Applications of QPE

The Quantum Phase Estimation algorithm is used as a sub-routine in many other quantum algorithms like Shor’s factoring algorithm (the most famous) and Quantum Amplitude Estimation algorithms. Another major application for QPE is eigenvalue estimation for quantum systems. Since atoms and molecules follow unitary evolution, the observable values of their hamiltonians are their eigenvalues, and using QPE, we could also estimate the energy eigenvalues of a molecule.

Coming to the end of this article, I would like you to take a step back from all the math and first intuitively think of the phase estimation algorithm, what it does, how can it be implemented, what are its limitations. Then when you are comfortable, the math should be worked out completely to get the final grasp. While we haven’t discussed what happens when the phase does not have an exact binary representation, we shall in the upcoming posts. I hope you liked the ideas and concepts behind Phase Estimation Algorithm and learned some new things here and there.

Stick around for more by Quantum Untangled.

You may find the code in this repository.