Quantum search in a dictionary using fingerprinting function

Abstract

The problem of searching for an element within a dictionary was considered. Over the past decades, various approaches, including classical and quantum algorithms, have been proposed to solve it. One possible solution is the method of quantum amplitude amplification, which underpins the well-known Grover algorithm and enables a quadratic speedup in the search process.In this article, a new approach to searching for an element w of length m in a dictionary V of size n with the use of the quantum fingerprinting function was introduced. The developed algorithm has a query complexity of O(√n) and requires O(logn+logm) qubits.

Keywords

• quantum algorithm
• searching for element in dictionary
• quantum search
• error correcting code
• fingerprinting function