|
This article is cited in 1 scientific paper (total in 1 paper)
Quantum search for a given substring in the text using a hashing technique
M. F. Ablayevab, N. M. Salikhovab a Zavoisky Physical-Technical Institute, FRC Kazan Scientific Center, Russian Academy of Sciences, Kazan, 420029 Russia
b Kazan Federal University, Kazan, 420008 Russia
Abstract:
The problem of searching for a given substring in the text was considered. It is known that classical algorithms solve this problem in a linear time depending on the length of the text and the specified template. Quantum algorithms speed up the search by “square root times”.
In this paper, we proposed a quantum algorithm that solves the search problem a) with a high probability of getting the correct result and b) with the same acceleration (by “square root times”) as compared with the classical one, but it c) requires much less memory (based on the number of qubits used) than the previously known quantum algorithms.
Keywords:
quantum algorithms, string search, quantum search.
Received: 23.07.2020
Citation:
M. F. Ablayev, N. M. Salikhova, “Quantum search for a given substring in the text using a hashing technique”, Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, 162, no. 3, Kazan University, Kazan, 2020, 241–258
Linking options:
https://www.mathnet.ru/eng/uzku1558 https://www.mathnet.ru/eng/uzku/v162/i3/p241
|
Statistics & downloads: |
Abstract page: | 184 | Full-text PDF : | 109 | References: | 13 |
|