Hybrid Classical–Quantum Text Search Based on Hashing

Farid Ablayev (), Nailya Salikhova () and Marat Ablayev ()
Additional contact information
Farid Ablayev: Institute of Computational Mathematics and Information Technology, Kazan Federal University, Kazan 420008, Russia
Nailya Salikhova: Institute of Computational Mathematics and Information Technology, Kazan Federal University, Kazan 420008, Russia
Marat Ablayev: Institute of Computational Mathematics and Information Technology, Kazan Federal University, Kazan 420008, Russia

Mathematics, 2024, vol. 12, issue 12, 1-13

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.

Keywords: text search; quantum hashing; Grover’s algorithm; prime numbers; strongly (n,?)-universal family of hash functions (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2024
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/12/12/1858/pdf (application/pdf)
https://www.mdpi.com/2227-7390/12/12/1858/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:12:y:2024:i:12:p:1858-:d:1414877

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().