Kitaev’s Phase Estimation — QPE algorithms

Alexei Kitaev, source —Google

In the last few posts of the series, we touched upon the relevant tools required for QPE, some mathematics, and two of the most widely used QPE algorithms. This post is dedicated to the original phase estimation algorithm proposed by Alexei Kitaev and delves into the workings, advantages, and some limitations of the original phase estimation approach. It is assumed that the reader is familiar with the basic concepts of quantum phase estimation and linear algebra. Also, if you have been following the series up until now, you shall be good to go! Let’s get started then.

Ideas and Mathematics

To remind you of our original problem, what we have is an unknown unitary matrix U and we want to find the eigenvalues of our matrix. Since any eigenvalue of a unitary matrix has unit modulus, it can be represented as follows

The unitary eigenvalue equation —(1)

If we are somehow able to determine θ, we would be able to find the eigenvalue of the unitary matrix U.

Although the basic and iterative QPE algorithms build up our phase either bit by bit or encoding it into multiple qubits, Kitaev’s QPE (KQPE) algorithm relies on some classical processing to obtain a decimal representation of the phase. The readers familiar with QPE would appreciate the nature of the processing involved in KQPE as it is the inspiration for the previous two approaches. Let us go ahead and start from the basics.

Given below is the simple quantum circuit used for the phase kickback procedure:

Phase Kickback circuit — (2)

Going through the gates in our circuit mathematically we get:

Mathematics for phase kickback —( 3)

You can clearly see that the first qubit has some kind of information encoded into the relative phase of its state. But if we look closely, it is not enough. Why? This is because this relative phase has no observable effect when we try to measure only the first qubit:

Initial probabilities of qubit 1–(4)

Can we do something to make the factor containing θ appear in observable quantities i.e. probabilities of measuring 0 or 1? Try adding a Hadamard gate on the first qubit just after the controlled unitary gate. What do you see? Work on the math a bit before seeing the result below! In the following image, we see the effect of the Hadamard gate on the first qubit:

The first proposed circuit — (5)

Continued mathematics of the first circuit — (6)

Now we do have something! If we see carefully see the measurement probabilities we have:

Probabilities of qubit 1 after H gate is applied — (7)

How does this help? Let us digress a little bit to brush up on some mathematics to fully understand and thus make use of these equations to evaluate our phase, θ.

Euler’s Identity and Trigonometry

Leonard Euler, one of the greatest mathematicians of all time, had devised a beautiful equation, now known as Euler’s formula. It is a very simple formula that relates the exponential of a real quantity with its corresponding cosine and sine values:

Euler’s Formula — (8)

If we try to do some twists and turns, we arrive at:

Finding a relation for cosine θ — (9)

Finding a relation for cosine θ — (10)

Doesn’t this look strangely familiar? It does and is exactly the probability of measuring the first qubit in our circuit as 0! This is pretty great as we have expressed the phase in a well-defined function for which an inverse exists. We shall get into the details of the above relation in a bit but first, let us state some useful trigonometric identities which will be used for further calculations in the KQPE algorithm:

Some trigonometric identities — (11)

Initial Results

Now that we have the tools, let’s see the final measurement probabilities in terms of trigonometric functions:

Probabilities of the first qubit in terms of cosine θ — (12)

Using the above two equations we arrive at the result that:

The phase in terms of inverse cosine function — (13)

Although we have the probabilities expressed as a function of cosθ, there is a bit of a problem here. Since cosθ is equal to cos(-θ), even if we evaluate arccos(2P(0)-1) or arccos(1–2P(1)), we won’t be able to distinguish whether the value pertains to +θ or -θ. This is because cosine has a positive value when the argument lies in the first or the fourth quadrants.

This limitation brings us to think about an alternative approach. If we could somehow encode the phase information in some other function that allows us to distinguish between +θ and -θ, we would be able to recover θ from the probabilities. Given that we are fairly deep in trigonometric functions, thinking of sine and tangent would be wise. Let us try for sine!

Building a modified circuit

The thought that would lead us to a different circuit for encoding phase as the sine is that:

Initial probabilities of the first qubit — (14)

Well, if we had a factor of i (iota) associated with exp(iθ), it could very well be written as:

Desired probabilities to achieve distinguishability in phase — (15)

to obtain the desired function of ‘sin(θ)’ in our results. (this is because of the fact that cos(θ + π/2) = -sin(θ) ). Follow along to see how!

Let us try to work backward and see this idea in action. We know that for trying to uniquely identify the phase of the unitary matrix, we want the following expression:

Desired probability expression for the first qubit — (16)

which means that the system should have been in the state:

Desired final state for the first qubit — (17)

just before measurement. How would that be possible? If we regroup the terms a little bit we shall see that:

The regrouped final state in the X basis — (18)

The above equation means that if we had applied an H gate to the state:

Desired state of the system just before the last H gate — (19)

we would get the state that we desire. Comparing the state of qubit 1 in the above image to the state of qubit 1 in the image (3), we can observe that only the |1⟩ state is affected by a factor of ‘i’. This transformation can be modeled as:

Required transformation matrix — (20)

For the readers familiar with the Clifford Gates, the above representation exactly matches with the S or the Rz(π/2) gate, up to a global phase. This is exciting as applying this S gate to qubit 1, just before the controlled unitary matrix, transforms the state as:

Desired transformation of the original superposition state — (21)

Now that we have arrived at the change that we would require in our circuit, let us look at the final result and the math to solidify our understanding:

Final modified circuit — (22)

The final state of the system — (23)

Finally, we have the probabilities of obtaining a 0 and 1 for the first qubit as:

The final desired probabilities of the first qubit — (24)

This lets us distinguish between the values of +θ and -θ as positive θ would correspond to a positive value ( in the domain 0,π) and negative theta would correspond to negative values ( again in domain 0,π). Going forward with our last stage of calculation and using something called the inverse trigonometric functions, we see that:

The phase in terms of inverse sine function — (25)

There is also a small caveat to using the inverse trigonometric functions. They are only defined for a certain domain of the input values. For those of you who aren’t familiar with inverse trigonometric functions, they are just like an inverse mapping of the outputs of the trigonometric functions to their respective inputs. For instance, since sin(x) is bound by [-1,1] in the output, the inverse of sin(x) (arcsin(x)) has its input bound by the output of sin(x). These domain conditions are always going to be satisfied for our inputs as:

Domain verification for inverse cosine and sine — (26)

We may also employ the inverse tangent or the arctan(x) function to evaluate theta values in the following way:

Obtaining phase in terms of the inverse tangent function — (27)

The reason for trying to use arctan is that the arctan function is more robust to errors than the arcsin function. If we have an error of, let’s say, s in our measured fractions and we plot the difference between the arctan and arcsin values for the actual and measured results, we would see something like:

A clip showing that the absolute error in arcsin(x) is always greater than arctan(x) where s is the measurement error in the input — (28)

This clearly shows that if we have an error in our measurements, the arctan function is a more robust function to use for the evaluation of our results. This leads us to the end of our KQPE algorithm with the final phase presented as :

The final phase in terms of an inverse tangent function — (29)

where the symbols have the relevant meanings as mentioned in previous images. Note that these probabilities are experimentally determined and thus we can indeed find out the phase of the unitary matrix using the simple equation above. This is Kitaev’s original approach for quantum phase estimation.

I hope this approach to solve the QPE problem made you ponder about how simple classical processing may sometimes pose an equivalent way to approach quantum computing problems and reduce the complexity of our operations by reducing the size of our quantum circuits.

During all our discussions with QPE algorithms, one thing which we skipped was the accuracy of our approach. How many measurements do we really need to make to get a good accuracy of the phase that we are trying to measure? How erroneous is our algorithm in measuring the phase that it is trying to evaluate? These are just the questions to be answered in our next post on the error and accuracy of QPE algorithms.

As always, stay tuned for more by Quantum Untangled.

For those of you who are curious, please follow this link to see the algorithm realized with IBM’s qiskit. Click here to go to the repository with the full code.