Geodesic
Quantum search for a given substring in the text using a hashing technique
Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki, Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, Tome 162 (2020) no. 3, pp. 241-258 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

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. 
@article{UZKU_2020_162_3_a0,
     author = {M. F. Ablayev and N. M. Salikhova},
     title = {Quantum search for a given substring in the text using a hashing technique},
     journal = {U\v{c}\"enye zapiski Kazanskogo universiteta. Seri\^a Fiziko-matemati\v{c}eskie nauki},
     pages = {241--258},
     year = {2020},
     volume = {162},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/UZKU_2020_162_3_a0/}
}
TY  - JOUR
AU  - M. F. Ablayev
AU  - N. M. Salikhova
TI  - Quantum search for a given substring in the text using a hashing technique
JO  - Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki
PY  - 2020
SP  - 241
EP  - 258
VL  - 162
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/UZKU_2020_162_3_a0/
LA  - ru
ID  - UZKU_2020_162_3_a0
ER  - 
%0 Journal Article
%A M. F. Ablayev
%A N. M. Salikhova
%T Quantum search for a given substring in the text using a hashing technique
%J Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki
%D 2020
%P 241-258
%V 162
%N 3
%U http://geodesic.mathdoc.fr/item/UZKU_2020_162_3_a0/
%G ru
%F UZKU_2020_162_3_a0
M. F. Ablayev; N. M. Salikhova. Quantum search for a given substring in the text using a hashing technique. Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki, Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, Tome 162 (2020) no. 3, pp. 241-258. http://geodesic.mathdoc.fr/item/UZKU_2020_162_3_a0/

[1] Kitaev A., Shen' A., Vyalyi M., Classical and Quantum Computation, MTsNMO, M., 1999, 192 pp. (In Russian)

[2] Grover L. K., “A fast quantum mechanical algorithm for database search”, Proc. 28th Annu. ACM Symp. on Theory of Computing, 1996, 212–219 | DOI | MR | Zbl

[3] Gilliam A., Pistoia M., Gonciulea C., Optimizing quantum search using a generalized version of Grover's algorithm, 2020, arXiv: 2005.06468

[4] Brassard G., Hoyer P., Mosca M., Tapp A., “Quantum amplitude amplification and estimation”, AMS Contemporary Mathematics, 305, eds. Samuel J. Lomonaco Jr., 2002, 53–74 | DOI | MR | Zbl

[5] Reitzner D., Nagaj D., Buzek V., Quantum walks, 2012, arXiv: 1207.7283 | Zbl

[6] Ablayev F., Ablayev M., Huang J.Zh., Khadiev K., Salikhova N., Wu D., “On quantum methods for machine learning problems part I: Quantum tools”, Big Data Min. Anal., 3:1 (2019), 41–55 | DOI

[7] Ablayev F., Ablayev M., Huang J.Zh., Khadiev K., Salikhova N., Wu D., “On quantum methods for machine learning problems part II: Quantum classification algorithms”, Big Data Min. Anal., 3:1 (2019), 56–67 | DOI

[8] Knuth D. E., Morris J. H. Jr., Pratt V. R., “Fast pattern matching in strings”, SIAM J. Comput., 6:2 (1977), 323–350 | DOI | MR | Zbl

[9] Ramesh H., Vinay V., “String matching in $\widetilde{O}(\sqrt{n}+ \sqrt{m})$ quantum time”, J. Discrete Algorithms, 1:1 (2003), 103–110 | DOI | MR | Zbl

[10] Ambainis A., “Understanding quantum algorithms via query complexity”, Proc. Int. Congress of Mathematicians, ICM 2018, 2019, 3265–3285 | DOI | MR

[11] Boyer M., Brassard G., Høyer P., Tapp A., “Tight bounds on quantum searching”, Fortschr. Phys.: Prog. Phys., 46:4–5 (1998), 493–505 | 3.0.CO;2-P class='badge bg-secondary rounded-pill ref-badge extid-badge'>DOI

[12] Zhang K., Korepin V. E., “Examples on quantum search algorithm with optimized depth”, Phys. Rev. A, 101:3 (2020), 032346, 1–12 | DOI | MR

[13] Carter J. L., Wegman M. N., “Universal classes of hash functions”, J. Comput. System Sci., 18:2 (1979), 143–154 | DOI | MR | Zbl

[14] Stinson D. R., “Universal hashing and authentication codes”, Des. Codes Cryptogr., 4 (1994), 369–380 | DOI | MR | Zbl

[15] Stinson D. R., “Combinatorial techniques for universal hashing”, J. Comput. Syst. Sci., 48:2 (1994), 337–346 | DOI | MR | Zbl

[16] Ablayev F. M., Vasiliev A. V., “Cryptographic quantum hashing”, Laser Phys. Lett., 11:2 (2013), 025202, 1–4 | DOI

[17] Ablayev F., Ablayev M., “On the concept of cryptographic quantum hashing”, Laser Phys. Lett., 12:12 (2015), 125204, 1–5 | DOI | MR

[18] Ablayev F. M., Ablayev M. F., Vasilev A. V., “Universal quantum hashing”, Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, 156, no. 3, 2014, 7–18 (In Russian) | MR

[19] Macaluso A., Clissa L., Lodi St., Sartori C., Quantum Ensemble for Classification, 2020, arXiv: 2007.01028