Quantum Phase Estimation

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²)

Phase estimation for n = 2 qubits in the top register

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

qiskit1: generates initial conditions for the algorithm

As shown in the below qiskit2, prepares psi wave function for the QPE algorithm.

qiskit2: generates psi function

As shown in the below qiskit3, generates Controlled U circuit for the given function.

qiskit3: controlled U

As shown in the below qiskit4, generates Inverse Quantum Fourier Transform.

qiskit4: QFT Dagger

As shown in the below qiskit5, generates Quantum Phase Estimation circuit for the given function.

qiskit5: QPE circuit

As shown in the below qiskit6, initializes the circuit, number of qubits, generates the QPE circuit.

qiskit6: initialize, generate the required circuit

visualize the generated circuit for the given function as shown in below qiskit7.

qiski7: generated circuit (cond…)
qiski7: generated circuit (contd…)
qiski7: generated circuit (contd…)
qiski7: generated circuit (contd…)
qiski7: generated circuit

As shown in the below qiskit8, performs measurement using simulator.

qiskit8: 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.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store