Implementing Grover’s search algorithm with Qiskit

Abstract

Quantum algorithms can solve certain problems faster than classical algorithms. One such problem is finding a marked item from an unstructured database. Classical algorithms need O(N) trials to find the marked item from a database of N items but Grover’s search algorithm, also called the quantum search algorithm, finds the marked item with O(√N) trials.

This thesis presents the theoretical background of qubits, quantum gates, quantum circuits and Grover’s algorithm. Grover’s algorithm uses an equal superposition of states of the items in the database and then amplifies the amplitude of the state of the marked item. IBM’s software development kit, Qiskit, is used to program quantum circuits that implement Grover’s algorithm. The programs are run on an ideal quantum computer simulator and on IBM’s actual superconducting quantum computer. The results of the simulations match with the theoretical results, but the experiments on real hardware show different results because of gate errors and noise from interactions with the environment. To have the quantum advantage over classical computers, quantum computers need a larger number of qubits and quantum error correction.