Grover’s algorithm
I will be using qiskit to study quantum algorithms in my own way. Since this is a record of my personal study, I may have left out a lot of explanations.
I am following the qiskit website.
Grover’s algorithm is famous for its ability to perform search problems very fast. For the search problem of an array with a normal list structure, performing a sequential search requires a computation time of $O(1)$ in the best case and $O(N)$ in the worst case. Also, if the list is sorted, using bipartite search is $O(N)$, which is exponentially faster.
Grover’s algorithm can achieve a computation speed of $O(\sqrt{N})$ even if the data is unstructured and unsorted.
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
from qiskit import IBMQ, Aer, assemble, transpile
from qiskit import QuantumCircuit, ClassicalRegister, QuantumRegister
from qiskit.providers.ibmq import least_busy
from qiskit import execute
from qiskit_textbook.tools import array_to_latex
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.
Amplitude amplification
A simple idea is to prepare $n$ bits, map $2^n$ states to the values you want to search, and search for one of the states you want to measure. However, in the initial state, the amplitudes of all the states are the same, so it will take an average of $2^n$ measurements to search for one state from the superimposed states.
The solution to this problem is the concept of amplitude amplification. The amplitude of the state to be searched for is amplified by applying the unitary operator to create a state where the state to be measured is measured with a very high probability.
We now decompose all the states into two states, the target state $(|\omega\rangle)$ and its orthogonal state $(|s’\rangle)$, and consider the vector space created by the two. The states of all superpositions are evenly distributed $|s\rangle$, and using a certain phase $\theta$.
$$ |s\rangle = \cos \theta\left|s^{\prime}\right\rangle + \sin \theta|w\rangle $$
This can be expressed as In the following, we will apply the rotation operation from this state to amplify the amplitude of the target vector.
Image of the rotation operation
The amplitude amplification algorithm is to maximize the amplitude of $|s’\angle$ from the initially large amplitude of $|s’\angle$ by performing the following $U_f$ and $U_s$ operations.
U_f(InvertUs)
Invert the amplitude of the components of $|\omega\rangle$.
$$ U_{f}=\left(\begin{array}{ll} 1 & 0 \\ 0 & -1 \end{array}\right) $$
U_s(Inverted for s)
Invert against $|s\rangle$. To flip symmetrically, we need to go through three steps: 1.
1. rotate only -theta
$$ U_{s_1}=\left(\begin{array}{cc} \cos (-\theta) & -\sin (-\theta) \\ \sin (-\theta) & \cos (-\theta) \end{array}\right) $$
2. Invert the amplitude of the ’s’ axis
$$ U_{s_{2}}=\left(\begin{array}{ll} 1 & 0 \\ 0 & -1 \end{array}\right) $$
3. rotate only theta
$$ U_{s_3}=\left(\begin{array}{cc} \cos \theta & -\sin \theta \\ \sin \theta & \cos \theta \end{array}\right) $$
Combination
Combining 1-3 above, we can express the inversion of symmetry for $|s\rangle$.
$$ \begin{aligned} U_s=U_{s_3} U_{s_2} U_{s_1} &=\left(\begin{array}{cc} \cos \theta & -\sin \theta \\ \sin \theta & \cos \theta \end{array}\right)\left(\begin{array}{cc} 1 & 0 \\ 0 & -1 \end{array}\right)\left(\begin{array}{cc}) \cos \theta & \sin \theta \\ -\sin \theta & \cos \theta \end{array}\right) \\ &=\left(\begin{array}{cc} \cos 2 \theta & 2 \sin \theta \cos \theta \\ 2 \sin \theta \cos \theta & -\cos 2 \theta \end{array}\right) \\ &=\left(\begin{array}{cc} \cos 2 \theta & \sin 2 \theta \\ \sin 2 \theta & -\cos 2 \theta \end{array}\right) \end{aligned} $$
U_s and U_f.
$$ \begin{aligned} U_{s} U_{f} &=\left(\begin{array}{cc} \cos 2 \theta & \sin 2 \theta \\ \sin 2 \theta & -\cos 2 \theta \end{array}\right)\left(\begin{array}{cc} 1 & 0 \\ 0 & -1 \end{array}\right) \\ &=\left(\begin{array}{cc} \cos 2 \theta & -\sin 2 \theta \\ \sin 2 \theta & \cos 2 \theta \end{array}\right) \end{aligned} $$
This matrix is
$$ |s\rangle = \cos \theta\left|s^{\prime}\right\rangle + \sin \theta|w\rangle $$
is the matrix that rotates by an additional $2\theta$, so
$$ \begin{aligned} &U_s U_{f}\left(\cos \theta\left|s^{\prime}\right\rangle+\sin \theta|\omega\rangle\right) \\ &=\cos 3 \theta\left|s^{\prime}\right\rangle+\sin 3 \theta|w\rangle \end{aligned} $$
and as a result, we have a phase of $3\theta$.
Generalizing and performing the operation $k$ times, we get
$$ \begin{aligned} &\left(U_{s} V_{f}\right)^{k}\left(\cos \theta\left|s^{\prime}\right\rangle+\sin \theta|\omega\rangle\right)\\ &=\cos (2 k+1) \theta\left|s^{\prime}\right\rangle+\sin (2 k+1) \theta|\omega\rangle \end{aligned} $$
In a normal search problem, $\theta$ is very small (the items to be searched are very small compared to all the items to be searched), but after repeating this operation many times, it will be multiplied by $2k+1$ and the amplitude of $|omega\rangle$ will increase.
Number of Measurements
Here, the probability of detecting $|\omega\rangle$ is maximized when $\displaystyle (2k + 1)\theta \approx \frac{\pi}{2}$, so
$$ k = \frac{\pi}{4\theta} - \frac{1}{2} $$
is the number of rotation operations to be used as a guide. Since we have the assumption that $\theta$ is very small, if the number of items to be searched is $M$ and the total number of items is $N$, then
$$ \theta \sim \sin\theta = \sqrt{\frac{M}{N}} $$
So, we get
$$ k \sim O\left(\sqrt{\frac{N}{M}}\right) $$
We can see that we can maximize the probability amplitude for symmetric data with the number of measurements
Implemented in qiskit
We would like to try to see what kind of circuit $U_f$ and $U_s$ will be in the case of two qubits. Let’s assume the search target is $|11\rangle$
U_f
For $U_f$, we only need to invert the target bit, so the CZ gate can be applied.
qc = QuantumCircuit(2)
qc.h(0)
qc.h(1)
qc.cz(0,1)
backend = Aer.get_backend('statevector_simulator')
final_state = execute(qc,backend).result().get_statevector()
array_to_latex(final_state, pretext="\\\\\\\\\\\\\\\\text{Statevector} = ")
$\displaystyle \\\\text{Statevector} = \begin{bmatrix} \tfrac{1}{2} \\ \tfrac{1}{2} \\ \tfrac{1}{2} \\ \frac{1}{2} \end{bmatrix} $
qc.draw('mpl')
U_s
$U_s$ can be achieved by applying adamant gates => CZ gates => adamant gates in that order.
$$ U_{s} = H^{\otimes n} U_{0} H^{\otimes n} $$
qc = QuantumCircuit(2)
qc.h(0)
qc.h(1)
qc.z(0)
qc.z(1)
qc.cz(0,1)
qc.h(0)
qc.h(1)
qc.draw('mpl')
Measure
Let’s apply $U_s$ and $U_f$ to two qubits and check that Grover’s algorithm holds.
qc = QuantumCircuit(2)
qc.h(0)
qc.h(1)
qc.cz(0,1)
qc.h(0)
qc.h(1)
qc.z(0)
qc.z(1)
qc.cz(0,1)
qc.h(0)
qc.h(1)
backend = Aer.get_backend('statevector_simulator')
final_state = execute(qc,backend).result().get_statevector()
array_to_latex(final_state, pretext="\\\\\\\\\\\\\\\\text{Statevector} = ")
$\displaystyle \\\\text{Statevector} = \begin{bmatrix} 0 \\ 0 \\ 0 \\ 1 \end{bmatrix} $
and the measurement probability of $|11\rangle$, which was the target, was maximized.