Application of Grover’s quantum algorithm for string matching

Abstract

In this work we present a quantum algorithm for exact string matching that relies on Grover’s algorithm. Grover’s algorithm, commonly used for unsorted data search, can be adapted to solve the problem and find a pattern’s location within a string. This work contains the demonstration of Grover’s algorithm for one and multiple target. It also presents the principles of quantum string matching, how to tackle this type of problem using Grover’s algorithm and the detailed steps to construct the query. The quantum string matching algorithm is then implemented in Qibo, an open-source full stack API for quantum simulation and quantum hardware control. We explicitly expose an example for a string of length N = 8 and a pattern of length M = 2.