Article · Mathematics · June 14, 2024

Hybrid Classical–Quantum Text Search Based on Hashing

Farid Mansurovich Ablayev, Nailya Salikhova, Marat Ablayev

Abstract

The paper considers the problem of finding a given substring in a text. It is known that the complexity of a classical search query in an unordered database is linear in the length of the text and a given substring. At the same time, Grover’s quantum search provides a quadratic speed-up in the complexity of the query and gives the correct result with a high probability. We propose a hybrid classical–quantum algorithm (hybrid random–quantum algorithm, to be more precise) that implements Grover’s search to find a given substring in a text. As expected, the algorithm works (a) with a high probability of obtaining the correct result and (b) with a quadratic query acceleration compared to the classical one. What is new is that our algorithm uses the uniform hash family functions technique. As a result, our algorithm is much more memory efficient (in terms of the number of qubits used) compared to previously known quantum algorithms.

Quantum Computing Algorithms and ArchitectureAlgorithms and Data CompressionQuantum Information and Cryptographyhybrid quantum-classical algorithmsGrover's algorithmsubstring search

Hybrid Classical–Quantum Text Search Based on Hashing

Abstract

More by Marat Ablayev