Quantum Phase Estimation
How to find the eigenvalue value?
In our previous article we have discussed about the Quantum Fourier Transform(QFT).
The QFT is interesting in that it can perform a basis transformation analogous to a Fourier transform exponentially faster than the best known classical algorithm.
The QFT is the key to a general procedure known as phase estimation, which in turn is the key for many quantum algorithms. So, in this article we discuss about quantum phase estimation(QPE).
Setup:
So far, the algorithms we discussed got the information about the function into the ±1 phase of each state, then we used this, for the Hadamard basis states. If we consider analogy for the quantum Fourier transform, we notice that there are roots of unity which are not just ±1. which means that a phase kickback trick will have to do phase kickback with roots of unity. We see both cases in the following sections.
Here we focus on solving an eigenvalue problem, namely an equation of the form as shown below
Let’s Recall some of the properties:
In the quantum case, we’re only going to be concerned with unitary operators, which we normally write as U.
with that, the phase estimation algorithm is used to determine the eigenvalues of a unitary operator.
The Problem:
Let U be a unitary operator that operates on m qubits with an eigenvector |x⟩ such that
We would like to find the eigenvalue exp(2𝜋𝑖𝜃) of |x⟩, which in this case is equivalent to estimating the phase 𝜃, to a finite level of precision. This is the reason the problem is termed as phase estimation.
We can write the eigenvalue in the form exp(2𝜋𝑖𝜃) because U is a unitary operator over a complex vector space, so its eigenvalues must be complex numbers with absolute value 1.
Here, the phase 𝜃 is going to be between zero and one, so we can write it as a decimal in binary notation as follows:
the binary decimal notation also equivalent as shown below:
Example: binary decimals
Let’s consider the number 0.75 in decimal which is 0.11 in binary,
since 0.11 ≡ 1 · (2^-1) + 1 · (2^-2) = 1/2 + 1/4 = 3/4 = 0.75
Algorithm:
The key to understanding the phase estimation algorithm is what happens in the following circuit.
Here, let U be a unitary operator and |ψ⟩ an eigenstate with eigenvalue λ = exp(2πi0.𝜃1) . We first perform a Hadamard gate on the first qubit to get the state
We then perform a controlled U operation. The action of this gate is to produce the new state as shown below
We apply controlled-U only if the input state is |1⟩, as shown below
from the problem definition applying unitary operator on |ψ⟩ results as shown in below
if we observe the above term, the second qubit register containing |ψ⟩ hasn’t changed. We shouldn’t expect it to, since |ψ⟩ is an eigenstate of U. Thus, no matter how many times we apply U to this register, nothing happens to |ψ⟩
well, what’s the point of applying U then?
The effect was that it wrote some information about the eigenvalue into the relative phase of the first qubit. which we can see in the above term.
Interesting! How can we read out this information from the quantum state?
Consider the effect of applying another Hadamard transformation on the first qubit, which will produce as shown below
if we apply the following H|0⟩ = |+⟩ and H|1⟩ = |-⟩ in the above term which results as shown below
By rewriting, we get the above term. if we closely observe 𝜃1 has two possible values either 0 or 1 from the Binary Decimal form which we have discussed above
Let’s analyze for 0 case:
in case of 1:
Thus, we measure with certainty (i.e., not probabilistically) a state that tells us exactly what the phase, and hence the eigenvalue, is.
for the Hadamard basis states the information is in the ±1 phase (eigenvalues) of each state.
The key idea of the phase estimation algorithm is to keep applying the same controlled-U operations, but at successively higher powers of two(i.e: 2⁰, 2¹, 2², 2³, … 2^n-1) which means (U¹, U², U⁴, U⁸, U¹⁶ …).
Let’s Analyze for two controlled-U operation(C-U) (n = 2; U¹, U²)
We’ve already computed what the first control does to the top register. The wavefunction at this point in the circuit is
Note that the relative phase in the first qubit now has two digits because we assumed that 𝜃 = 0.𝜃1𝜃2 consists of two digits.
The same exact operation now happens on the second qubit, except for one key difference - the power of U. In particular, U is now squared.
What effect does squared U creates?
from one of the properties we have mentioned above(start of the problem) for eigen values as
Which gives us applying the unitary twice to the eigenstate.
Here we have an interesting observation from above
The effect is that the decimal moves one place to the right.
Well, the interesting and convenient is, what happens in the exponent?
Here 𝜃1 is an integer and so the exponential is unity(2 times of Z is always a even number).
Generalizing the condition gives
After applying the squared-unitary operator(U²) on the above wavefunction is
How do we read out this information?
This time it’s not so easy as a simple Hadamard transform.
Which brings the quantum Fourier transform. In particular, the key fact that we’ll be using is the following:
from the QFT definition
rewriting to the below form
by simplifying the above form
by expanding the product term
the above terms concluded using the following conditions
By using the conclusion and rewriting as shown below
The state on the bottom looks exactly like what we end up with from phase estimation! except with the order of the bits reversed.
So, what we need to apply then to read out the information for the below term is the Inverse Quantum Fourier transform.
Thus, if we apply Inverse Quantum Fourier Transform to the state in as shown above, we get a product state containing the information we want about the phase as shown below
since |ψ⟩ is unchanged we can apply Inverse Quantum Fourier Transform on the first register itself.
General Phase estimation Algorithm:
If the phase 𝜃 can be written exactly in n bits, this circuit computes 𝜃 exactly. If it requires more bits, this circuit computes a “good” approximation to 𝜃.
ignoring the |ψ⟩ register that never changes, after applying the Hadamard’s as shown below
after applying the controlled unitary operator’s as shown below
after applying the Inverse Quantum Fourier Transform (reverse of Quantum Fourier Transform circuit shall gives the IQFT)as shown below
then by measuring the final state, we obtain a description of the phase, and hence the eigenvalue.
Implement QPE using qiskit and Cirq:
In this section we implement QPE circuit using qiskit for θ=1/3 = 0.333333….. and using cirq for a range of decimal values.
Implement QPE using qiskit:
As shown in the below qiskit1, generates initial conditions for the QPE algorithm
As shown in the below qiskit2, prepares psi wave function for the QPE algorithm.
As shown in the below qiskit3, generates Controlled U circuit for the given function.
As shown in the below qiskit4, generates Inverse Quantum Fourier Transform.
As shown in the below qiskit5, generates Quantum Phase Estimation circuit for the given function.
As shown in the below qiskit6, initializes the circuit, number of qubits, generates the QPE circuit.
visualize the generated circuit for the given function as shown in below qiskit7.
As shown in the below qiskit8, performs measurement using simulator.
After the circuit running over simulator, below is the histogram for the obtained result
Conclusion:
If we increase number of qubits used for precision register then we get better result.
Implement QPE using cirq:
the below function generates initial conditions for the QPE algorithm
the below function generates Controlled U circuit for the given function.
the below function generates Inverse Quantum Fourier Transform.
the below function generates the Quantum phase estimation circuit.
the below code block initializes the required settings and invokes qpe function
results generated from the above code block
updated: Aug/17/2021 — Notation correction
references: qiskit textbook, cirq tutorials, Wikipedia, stack exchange, Engineering mathematics, open source materials.
