Iterative Phase Estimation Algorithm

The latest version of this notebook is available on https://github.com/qiskit/qiskit-tutorial.

For more information about how to use the IBM Q Experience (QX), consult the tutorials, or check out the community.

Contributors

Antonio Córcoles, Jay Gambetta, Rudy Raymond

Quantum Phase Estimation (QPE)

The Quantum Phase Estimation (QPE) algorithm solves the problem of finding unknown eigenvalues of a unitary operator. The attractiveness of the QPE algorithm is due to the fact that it is a key ingredient of some other very powerful algorithms, like order-finding and Shor's.

In a standard textbook, such as Nielsen & Chuang Quantum Computation and Quantum Information, in the QPE, each bit of the phase is encoded in a different qubit on a register using the phase kickback property of controlled-unitary operations. This is followed by an inverse Quantum Fourier Transform operation, which yields an n-bit approximation to the phase by reading the n-qubit register.

Iterative Phase Estimation Algorithm (IPEA)

The QPE algorithm can, however, be realized in a much smaller qubit system, by iterating the steps on a system of just two qubits. This is called the Iterative Phase Estimation Algorithm (IPEA).

Consider the problem of finding $\varphi$ given $|\Psi\rangle$ and $U$ in $U |\Psi\rangle = e^{i \phi} | \Psi \rangle$, with $\phi = 2 \pi \varphi$. Let's assume for now that $\varphi$ can be written as $\varphi = \varphi_1/2 + \varphi_2/4 + ... + \varphi_m/2^m = 0.\varphi_1 \varphi_2 ... \varphi_m$, where we have defined the notation $0.\varphi_1 \varphi_2 ... \varphi_m$. Now, if we have two qubits, $q_0$ and $q_1$, and we initialize them as $q_0 \rightarrow |+\rangle$ and $q_1 \rightarrow |\Psi \rangle$, then, after applying a control-U between $q_0$ and $q_1$ $2^t$ times, the state of $q_0$ can be written as $|0\rangle + e^{i 2 \pi 2^{t} \varphi} | 1 \rangle$. That is, the phase of $U$ has been kicked back into $q_0$ as many times as the control operation has been performed.

For $t=0$, we have a total phase in $q_0$ of $e^{i 2 \pi 2^{0} \varphi} = e^{i 2 \pi \varphi} = e^{i 2 \pi 0.\varphi_1 \varphi_2 ... \varphi_m}$

For $t=1$, the phase would be $e^{i 2 \pi 2^{1} \varphi} = e^{i 2 \pi \varphi_1} e^{i 2 \pi 0.\varphi_2 \varphi_3 ... \varphi_m}$

For $t=2$, $e^{i 2 \pi 2^{2} \varphi} = e^{i 2 \pi 2 \varphi_1} e^{i 2 \pi \varphi_2} e^{i 2 \pi 0.\varphi_3 \varphi_4 ... \varphi_m}$

And for $t=m-1$, $e^{i 2 \pi 2^{m-1} \varphi} = e^{i 2 \pi 2^{m-2} \varphi_1} e^{i 2 \pi 2^{m-3} \varphi_2} ... e^{i 2 \pi 2^{-1} \varphi_m} = e^{i 2 \pi 0.\varphi_m}$. Note that if we perform a Hadamard operation on the state $|0\rangle + e^{i 2 \pi 0.\varphi_m}|1\rangle$ and perform a measurement in the standard basis, we obtain $|0\rangle$ if $\varphi_m = 0$ and $|1\rangle$ if $\varphi_m = 1$.

In the first step of the IPEA, we directly measure the least significant bit of the phase $\varphi$, $\varphi_m$, by initializing the 2-qubit register as described above, performing $2^{m-1}$ control-$U$ operations between the qubits, and measuring $q_0$ in the diagonal basis.

For the second step, we initialize the register in the same way and apply $2^{m-2}$ control-$U$ operations. The phase in $q_0$ after these operations is now $e^{i 2 \pi 0.\varphi_{m-1}\varphi_{m}}= e^{i 2 \pi 0.\varphi_{m-1}} e^{i 2 \pi \varphi_m/4}$. We see that prior to extracting the phase bit $\varphi_{m-1}$, we must perform a phase correction of $\varphi_m /2$. This is equivalent to a rotation around the $Z-$axis of angle $-\varphi_m /4$.

Therefore, the $k$th step of the IPEA, giving $\varphi_{m-k+1}$, consists of the register initialization ($q_0$ in $|+\rangle$, $q_1$ in $|\Psi\rangle$), the application of control-$U$ $2^{m-k}$ times, a rotation around $Z$ of angle $\omega_k = -2 \pi 0.0\varphi_{k+1} ... \varphi_m$, a Hadamard transform to $q_0$, and a measurement of $q_0$ in the standard basis. Note that $q_1$ remains in the state $|\Psi\rangle$ throughout the algorithm.

IPEA circuit

Let's first initialize the API and import the necessary packages

Now you can try the following circuit in the quantum simulator for a phase of $-5\pi/8 = 2 \pi \varphi$ and $m=4$. Note that the IPEA cannot be run in the real device in this form, due to the current lack of feedback capability.

The results are given in terms of $\varphi = 0.\varphi_1 \varphi_2 \varphi_3 \varphi_4$, with the least significant digit ($\varphi_4$) as the leftmost bit in the classical register. The result is $\varphi = 11/16$, from which $\phi = 2\pi \varphi = 11 \pi/8 = 2 \pi - 5\pi/8$, as encoded in the circuit.

IPEA in the real device

As we have mentioned before, we currently lack the ability to use measurement feedback or feedforward, along with qubit resetting, on the real device in the Quantum Experience. However, we still can implement a segmentized version of the IPEA by extracting the information about the phase one bit at a time.

Try the following four circuits in the real device. They estimate the same phase as in the previous example (-5$\pi/8$), one bit at a time, from least ($\varphi_4$) to most ($\varphi_1$) significant bit.

In the first step of IPEA as above, we obtain the bit "1" with probability close to one. We then proceed to the second step of IPEA, assuming that we have identified the result of the first step correctly, as below.

In the second step of IPEA as above, we obtain the bit "1" with probability close to one. We then proceed to the third step of IPEA, assuming that we have identified the result of the first and second steps correctly, as below.

In the third step of IPEA as above, we obtain the bit "0" with probability close to one. We then proceed to the fourth step of IPEA, assuming that we have identified the result of the first, second, and third steps correctly, as below.

In the fourt step of the IPEA, we identify the bit "1" with high probability. In summary, we can conclude with high probability that the binary string of the phase is "1011"; that is, eleven in the decimal.

We have left aside the case when $\varphi$ does not accept a decomposition of the form $\varphi = \varphi_1/2 + \varphi_2/4 + ... + \varphi_m/2^m$. In that case, it can be shown that we can still use the IPEA to obtain $\varphi$ to an accuracy of $2^{-m}$ with greater than a constant probability independent of $m$ (around $81\%$ [1]).

References

[1] M. Dobsicek et al. Phys. Rev. A 76, 030306 (2007)