Intro to QPE and Phase Encoding — QPE algorithms
Mathematics for QPE
This is the first post in a new series on Quantum Phase Estimation algorithms. The series aims to dive into a very important subroutine in quantum computation: the QPE algorithm. In the first two posts, we will look at the basics of the QPE algorithm — what it is, why is it needed and some mathematics required to fully understand it. These posts assume that the reader is familiar with the linear algebra required for quantum computing. You may look at our Linear Algebra series to brush up on such concepts. Let us get started then!
Intuition behind QPE
Let’s start with an analogy.
Imagine you have a shelf. Suppose that shelf contains planks at different heights. Each plank provides some definitive information about your shelf. If some plank is at height h, then it provides us with a piece of information that this shelf has the ability to contain objects that would be placed at height h. You can also have other planks with heights h1, h2, h3, and so on. Each value for height gives you some information about the shelf. Well, how do you measure this height? You take a ruler and you measure it relative to your floor or some surface.
This is the essential idea behind QPE. Quantum Phase Estimation is a procedure, an algorithm used to measure the eigenvalues of an unknown unitary matrix. Sounds tough? Let’s relate it.
Think of the unitary matrix as the shelf which has eigenvalues (which are, back to the analogy, the heights of the planks). QPE is the act of measuring these eigenvalues. What is the ruler then? That’s the math and the neat tricks we employ in our algorithm! How do we do it? To measure with a ruler, we need to know how to read its scale, and thus for understanding how we measure the phase requires us to look at the math needed to make sense of the QPE algorithm.
Required Mathematics
1. Nature of eigenvalues of a unitary matrix
Any unitary matrix, in quantum mechanics, is a square matrix that satisfies the following equation:
This has implications for the eigenvectors of U (unitary matrix) and the corresponding eigenvalues. The following image would make things a lot clearer:
We can now clearly see that any eigenvector, λ, of a unitary matrix, U, satisfies the following equation:
where θ is the angle or the phase associated with the eigenvalue of U. Since determining this θ ensures that we can also determine the eigenvalue of the matrix, the QPE algorithm is all about determining this phase.
NOTE: although θ can be anything, we assume that θ belongs to [0,2π) as any angle > 2π or < 0 can always be brought down to the domain [0,2π). Have a thought about how this can be done and why is it equivalent.
2. Phase Kickback
Now that we are aware of what the phase we are looking for in QPE is, let’s look at a neat little trick that enables us to run QPE in the first place.
Imagine you have a unitary matrix U and you form a single-qubit control gate out of it. Let’s call this gate CU. This is a controlled unitary gate that is conditioned on a single qubit and looks something like this:
Now, let us say that this CU gate acts on a state |λ⟩ present in a target quantum register and has a control qubit in the state |q⟩ present in the control quantum register. If we assume |λ⟩ to be an eigenvector of U, as we change the state |q⟩, the following results arise —
What if control was in an equal superposition of |0⟩ and |1⟩?
Since the eigenvector can be factored out as an independent quantum state in our system, we are left with a relative phase kicked back into our control qubit. This attachment of relative phase to a control qubit due to the action of a CU gate on its eigenvector is called Phase Kickback. For a more thorough understanding, be sure to check out our article explaining the same. But the bigger question is, how is this phase kickback going to help us in phase estimation?
3. Encoding phase to control qubits
As we just saw, the phase kickback process allows us to encode the eigenvalue of a unitary matrix as a relative phase in the superposition state of a qubit. From image 6, it can be clearly seen that this eigenvalue was encoded as a relative phase in our control qubit. But, how do we determine this phase?
The next part requires some patience, so bear with me!
As mentioned in image 4, we can assume the phase θ belongs to the interval [0,2π). Further, for representation’s sake, we may say that θ = θ* ⋅ (2π) where θ* belongs to the interval [0,1). Determining this θ* is equivalent to determining θ as they only differ by a constant factor and since θ* is a decimal number between 0 and 1, it can be represented as a binary fraction, that is —
where n is the precision up to which this binary fraction has been defined.
For example, a phase of 1/4 looks something like 0.01 in binary. In this case, the phase has an exact representation in binary form. For a phase of 1/5, we have to specify up to what precision we want to determine this θ. Let’s say we want a precision of 4 bits, then we have our representation as 0.0011 for θ = 1/5.
Now that the representation is taken care of, let’s get to the encoding (and most interesting) part. If we have an n-bit binary representation of the phase, it makes sense to use n-qubits for each of the bit. The essential idea behind encoding is that we somehow want to encode each of the bits present in our phase such that when we measure the qubits, in which we encoded our phase, we get a correct estimate of the phase with high probability. Taking this one step further, let us actually look at the math that would help us realize the same.
Let’s look at the following circuit —
Here, as we understood in phase kickback, |λ⟩ is an eigenvector of U, the control qubit is in an equal superposition of |0⟩ and |1⟩ but the matrix is a bit different. What is it?
Let us mathematically define the system that we have with us —
What does (2^j)θ mean here? It is just equal to the bit representation of θ shifted left j times as you would expect for any binary fraction. But since this binary representation is present as the power of the imaginary exponent, we can simplify our state further as:
We simplified the left half before the decimal point of our binary exponent to k because the binary representation of any number has an integral part and a fractional part. If we take the example of 4.25, we have an integral part of 4 and the fractional part as 0.25 or 1/2². This number, 4.25, can be represented as 4 + 1/2² which is equal to 100 + 0.01 in binary. Now, 100 here represents k in our expression. Since this binary representation, to the left of the decimal point, is for an integer, we say that k is an integer. You may even refer to this link for a more clear understanding of the binary representation of numbers.
The final result that we get after all of this heavy-duty math is a simple expression which says that:
Let’s take some examples to clear things out more. Let us say θ is 1/4 = 0.01 in binary. If we apply the matrix U 2¹ times we will have:
If the value of θ is 1/5 = 0.0011, up to 4-bit precision, and we apply the matrix U 2² times, the system would look something like —
Let the above math sink in nicely before you move ahead as this is the backbone for the phase estimation procedure that we are going to explore in our following posts.
Okay, with this math under our belts, let us see how the whole phase encoding step looks like.
As we discussed before, it made sense to take n-qubits to estimate the phase up to n-bit precision. Let us then take n ancillary (extra) qubits and look at what the combined state for our system looks like. We number the extra qubits from 0 to n-1 and each jth qubit has the matrix U^(2^j) applied to it. This is what we get:
To remember this expression, a simple way would be that the phase, which is encoded in the qubit j, is shifted j places to the left due to the application of the unitary U^(2^j).
At this point, we have the tools to understand the phase estimation algorithm to some extent. We understood what is the phase in the QPE algorithm, how it can be represented efficiently and looked at a neat procedure to encode that phase into different qubits. But this is only half the picture. The last piece of the puzzle is extracting the bits out of those qubits. This would lead us to something called a Quantum Fourier Transform which is much, much simpler than it sounds!
Extracting the phase, combining everything to form our QPE algorithm, and why we care about the phases of a unitary matrix so much are going to be some of the topics of our next post in this series. Hope you learned a thing or two from this post and found it as exciting as it really is! Stay tuned for more by Quantum Untangled.
