Quantum phase estimation

I am going to use qiskit to study quantum algorithms in my own way. This is a record of my personal study, so I may have left out a lot of explanations.

I am following the qiskit website.

Let’s study quantum phase estimation, which is the most important quantum algorithm. It is used in a variety of algorithms and understanding it is essential. It is a combination of phase kickback and quantum Fourier inversion, and estimates the eigenvalues of an eigenvector for a unitary operator (its phase).

github

  • The file in jupyter notebook format is here

google colaboratory

  • To run it in google colaboratory here

Author’s environment

!sw_vers

ProductName: Mac OS X
ProductVersion: 10.14.6
BuildVersion: 18G103

Python -V

Python 3.8.5

Import the basic libraries and check their versions.

%matplotlib inline
%config InlineBackend.figure_format = 'svg'

import qiskit
import json

import matplotlib.pyplot as plt
import numpy as np
import math

from qiskit import IBMQ, Aer, transpile, assemble
from qiskit import QuantumCircuit, ClassicalRegister, QuantumRegister

from qiskit.visualization import plot_histogram

dict(qiskit.__qiskit_version__)

{'qiskit-terra': '0.17.4',
 'qiskit-aer': '0.8.2',
 'qiskit-ignis': '0.6.0',
 'qiskit-ibmq-provider': '0.13.1',
 'qiskit-aqua': '0.9.1',
 'qiskit': '0.26.2',
 'qiskit-nature': None,
 'qiskit-finance': None,
 'qiskit-optimization': None,
 'qiskit-machine-learning': None}

Understanding the theoretical part

Find the eigenvalue $e^{2 \pi i \theta}$ of the eigenvector $|\psi\rangle$ for the unitary operator. The eigenvectors and unitary operators are assumed to be known.

$$ U|\psi\rangle=e^{2 \pi i \theta}|\psi\rangle $$

The quantum circuit for phase estimation looks like this The bits are ordered from the left side up. The quantum circuit for phase estimation looks like this. The bits on the left are ordered from top to bottom.

The top $N$ bits are the registers that store the quantum states, and the bottom bits are the eigenvectors. Apply the adamantine gate to the qubits in the first register, and apply the above unitary operator as the control unitary operator to each qubit in the first register. The number of times to apply is $2^k$ times for the $k$th bit.

$$ \begin{aligned} &|0\rangle^{\otimes n}\otimes|\psi\rangle \\ &\stackrel{H}{\rightarrow}\sum_{k=0}^{2^{n}-1}|k\rangle\otimes|\psi\rangle \\ &\stackrel{CU}{\rightarrow}\sum_{k=0}^{2^{n}-1} e^{2 \pi i k\theta}|k\rangle\otimes|\psi\rangle \end{aligned} $$

The last transformation of the equation is somewhat confusing, so let’s try a specific transformation of the equation for the case $n=2$.

$$ \begin{aligned} &|00\rangle\otimes|\psi\rangle \\ &\stackrel{H}{\rightarrow} \frac{1}{2}\left(|00\rangle+|01\rangle+|10\rangle+|01\rangle\right) \otimes |\psi\rangle\\ &\stackrel{CU_{1}}{\rightarrow} \frac{1}{2}\left(|00\rangle+e^{2 \pi i\theta}|01\rangle+\left|10\rangle+e^{2 \pi i \theta}\right| 11\rangle\right)\otimes|\psi\rangle\\ &\stackrel{CU_{2}}{\rightarrow} \frac{1}{2}\left(|00\rangle+e^{2 \pi i \theta}|01\rangle+e^{2 \pi i \theta}|10\rangle+e^{2 \pi i \theta \times 2}|11\rangle\right)\otimes \psi\rangle\\ &\stackrel{C U_{2}}{\rightarrow} \frac{1}{2}(|00\rangle+e^{2 \pi i \theta}|01\rangle+e^{2 \pi 1 \theta \times 2}|10\rangle+e^{2 \pi i \theta \times 3}|11\rangle\otimes|\psi\rangle\\ &=\sum_{k=0}^{3} e^{2 \pi i \theta k}|k\rangle \otimes|\psi\rangle \end{aligned} $$

This notation is used in Shore’s algorithm. This notation will appear in the Shore algorithm, etc., so it’s good to have a quick look and remember it.

$$ \frac{1}{\sqrt{2^n}}\sum_{k=0}^{2^{n}-1} e^{2 \pi i \theta k}|k\rangle \otimes|\psi\rangle \stackrel{\mathcal{Q F T}^{-1}}{\longrightarrow} \frac{1}{2^{n}} \sum_{x=0}^{2^{n}-1} \sum_{k=0}^{2^{n}-1} e^{-\frac{2 \pi i k}{2^{n}}\left(x-2^{n}\theta\right)}|x\frac rangle $$

When the measurement is performed in this state, the probability of observing $x=2^n\theta$ with the maximum amplitude is maximized.

Implemented with qiskit

I’m going to implement it with qiskit referring to the site and check that the phase estimation is done. Since the eigenvectors and unitary operators are known, I will follow qiskit and implement it using a T-gate as an example.

The T-gate has the eigenvalue $\displaystyle e^{\frac{i \pi}{4}}$ for $|1\rangle$.

$$ T|1\rangle=e^{\frac{i \pi}{4}}|1\rangle $$

Therefore, we have

$$ \theta=\frac{1}{8} $$

is the answer we seek.

First we prepare the circuit and create the eigenvector $|1\rangle$ using the NOT gate.

qpe = QuantumCircuit(4, 3)
qpe.x(3)
qpe.draw('mpl')

Apply adamantine gates.

for qubit in range(3):
    qpe.h(qubit)
qpe.draw('mpl')

Apply the control unitary operator sequentially to the qubits.

repetitions = 1
for counting_qubit in range(3):
    for i in range(repetitions):
        qpe.cp(math.pi/4, counting_qubit, 3);
    repetitions *= 2
qpe.draw('mpl')

Implement the IQFT functions.

def qft_dagger(qc, n):

    for qubit in range(n//2):
        qc.swap(qubit, n-qubit-1)
    for j in range(n):
        for m in range(j):
            qc.cp(-math.pi/float(2**(j-m)), m, j)
        qc.h(j)

qpe.barrier()
qft_dagger(qpe, 3)

qpe.barrier()
for n in range(3):
    qpe.measure(n,n)

qpe.draw('mpl')

aer_sim = Aer.get_backend('aer_simulator')
shots = 2048
t_qpe = transpile(qpe, aer_sim)
qobj = assemble(t_qpe, shots=shots)
results = aer_sim.run(qobj).result()
answer = results.get_counts()

plot_histogram(answer)

The result is $(001)_2=1$, so we solve for $2^3\theta=1$ to get the answer we want, $\displaystyle \frac{1}{8}$.

Impressions

The famous Shore’s algorithm is also an application of quantum phase estimation, so I think it is probably a very important algorithm. Still, I think it is really amazing that people think of this kind of thing first. Furthermore, I have to thank IBM for providing such a free tool.